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.
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
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
* Swapping Individual bits with XOR operator
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
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
* Finding the log base 2 of an integer with MSB set
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
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
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.