Bit Hacks
Bitwise operators in Java.
& - bitwise and
| - bitwise or
^ - bitwise xor
~ - bitwise not
<< - bitwise shift left
>> - bitwise shift right
1. Check if number is power of 2.
public static boolean isPowerOf2(int n){
return n != 0 && ((n & (n-1))== 0);
}
isPowerOf2 5 -- false
isPowerOf2 8 -- true
2. Count number of set bits.
public static int noOfSetBits(int n){
int count = 0;
while(n!=0){
count++;
n = n & n-1;
}
return count;
}
noOfSetBits 5 -- 2
noOfSetBits 8 -- 1
3. Check if number is even or odd.
public static boolean isEven(int n){
return (n&1) == 0;
}
isEven 5 -- false
isEven 8 -- true
4. Check if Kth bit is set.
public static boolean isKSet(int n, int k){
return (n & (1 << k-1)) != 0;
}
isKSet 50(110010) 5 -- true
isKSet 133(10000101) 4 -- false
5. Set Kth bit
public static int setKthBit(int n, int k){
return n | (1<<k-1);
}
setKthBit 50(110010) 5 -- 50 (110010)
setKthBit 133(10000101) 4 -- 141 (10001101)
6. Unset Kth bit
public static int unsetKthBit(int n, int k){
return n & (n ^ (1 << k-1));
}
unsetKthBit 50(110010) 5 -- 34 (100010)
unsetKthBit 133(10000101) 4 -- 133 (10000101)
public static int unsetKthBit2(int n, int k){
return n & ~(1<<k-1);
}
unsetKthBit2 50(110010) 5 -- 34 (100010)
unsetKthBit2 133(10000101) 4 -- 133 (10000101)
7. Toggle Kth bit
public static int toggleKthBit(int n, int k){
return n ^ (1 << k-1);
}
toggleKthBit 50(110010) 5 -- 34 (100010)
toggleKthBit 133(10000101) 4 -- 141 (10001101)
8. Isolate rightmost set bit
public static int isolateRightMostOne(int n){
return ~(n-1) & n;
}
isolateRightMostOne 50(110010) -- 2 (10)
isolateRightMostOne 133(10000101) -- 1 (1)
9. Isolate rightmost unset bit
// Eg: 10101011 ---> 000000100
public static int isolateRightMostZero(int n){
return (n+1) & ~n;
}
isolateRightMostZero 50(110010) -- 1 (1)
isolateRightMostZero 133(10000101) -- 2 (10)
In two's complement system , -x = ~x + 1
Further read
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know