WIKI
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed ups, as bit manipulations are processed in parallel, but the code can become more difficult to write and maintain.
Representation of a decimal number (base 10) into binary:
Binary representation of a number contains only 0 and 1. One easy way to find the binary representation of number can be keep dividing the number by 2, and keep track of the remainder, and at end, when the number becomes 0 (after multiple division), we stop and write the remainders in reverse order.
Example, if we have 6.
We divide it by 2, the number becomes 3, and we get the remainder 0, we again divide by 2, the number becomes 1, and we get the remainder 1, we further divide by 2, the number becomes 0, and we get the remainder 1. Now the number becomes 0, we stop.
The remainders are 0, 1, 1. We write this in reverse order: 110.
Both of representation denotes the same number, the only difference is of its, base. As an example consider a number 125 in decimal (i.e base 10).
125= 1*100 + 2*10 + 5*1 = 1*10^2 + 2*10^1 + 5*10^0.
The same number represented in binary is (1111101) base 2.
1111101=1*64+1*32+1*16+1*8+1*4+0*2+1*1=
=1*2^6+1*2^5+1*2^4+1*2^3+1*2^2+0*2^1+1*2^0
NOTE: In binary a negative number is represented as 2’s complement of its positive. Example: -2056 is stored as 2’s complement of 2056.
For better knowledge of 1’s and 2’s complement, refer to this : https://www.geeksforgeeks.org/1s-2s-complement-binary-number/
Basic bitwise operators used in bit manipulation:
AND(&): Bitwise “and” of two numbers (say A and B), is intersection of bits present at a particular position, i.e. if both the bit at a position(say ith position) has 1 in it, then the resultant number also will have 1 at the that (ith)position, otherwise 0.
& operator works like set intersectioin.
Example: 5= 101(base 2), and 7= 111(base 2)
(101) & (110)= 100 (So bitwise and of 5 and 6 will 4 (100 in binary)).
OR(|): Bitwise “or” of two numbers (say A and B), is union of bits present at a particular position, i.e. if any of the bit at a position(say ith position) has 1 in it, then the resultant number also will have 1 at the that (ith)position, otherwise 0.
|operator works like set union.
Example: 4= 100 (base 2) , and 2= 010 (base 2).
(100) & (010)= (110) (So bitwise or of 4 and 2 will be 6 (110 in binary)).
NOT(~): This operator is used to flip the bits at all the position in a number. It is basically 1’s compliment of a number.
Example: ~5=~(101) = 010 = 2 (in decimal), (for simplicity purpose I have written the answer of ~5=2, considering only 3 bits, but in reality, integers contains 32 bits, and binary notation of 5 is 00000000000000000000000000000101, so not of 5 (~5) will be 11111111111111111111111111111010 = -6 (notice that the first bit is a sign bit, 0 represents positive, and 1 represents negative).
XOR(^): Bitwise XOR of two numbers kinda searches for different bits, if bits at a particular position in two numbers are different, then resultant number will have set (1) at that position, otherwise 0.
Example: (1001) ^ (0101) = 1100
Bitwise XOR of a number with itself is 0, and Bitwise XOR of a number with 0 is the number itself, i.e. A^A=0, and A^0=A.
Bitwise XOR of two numbers can be expressed in the form of &(and), ~(not), |(or).
A^B= (A&(~B))|((~A)&(B)).
NOTE: Bitwise XOR is commutative and associative, i.e. A^B=B^A , and (A^B)^C= A^(B^C).
LEFT SHIFT(<<): This operator is used to shift the each bit of a number towards the left, and append 0 at the end (Right).
Example: (5<<2 = 101 << 2 =10100=20). A<<B is basically A*(2^B).
RIGHT SHIFT(>>): This operator is used to shift the each bit of a number towards right, the rightmost bits are destroyed in this process. Example:(10>>2 = 1010 >> 2 =10=2). A<<B is basically A/(2^B) (floor division).
To summarize AND, OR, XOR and NOT:
NOW LETS DISCUSS SOME ALGORITHMS AND TRICKS:
How to remove the least significant (rightmost) bit?
Least significant bit is the rightmost bit, which is a set in the binary representation of a number. Example, for 10010 , the least significant bit would be 10010 (which is bold).
Now how do I remove it?,
One basic way can be, keep checking for the first bit from right towards the left, until we find the first set bit (i.e 1), and remove it. Complexity of this would be O(logn), but why do that, when it can be done in O(1). A simple way to do it is, by taking bitwise “and” of that number(n) with (n-1), i.e
n&(n-1) , it will have its LSB removed.
How does this work?, For that we need to know the relation between
n and n-1, n-1 has all the bits same as n, but all the bits at the right side of (LSB) are flipped (including the LSB). Example , if n is 100001000 , then n-1 would be 100000111.
So, n&(n-1) can help us remove the LSB.
Also we can get the least significant bit, by n&(-n) , or n^(n&(n-1)),
or n - n&(n-1).
How do I check whether a number is a perfect power of 2 or not?
One basic algorithm can be keep dividing the number (say n) by 2, until n becomes odd, if we end up with n=1, this would mean it is a perfect power of 2, otherwise not.
void check(int n){
while(n%2==0){
n=n/2;
}
if(n==1) print (yes) else (no).
}
}
But, what if I say this is time consuming, and there exists a better way to check?
We know that a perfect power of 2 has all the bits equal to zero, except for the leftmost one, like 4=100 (in binary), 8=1000 (in binary), 64=10000 (in binary). We already know a way to Remove the LSB, in case of perfect power of 2, as there is a single bit, we can just remove it, an check that the resultant number is 0 or not.
void check(int n){
if(( n&(n-1) )==0)
print (yes);
else print (no);
}
How to get the bit of a number at a particular position?
The bit of a number(say n) at a position(say k) =( n&(1<<k) ) !=0
Example: Suppose n=100011010, and we need bit at position 4, then 1<<4, will be 10000, so n& (1<<k) = 100011010 & (10000)= 10000 !=0 ,so it has 1 at 4th position.
At position 2, n&(1<<2)=0, so it has 0 at 2nd position.
Note: The bit position here, start from 0.
How to get the next power of 2 (greater than a number)?
We can get the next power of 2 of a number (say n) by simply finding the most significant bit, suppose it is at position k, the next power of 2 of that number would be 1<<(k+1). Or we can just find the MSB, and multiply it by 2.
(We can find the MSB, by removing LSB one by one, the last bit removed will be our MSB. Complexity : O(number of set bits).)
How to count the number of set bits in a number?
We have seen above, how to remove the LSB, we can keep removing the LSB, until the number becomes zero, while doing so, we will keep a count on number of bits removed, the final count will be the number of set bits.
Algorithm:
int c=0;
while(n>0){
n=n&(n-1);
c++;
}
cout<<c<<endl;
Complexity : O(number of set bits).
SUBSET GENERATION
Bit Manipulation can help us iterate over or generate all the possible (2^n) subset of a given array (of size n). Basically, we use the idea that we can represent a subset of the array as 0’s and 1’s , there will be total n bits, ‘1’ at the ith bit indicates that the ith element is chosen for the current subset, and 0 indicates that it is not chosen, like if there are 3 (n=3) elements , 110 would indicate zeroth index element is not chosen (0), 1st index element is chosen (1), and 2nd element is also chosen(1), we do the same for all other 3 bit binary numbers too like 101,001,111,etc.
Implementation:
int ar[]={1,2,3};
int n=sizeof of ar/ sizeof(ar[0]); //=3
for(int i = 0;i < (1 << n);i++){Complexity : O(n * 2^n)
for(int j = 0;j < n;++j){
if(i & (1 << j))
cout << ar[j] << ' ';
}
cout << endl;
}
Refer to this for better understanding: https://www.geeksforgeeks.org/power-set/.
For more algorithms and tricks you can visit these pages:
https://www.geeksforgeeks.org/bitwise-hacks-for-competitive-programming/
https://www.geeksforgeeks.org/bit-tricks-competitive-programming/
https://www.geeksforgeeks.org/calculate-xor-1-n/
https://www.geeksforgeeks.org/sum-bitwise-possible-subsets-given-set/
Thanks for Reading
If anything is not clear, please let me know in the comments. :)
About Me:
I am Abhinav, Member Competitive Coding Wing, Geekhaven IIIT Allahabad
