CODEWITHSUNDEEP
javabitwise-operatorsbit
user3413646
user3413646

Reputation: 167

Bit circular shift

I am currently learning on bit-wise operations, and i am tasked to do a left rotate of 4-bit integer.

My code for a 4bit left rotate is

private static int BITS_IN_INTEGER = 4;

private static int leftRotate(int x, int n) {
  return (x << n) | (x >> (BITS_IN_INTEGER - n));
}

I want to make a 4-bit circular shift to maintain as a 4-bit after rotating but can't seem to understand how it works.

Example: 10 (1010) after left rotate by 1 bit will give me 5 (0101) but it gives me a value of 21 which is more than my 4-bit.

Any help to make me understand this problem will be much appreciated!

Upvotes: 1

Views: 1969

Answers (2)

lacroixDj
lacroixDj

Reputation: 101

This is a implementation of leftRotate() and rightRotate(), based on the above Answer from Socowi (thank you!)

I needed to emulate a simple compass with 90º degree rotations in both left (counter-clockwise) and right (clockwise) directions (not a real compass, just a funny problem).

So instead of messing up the code by storing the previous orientation and using * if / else * or * switch *, I came up with the idea that a or would be much more clean, efficient, and elegant of course.

However, I had the same problem about limiting the mask to 4 bits. Thanks to the above solution I was able to do it! ;)

So assuming the following:

 - North = 1 = 0001
 - West  = 2 = 0010
 - South = 4 = 0100
 - East  = 8 = 1000

When I need to turn 90º from North to -> West I call leftRotate() and so on until I get to the same point again (North).

The same applies in reverse, if turning 90º from North to -> East I call rightRotate(), and then again to turn South, and so on.

Here is the snippet, hope it helps:

const BITS_IN_INTEGER = 4;
const INTEGER_MASK = (1 << BITS_IN_INTEGER) - 1;

// this function rotates to left (counter clockwise) 1,2,4,8...1,2,4,8

function leftRotate(x, n) {
  return INTEGER_MASK & ((x << n) | (x >>> (BITS_IN_INTEGER - n)));
}


// this function rotates to right (clockwise)  1,8,4,2...1,8,4,2

function rightRotate(x, n) {
  return INTEGER_MASK & ((x << (BITS_IN_INTEGER - n)) | (x >>> n));
}

// Lets rotate:

console.log('--- Rotate to left (counter clockwise) 1,2,4,8...1,2,4,8...1:')

let value = 1;

for (let i = 0; i < 8; i++) {
  console.log(value);
  value = leftRotate(value, 1);
}

console.log('-- Rotate to right (counter clockwise) 1,8,4,2...1,8,4,2...1:')

for (let i = 0; i < 8; i++) {
  console.log(value);
  value = rightRotate(value, 1);
}

Upvotes: 3

Socowi
Socowi

Reputation: 27215

If I understood you correctly, you want to

  • emulate integers with BITS_IN_INTEGER many bits instead of 32 bits.
  • do a rotation on such an emulated integer

Currently you can do a rotation, but the upper bits of the actual int which are not part of the emulated int can end up in something other than 0. Example:

intput x
0000 0000  0000 0000  0000 0000  0000 1100
                                     |____|___, emulated int
result of rotating left by n=2       |    |
0000 0000  0000 0000  0000 0000  0011 0011

As we can see, all we have to do is setting the bits above the emulated int (that is the 32 - BITS_IN_INTEGER upper bits) to zero. To this end, we use a logical "and" (&). We need a mask that has 0 on the bits we want to set to zero (anything & 0 is always 0) and a 1 on the bits we want to keep (anything & 1 is always anything).

  0...0  0011 0011  ←  the result from before
& 0...0  0000 1111  ←  a mask
——————————————————
  0...0  0000 0011  ←  the masked result where unused bits are 0

To generate a mask of the form 0...01...1 with BITS_IN_INTEGER many 1s we can use (1 << BITS_IN_INTEGER) - 1. The - 1 converts 10000 into 01111. 

static int BITS_IN_INTEGER = 4;
static int INTEGER_MASK = (1 << BITS_IN_INTEGER) - 1;

static int leftRotate(int x, int n) {
  return INTEGER_MASK & ((x << n) | (x >>> (BITS_IN_INTEGER - n)));
}

Upvotes: 4

Related Questions