Bit level
hacks enable you to manipulate integers in intelligent way. Instead of
performing some operations by looping over individual bits, you can get the
result by performing simple bit level operations.
Java
provides rice bit wise operators, to perform inversion, left shift, right
shift, bitwise and, o and Ex-OR operations.
|
Operator
|
Description
|
|
~
|
Inverts a bit pattern
|
|
<<
|
Perform Left shift
|
|
>>
|
Perform Right Shift
|
|
>>>
|
Perform unsigned right shift
|
|
&
|
Bit wise AND
|
|
|
|
Bit wise OR
|
|
^
|
Bit wise Exclusive OR
|
For more
information on Bitwise operators go through following link.
Hack 1: Swap two numbers
Usually, you
swap two numbers using a temporary variable like below.
temp = a
a = b
b = c
We can
achieve the same functionality using X-OR (^) operator.
a = a ^ b;
b = a ^ b;
a = a ^ b;
Hack 2: Check whether a number is power of 2
If n is a power
of 2, then n&(n-1) is equal to 0.
|
Number
|
Binary
|
Number-1
|
Binary
|
|
2
|
00000010
|
1
|
00000001
|
|
4
|
00000100
|
3
|
00000011
|
|
8
|
00001000
|
7
|
00000111
|
|
16
|
00010000
|
15
|
00001111
|
|
32
|
00100000
|
31
|
00011111
|
Observe
above table, you can understand the logic easily.
Hack 3: Count all set bits in an integer
Do bit wise and
operation of num with 1. If result is 1, increment the counter. Right shift
number by 1. Repeat this procedure until num > 0.
int count =
0;
while (num
> 0) {
count = count + (num & 1);
num = num >> 1;
}
Hack 4: Count all unset bits in an integer
Logic is
just opposite to previous logic.
while (num
> 0) {
if ((num & 1) == 0)
count = count + 1;
num = num >> 1;
System.out.println(num);
}
Hack 5: Check whether nth bit is set or not
Shift 1 to n
times left, and bitwise and with n, if result is 1, then nth bit set, else not.
public
static boolean isNthBitSet(int num, int n){
int temp = 1 << n;
return ((num & temp) != 0);
}
Hack 6: Check number is even or odd without
division
If number is
even, then last bit is 0, else 1.
public
static boolean isEven(int num) {
return ((num & 1) == 0);
}
Hack 7: Set nth bit of a number
Left Shift
1, n times and perform bitwise or operation.
public
static int setNthBit(int num, int nthBit){
num = (num | (1 << nthBit));
return num;
}
Hack 8: Toggle nth bit
If nth bit of a number is 0, then make it as 1, else 0.
public
static int toggleNthBit(int num, int n) {
num = num ^ (1 << n);
return num;
}
Hack 9: Isolate right most set bit
‘x = x &
(-x)’ isolate right most set bit.
100 000001100100
-100 111110011100
-------------------------------
100 &
-100 000000000100
-------------------------------
Following is
the complete java program for above hacks.
public class BitUtil { public static boolean isPowerOfTwo(int n) { return ((n & (n - 1)) == 0); } public static int getNumSetBits(int num) { int count = 0; while (num > 0) { count = count + (num & 1); num = num >> 1; } return count; } public static int getNumUnsetBits(int num) { int count = 0; if (num == 0) return 1; while (num > 0) { if ((num & 1) == 0) count = count + 1; num = num >> 1; } return count; } public static boolean isNthBitSet(int num, int n) { int temp = 1 << n; return ((num & temp) != 0); } public static boolean isEven(int num) { return ((num & 1) == 0); } public static int setNthBit(int num, int nthBit) { num = (num | (1 << nthBit)); return num; } public static int toggleNthBit(int num, int n) { num = num ^ (1 << n); return num; } public static int isolateRightMostNthBit(int num) { num = num & (-num); return num; } }
Following is
the junit test case for above program.
import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import org.junit.Test; public class BitUtilTest { @Test public void testIsPowerOfTwo() { assertTrue(BitUtil.isPowerOfTwo(2)); assertTrue(BitUtil.isPowerOfTwo(4)); assertTrue(BitUtil.isPowerOfTwo(8)); assertTrue(BitUtil.isPowerOfTwo(16)); assertTrue(BitUtil.isPowerOfTwo(32)); assertTrue(BitUtil.isPowerOfTwo(64)); assertTrue(BitUtil.isPowerOfTwo(1)); assertFalse(BitUtil.isPowerOfTwo(3)); assertFalse(BitUtil.isPowerOfTwo(5)); assertFalse(BitUtil.isPowerOfTwo(6)); assertFalse(BitUtil.isPowerOfTwo(7)); } @Test public void testGetNumSetBits() { assertEquals(BitUtil.getNumSetBits(0), 0); assertEquals(BitUtil.getNumSetBits(1), 1); assertEquals(BitUtil.getNumSetBits(2), 1); assertEquals(BitUtil.getNumSetBits(3), 2); assertEquals(BitUtil.getNumSetBits(4), 1); assertEquals(BitUtil.getNumSetBits(5), 2); assertEquals(BitUtil.getNumSetBits(6), 2); assertEquals(BitUtil.getNumSetBits(7), 3); assertEquals(BitUtil.getNumSetBits(8), 1); } @Test public void testGetNumUnsetBits() { assertEquals(BitUtil.getNumUnsetBits(0), 1); assertEquals(BitUtil.getNumUnsetBits(1), 0); assertEquals(BitUtil.getNumUnsetBits(2), 1); assertEquals(BitUtil.getNumUnsetBits(3), 0); assertEquals(BitUtil.getNumUnsetBits(4), 2); assertEquals(BitUtil.getNumUnsetBits(5), 1); assertEquals(BitUtil.getNumUnsetBits(6), 1); assertEquals(BitUtil.getNumUnsetBits(7), 0); assertEquals(BitUtil.getNumUnsetBits(8), 3); } @Test public void testIsNthBitSet() { System.out.println(165 & 4); assertTrue(BitUtil.isNthBitSet(165, 0)); assertTrue(BitUtil.isNthBitSet(165, 2)); assertTrue(BitUtil.isNthBitSet(165, 5)); assertTrue(BitUtil.isNthBitSet(165, 7)); assertFalse(BitUtil.isNthBitSet(165, 1)); assertFalse(BitUtil.isNthBitSet(165, 3)); assertFalse(BitUtil.isNthBitSet(165, 4)); assertFalse(BitUtil.isNthBitSet(165, 6)); assertFalse(BitUtil.isNthBitSet(165, 8)); assertFalse(BitUtil.isNthBitSet(165, 9)); assertFalse(BitUtil.isNthBitSet(165, 10)); } @Test public void testIsEven() { assertTrue(BitUtil.isEven(0)); assertTrue(BitUtil.isEven(2)); assertTrue(BitUtil.isEven(4)); assertFalse(BitUtil.isEven(1)); assertFalse(BitUtil.isEven(3)); assertFalse(BitUtil.isEven(5)); } @Test public void testSetNthBit() { assertEquals(BitUtil.setNthBit(42, 0), 43); assertEquals(BitUtil.setNthBit(43, 2), 47); assertEquals(BitUtil.setNthBit(47, 4), 63); } @Test public void testToggleNthBit() { assertEquals(BitUtil.toggleNthBit(171, 0), 170); assertEquals(BitUtil.toggleNthBit(170, 6), 234); assertEquals(BitUtil.toggleNthBit(234, 3), 226); assertEquals(BitUtil.toggleNthBit(226, 7), 98); } @Test public void testIsolateNthBit() { assertEquals(BitUtil.isolateRightMostNthBit(100), 4); assertEquals(BitUtil.isolateRightMostNthBit(123), 1); assertEquals(BitUtil.isolateRightMostNthBit(204), 4); assertEquals(BitUtil.isolateRightMostNthBit(256), 256); } }
If you are interested
in learning more bit level hacks, go through following link.
No comments:
Post a Comment