December 31, 2018 • ☕️☕️ 8 min read
Bit operations operate on the individual bits of the bit patterns and we perform such operations using bitwise operators. Data in memory (RAM) is organized as a sequence of bytes. Each byte is a group of eight consecutive bits. We use bitwise operators whenever we need to manipulate bits directly. Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level. Bitwise operators are language agnostic and getting hold of them can help in doing some things easily and most importantly in a shorter and sharper way.
A | !A |
---|---|
0 | 1 |
1 | 0 |
A | B | A&B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
A | B | A|B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
A | B | A^B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
How it works
Using this operator is equivalent to multiplying the bit pattern with 2 ^{n} ( if we are shifting n bits ) i.e.
419 in binary 0000111110110011 << 1 = 838 (0001111101100110)
How it works
Using this operator is equivalent to dividing the bit pattern by 2 ^{n} ( if we are shifting n bits ) i.e.
220 in binary 11011100 >> 1 = 110 (1101110)
Difference between a binary number n and n-1 is : All the bits on the right of the rightmost 1 are flipped including the rightmost 1(which will get zero). Some examples :
If 12 (1100) then -12 in binary representation will be 2’s complement of (1100) i.e 1’s complement(1100) + 1 = 0100, We traverse the one’s complement starting from right most bit towards left , and look for 0. We flip all 1’s to 0 until we find a 0. Finally, we flip the found 0
Two unique properties of XOR
n ^ n = 0
n ^ 0 = n
Fenwick Tree or Binary Indexed tree
Helps in calculating prefix sums in an array efficiently. For example, an array is [100, -100, -1, 1, 12] the length 3 prefix [100, -100, -1] with sum 100 - 100 + -1 = -1). If you are into competitve programming or have given long contest on codechef then 4/5 th question generally requires you to do things like
Prerequisite for fenwick trees : How to get last set bit ? For example For 1010, you should perform some operations to give 0010 as the output where 1 is last set bit in 1010. For this solution is just this simple equation x ^ (x & (x - 1)) (See how sharp bitwise solutions are!)..Lets make truth table of this to get how this equation works:
x(8) | x-1(7) | x & x-1 = mans | x ^ mans |
---|---|---|---|
1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 last set bit |
0 | 1 | 0 | 0 |
0 | 1 | 0 | 0 |
(x & (x - 1)) this equation actually came from our observation defined in above section. XOR(^) helps in removing 1 which exists in both results so we get last set bit!
We can use above equation and fenwick tree to maintain a partial sum tree(array to be precise). Denote BIT[] as fenwick tree and any index we can store sum of some numbers of any given array.
For every index i in the BIT[] array we store the cumulative sum from the index i to i - (1<<r) + 1 (both inclusive), where r represents the last set bit in the index i. So in mathematical equation this means
{
a[1] + ... + a[x], if x is power of 2
BIT[x] =
a[x], if x is odd
}
How (x & (x - 1)) equation played a role in above fenwick equation?
If we see numbers 2,4,8.. in binary form 0010,0100,1000..so on then we always get a last set bit with no other set bits(1 bit) in the representation so if r represents set bit position ex: For 4 (0100) set bit position is 3(0 for 0 ,0 for 1, 1 for 2 if read from right -> left) so
if i = 4 then range [i to i - (1<<r) + 1] represents 4 to 4 - (2 ^{r} = 2 ^{2} = 4) + 1 = [4,1] i.e index 4 should contain sum of first 4 elements.
if i = 16 then 16(10000)-(2 ^{r} = 2 ^{4} = 16 - 16 + 1 = 1) i.e index 16 should contain sum of first 16 elements.
if i = 3 then 3(0011) - (2 ^{r} = 2 ^{0} = 1 = 3-1+1) = [3,3] i.e index 3 will contain sum of only number at index 3 or just value at index 3.
Brian Kernighan’s Algorithm
Again using our observation about x & x-1 and use it to give rightmost set bit so if we do it again and again till we get 0 then we will get no of set bits it originally had! This is what Brian Kernighan’s algo does.
while (n) {
n = n & (n-1);
count++;
}
Get non-repeated value from array of duplicates
Example array [1, 33, 54, 4, 7, 8, 8901, 33, 1, 4, 54, 8, 8901] and answer will be 7 if we use XOR operation by using its property of m ^ m = 0 && m ^ 0 = m.
Manually lets XOR one by one and also take XOR of 7 at last so that before that we should have something like 0000 then only this property 0^7 would give us the answer.
1 ^ 33
1 00000001
^ 33 00100001
= 32 00100000
32 00100000
^ 54 00110110
= 22 00010110
22 ^ 4
22 00010110
^ 4 00000100
= 18 00010010
18 ^ 8
18 00010010
^ 8 00001000
= 26 00011010
26 ^ 8901
26 0000000000011010
^ 8901 0010001011000101
= 8927 0010001011011111
8927 ^ 33
8927 0010001011011111
^ 33 0000000000100001
= 8958 0010001011111110
8958 ^ 1
8958 0010001011111110
^ 1 0000000000000001
= 8959 0010001011111111
8959 ^ 4
8959 0010001011111111
^ 4 0000000000000100
= 8955 0010001011111011
8955 ^ 54
8955 0010001011111011
^ 54 0000000000110110
= 8909 0010001011001101
8909 ^ 8
8909 0010001011001101
^ 8 0000000000001000
= 8901 0010001011000101
8901 ^ 8901
8901 0010001011000101
^ 8901 0010001011000101
= 0 0000000000000000 (Here we go!)
0 ^ 7
0 00000000
^ 7 00000111
= 7 00000111 Finally :)
Checking if given 32 bit integer is power of 2
All the power of 2 have only single bit set and using our x and x-1 observation if we perform (x & x-1) then if x is power of 2 this will give 0 otherwise 1. So !(x & x-1) will give whether the number is power of 2. If case of x = 0 we dont wish to do x-1 so final equation is
(x && !(x & x-1))
Quick conditional assignment
if (x == a)
x = b;
if (x == b)
x = a;
Better way
x = a ^ b ^ x
If a number is even or odd
if x & 1
fmt.Println("ODD")
else
fmt.Println("EVEN")
Swap numbers without extra variables
i = i ^ k; // i has both i and k let it be I
k = i ^ k; // remove k from I so k = i
i = i ^ k; // remove k (which is now i) from I so i = k
I also wanted to explain how bitwise operators are related to set theory but for now keeping this post short and sweet we will be covering this topic into a separate article along with some interesting problems on algorithms, data structures and tricks explained above.
Thanks! 🙌
The fault in my articles, they don't close themselves.