First Let us Understand all Bitwise Operators one by one.
1. BITWISE AND (&) Operator
This bitwise & operator takes two bits/numbers as operands and return 1 if both bits are 1 otherwise return 0.
Ex: 1&1 = 1, 1&0 = 0, 0&0 = 0.
2. BITWISE OR(|) Operator
This bitwise | operator takes two bits or numbers as operands and return 0 if both bits are 0 otherwise return 1.
Ex: 1|1 = 1, 1|0 = 1, 0|0 = 0.
3. BITWISE XOR(^) Operator
This bitwise ^ operator takes two bits or numbers as operands and return 0 if both bits are the same otherwise 1.
Ex: 1 ^ 1 = 0, 1 ^ 0 =1.
Two Most Important Property of Bitwise XOR operator is:
I. a^a = 0 (XOR of two same number is 0)
II. 0^a = a (XOR of a any number with 0 is number itself)
3. BITWISE left Shift(<<) Operator
This Bitwise Operator takes two numbers as operands and shifts the first number’s bits towards left by the given number (second number ) of time. Its expression is a<<b.
Ex: 1<<1 = 2.
Here a= 1,b=1. Binary of 1 = 01, shifting its bits towards left by 1 (b), we get 10 which is equal to 2. So 1<<1 = 2.
Some Other useful observation is here that left shift (a,b) is equal to a*pow(2,b).
a<<b = a*pow(2,b). In above example, 1<<1 = 1*pow(2,1) = 1*2 = 2.
4. BITWISE Right Shift(>>) Operator
This Bitwise Operator takes two numbers as operands and shifts the first number’s bits towards Right by the given number (second number ) of time. Its expression is a>>b.
Ex: 4>>1 = 2.
a = 4, b = 1. Binary of a = 100, shifting right by 1 time, we get 010 = 2. So 4>>1 = 2.
Some Other useful observation is here that left shift (a,b) is equal to a/pow(2,b).
a>>b = a/pow(2,b). In above example, 4>>1 = 4/pow(2,1) = 4/2 = 2.
5. BITWISE NOT(~) Operator
This Bitwise Operator is a Unary Operator means it takes only one number and inverts the bits of that number.
Ex: ~4 = 3.
As we know binary(4) = 100, by using not operator, 1 -> 0 and 0->1. So ~100 = 011 which is 3.
Now let's do some Basic Questions based on these concepts.
1. Multiplication of a number by a power of 2
Suppose we have to multiply a number by a power of 2, instead of using the multiplication operator and power function, we can use the bitwise left shift operator here. As I have already mentioned above that a<<b = a*pow(2,b).
So Code is just ans = a<<b.
2. Division of a number by a power of 2
Suppose we have to Divide a number by a power of 2, instead of using the Divide operator and power function, we can use the bitwise Right shift operator here. As I have already mentioned above that a>>b = a/pow(2,b).
So Code is just ans = a>>b.
3. Swapping of Two Numbers
In this Question, we have to swap elements of two variables. Like a = 7, b = 8 after swapping a = 8, b = 7.
What our General Approach is to store variable “a” into another variable like temp, and put value of “b” in “a” and again put value temp in “b”.
int temp = a;
a = b;
b = a;
But we can use Bitwise XOR here. The code is shown below:
int temp = a^b;
a = temp^a;
b = temp^b;
How the above code is working. As Earlier mentioned Bitwise XOR property numbers 1 & 2 are working here.
In First line temp = a^b. we are storing xor of a and b.
In the second line what we are doing a = temp^a ( a^b^a), So
a^a = 0 (Property number 1), and 0^b which is b, it is assigned to a.
In the third line what we are doing b= temp^b ( a^b^b), So
b^b = 0 (Property number 1), and 0^a which is a, is assigned to b.
4. To check if a given number is even or odd
Suppose we are given a situation that we have to check that the given number is odd or even.
So What we do?
We quickly use the modulo (%) operator to check it, but what if are said not to use the modulo operator. In that situation, we can use the Bitwise AND(&) operator.
How does it work? we use the below expression.
Every number is odd if it’s left most bit is 1, otherwise even.
cout<<”Number is Odd”;
cout<<”Number is Even”;
num = 4 (100).
100 & 001 = 0. (Even Number)
num = 7 (111).
111 & 001 = 1 (Odd Number)
5. To set an ith bit of a given number
Suppose we are given a number 5 (101). we have to set the second bit of number and have to get the result as 111 = 7.
So Approach here would be to use a combination of left-shift operator and or Operator.
Firstly we will have to left shift 1 by bit which we have to set.
Means if we are given num = 5, bit = 2.
So temp = 1<<(bit-1)
In the Second Step, we will do or of this temp with the given number.
num = num | temp
So Programme would be as follows:
int num = 5;
int bit = 2;
int temp = 1<<(bit-1);
num = num | temp;
The above code’s explanation can be seen in the below image.
As Show in the above picture, we have successfully set the 2-bit number.
Now there are plenty of other questions based on the above concepts. Like I am writing some more basic questions which you can try yourself.
6. To turn off the ith bit of a number.
7. To Check if a number is power of two or not.
8. To Find min/max of two numbers.
9. to count all set bit in a given number.
10. to flip ith bit of number. (means if it 0 then convert it to 1, if it is 1 then to 0).
I am attaching some more links to questions which you can try.
- Majority Element
- Reverse Bits
- Missing Number
- Power of 4
- Find Two Missing Numbers
- Sum Of Two Integers
- Find the repeating and the missing
If You want to learn more about bit manipulation, you can check out the below resource.
Thank You very much 🙏.