Is there an algorithm to bit shift every n-long bits from a number without overflow?

Viewed 75

For example, if I have a number 0101 1111 and I want to shift every 4 bit long section to the left to get 1010 1110. While I could just modulo off each section to get two 4-bit numbers, is there an algorithm that doesn't need to do this?

2 Answers

A naive approach

A first naive appraoch is to slice the 4 bit groups and process them individually. The expected result is obtained with the following for the first group of 4 bits.

(((x & 0xf)          // take only 4 bits
    << 1)            // shift them by 1
       & 0xf)        // get rid of potential overflow    

For the n+1 th group of 4 bits, it's

(((x & (0xf<<(n*4)))
    << 1)
      & (0xf<<(n*4)))

Since this is designed, so that there is no overlap around the 4 bits that are processed, you could iterate, and binary-or the partial results.

A less naive approach

Another approach is to simply shift the full x by 1, causing every 4 bit group to be shifted at once:

0101 1111  -> 1011 1110

We can then easily get rid of the overflow, and at the same time make sure that 0's are injected on the left, by clearing every 4th bit in the result of the shift:

   1011 1110 
 & 1110 1110
   ---------
   1010 1110

1110 is e in hexadecimal. So you need to generate a number with as many 0xe as there are 4 bit segments. In your case it's 0xee if it's just 8 bits. It's 0xeeeeeeeeeeeeeeee if it's 64 bits. Someone told this answer in the comments. Here you have the explanation.

Caution if your underlying data type is signed, because of the sign bit. Do this processing on unsigned integers to avoid any surprise.

Here is one way.

int bits = 0b1111_0001_0011_0111;
int result = 0;
int m = 0b1111;
while(m != 0) {
    result |= ((bits & m) << 1) & m;
    m <<= 4;
}
System.out.printf("%-7s = %s%n","src", Integer.toBinaryString(bits));
System.out.printf("%-7s = %s%n","result", Integer.toBinaryString(result));

Prints

src     = 1111000100110111
result  = 1110001001101110
Related