1. Checking whether K-th bit is set or not
Let us assume that given number is n. Then for checking the K-th bit, use the following expression: n & (1 << K -1).
If the expression is true then we can say the k-th bit is set(that means , set to 1)
Example: n = 01001011 K = 4
n & (1 << k-1) 00001000
2. Setting K-th bit
For a given number n , to set the K-th, use the following expression: n | 1 << (K-1)
Example: n = 01001011 K = 3
n | (1 << K-1) 01001111
3. Clearing K-th bit
To clear K-th bit of a given number n, use the following expression: n & ~ (1 << K -1)
Example: n = 01001011 K = 4
n & ~(1 << K – 1) 01000011
4. Toggling K-th bit
For a given number n, for toggling the K-th bit, use the expression: n ^ (1 << K -1)
Example: n = 01001011 K = 3
1 << (K – 1) 00000100
n ^ (1 << K -1) 01001111
5. Checking whether number is Power of 2 or not
Given number n, to check whether the number is 2 raised to power n form or not, use the following expression: if (n & n-1 == 0)
Example: n = 01001011
n – 1 = 01001010
n & n-1 = 01001010
if(n & n-1 == 0) 0
6. Multiplying number by power of 2
For a given number n, to multiply the number with 2 raised to power K, use the following expression: n<<K.
Example: n = 01001011 K = 2
n << K 00101100
7. Dividing number by power of 2
For a given number n, to divide the number with 2 raised to power K, use the following expression: n>>k
Example: n = 01001011 K = 2
n >> K 00010010
8. Finding Modulo of a Given Number
For a given number n, to find the %8, use the following expression: n & 0x7. Similarly, to find %32, use the following expression: n & 0x1F
Important note: As stated above, we can write for any modulo value.
9. Reversing the Binary Number
For a given number n, to reverse the bits, use the following code
unsigned int n, reversed = n;
int s = sizeof(n);
for(; n; n>>1){
reversed <<= 1;
reversed |= n &1;
s–;
}
reversed <<= s;
10. Average without Division
Is there a bit-twiddling algorithm to replace mid = (low + high) / 2 (used in Binary Search and Merge Sort) with something much faster?
Use mid = (low + high) >> 1, But, by using this there may be the possibility o f integer overflow, to overcame this issue , use the following expression: low + ((high – low) >>1)
Quote of the day: Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.
― Rick Cook, The Wizardry Compiled