BitWise Operators Advanced Tricks

This article is an extension of BitWise Operators - Basic Tutorial. In this article we will look at some complex application of bitwise operators.

* Compute the parity of a number

Parity of a number is based on the count of SET bits ('1') in a number. If the total count of SET bits is even, it is known as even parity, otherwise its known as odd parity.

unsigned int v;       // word value to compute the parity of
bool parity = false;  // parity will be the parity of v

while (v)
{
  parity = !parity;
  v = v & (v - 1);
}


Explanation: expression (v & (v-1)) eliminates the left-most SET bit from a number, and the while loop will keep on running till all the SET bits are exhausted. In a way, we are calculating the SET bits in the number. Based on this count we can deduce the parity of the number. It returns 1 if parity is odd, otherwise it returns 0.


* Swapping two values without the use of temporary variable

#define SWAP(a, b) ((&(a) == &(b)) || \
            (((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))


Explanation: The check "((&(a) == &(b))" is used here to check whether the memory-locations of the two variables is same or not. Rest all is similar to our normal swap routine, its just that this function uses internal variables from system.
Note: This should only be used for integers and you might face overflow issues with large values.

There is a slightly faster method to achieve the above operation through the use of XOR operators

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))



* Swapping Individual bits with XOR operator

unsigned int i, j; // positions of bit sequences to swap
unsigned int n;    // number of consecutive bits in each sequence
unsigned int b;    // bits to swap reside in b
unsigned int r;    // bit-swapped result goes here

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));


Explanation: Let us take b=0010_1111, n=3, i=1 (second bit from right) and j = 5. Which means, we have to shift 3(n) consecutive bits from bit-position 1(i) to 5(j). Hence, it results in transition of 0010_1111 to 11100011.


Step1. First create a mask of as many bits you want to shift which is 3 in this case.
temp_a = ((1U << n) - 1) => (1000 - 1) => 0111


Step2. As explained in previous example of swapping using XOR operator, here also we would apply XOR operation on individual 3-bits (1-3 and 5-7) by applying the shift operators. i.e. XOR 111 with 001 (these are the actual bits we want to swap).
temp_b = (b >> i) ^ (b >> j) => (0010_1111 >> 1) ^ (0010_1111 >> 5) => (0001_0111) ^ (0000_0001) => 0001_0110


Step3. Apply mask created in step1 to get significant 3 bits.
x = temp_a & temp_b => 0000_0110


Step4. Use the temporary XOR pattern created in Step2 and move it to the desired place. i.e. position 5 to 7 and position 1 to 3.
temp_c = (x << i) | (x << j) => (0000_0110 << 1) | (0000_0110 << 5) => 0000_1100 | 1100_0000 => 1100_1100


Step5. Carry out the XOR with original number and the XOR pattern to get the desired effect.
r = b ^ temp_c => 0010_1111 ^ 1100_1100 => 1110_0011


* Reverse the bits

unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{  
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero


Explanation: The bit-reversal routine is pretty straightward. All we are doing is iterating over the whole bit set and then at each step, we are assinging the LSB (right-most bit) into the result. The last step "r <<= s" is neccessary to shift the left-over bits with value '0' which are at the present at the left side of the left-most SET bit (bit with value '1').

Here is a faster version of bit-reversal routine specifically for 32-bit word


unsigned int v; // 32-bit word to reverse bit order
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ...
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);



* Finding the log base 2 of an integer with MSB set

unsigned int v; // 32-bit input word
unsigned int r = 0; // result goes here
while (v >>= 1)
{
  r++;
}


Explanation: The log base 2 of an integer is the same as the position of the highest bit set (or most significant bit set, MSB). e.g. log2(16) => 0001_0000 => highest SET bit is 4th (if you count LSB as 0) => 4 (the answer).


* Finding the log base 2 of an N-bit integer

unsigned int v;  // 32-bit value to find the log2 of
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;

register unsigned int r = 0; // result
for (i = 4; i >= 0; i--)
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  }
}


Explanation: The constants defined in the array are actually the expected result of log(num) ie. 2, 4, 8 and so on. The array lists down all the possible values that can represent 2^n for a 32-bit integer. At every step, we are trying to figure out the highest possible value for the operation. If it matches, we store the result in 'r' and then shift it accordingly and wait for the next match if any. If any other match is there, we would OR it with the already computed result 'r'.


* Round UP to the next power of 2

unsigned int v;

v--;
v |= v >> 1;  //take care of 2-bit word
v |= v >> 2;  //take care of 4-bit word
v |= v >> 4;  //take care of 8-bit word
v |= v >> 8;  //take care of 16-bit word
v |= v >> 16; //take care of 32-bit word
v++;


Explanation: Effectively, we have to find the SET bit at the left-most position OR the highest numbered bit which is SET. Now, we need to fill all the bits that are there at the left-hand side of this SET bit with '1'. Next, if we add one to this newly generated number, we are left with a number that is power of 2 and greater then the given number. The expression "v--" is there to handle situation where we pass a number that is already power of 2 to this function.

e.g. Let us take 17 as an example whose binary representation is 0001_0001.

To get the next highest power of 2 from this number we have to get to 32 ie. 0010_0000
The approach taken in the code above is to mark all the bits in 0001_0001 from bit-position 4 (counting the left-most bit as 0) to bit-position 0 as '1'.
We achieve this by the sequential SHIFT and OR operations and finally we would have something like 0001_1111.
Lastly, adding 1 to this we get 0010_0000 which is 32, the next highest power of 2.

Note: The above logic can easily be extended to N-bit words. We will have to provide the shift condition till N/2 bits.

With this I am closing this article, which relied mostly on the bitwise operations to accomplish few complex operations. The reference for this article can be found at Bit Twiddling Hacks. I have a follow-up article Bitwise Operators - Interview questions for these tips and tricks which directly find application in few of the Interview Questions.

-Pankaj
Happy Programming

comments powered by Disqus