Bit circular shift

Question

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!

Answer 1

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)));
}