A gist of vital questions/concepts related to Bit wise manipulation :
- Turn off the first set bit(1) from right of a number N.
- Application: Fast Bit Count
- Application: Single Number III
- Odd/Even test
- Get Kth bit of N / Checking if the Kth bit is set or unset: { bool bit_K = num & (1 << K); }
- Set Kth bit of N: {num |= (1 << pos);}
- Unset Kth bit of N: {num &= (~(1 << pos));}
- Toggling a bit at Kth position: {num ^= (1 << pos);}
- Convert an integer (Decimal) into a bitwise (string)
- Difference between '&' and '&&' or for that matter '|' and '||'
- Range of (a &b) , range of(a|b), range of (a^b)
REMEBER the tools at our disposal are :
- SHIFT operators : >>(right shift, div by 2) and <<(left shift, mul by 2)
- BOOL operators : ^ (XOR), &(and) , ~(NOT)
- Arithmetic operators like +, - , /, * are not used.
int int_var;
cout<<sizeof(int_var)<<endl; // returns number of bytes
output is 4
this means an integer has 32 bits or 32 placeholders to hold either 1 or 0.
1.Turn off the first set bit(1) of a number N.
Two ways :
A.
- get ~N
- add +1
- multiply this with N... log of this result will show the position of rightmost set bit
B
- get (N-1)
- flip the bit ~(N-1)
- multiply this with N... log of this result will show the position of rightmost set bit
```Java
count=0;
while(n>0) {
n= n &(n-1);
count++;
}
return count;
```
2. Check whether n is even or odd: The naive approach to check a number is even or odd is to take the modulo with 2. The better and efficient method is to take the (n&1). If the last bit is set n is odd, else even.
3. If you want the k-th bit of n, then do :
(n & ( 1 << k )) >> k
(n >> k) & 1 is equally valid
5.
A&B =[0,min(A,B)] A^B =[0,A+B] A|B =[max(A,B),A+B]
TIPS :
- mask = 0xffffffff then ~(a^mask)
References :
