Bit Manipulation Concepts for Competitive Programming
As we all know to get placed in MNC the most basic requirement is problem solving. Many MNCs nowadays don't take any interest in what new technologies you know , but it gives you an extra edge while giving interviews in big companies. The main focus of all these is fundamentals of programming like data structures , algorithms etc. So we as a student take it lightly and focus more and more on learning the new technologies rather than to give importance on fundamentals and hence we are not able to solve the basic questions from algorithms and hence rejected straight away by the company.
So in this blog I would focus on the topic which helps to solve the different problems easily in lower time complexity rather than solve directly by the naive approach like loops.
1. Some Basic Concepts of Bits
a) Truth table for AND logic :
| A | B | Result |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
b) Truth table for OR logic :
| A | B | Result |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
c) Truth table for XOR logic:
| A | B | Result |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
d) Right Shift(>>):
- This operator is used to shift the bits to the right side and append 0 at the last left position.
For eg : 0101 >> 1 => 0010, it would shift to the right side by 1.
e) Left Shift (<<) :
- This operator is used to shift the bits to the left side and append 0 at the last right position.
For eg : 0101 << 1 => 1010, it would shift to the left side by 1.
2. Some require concepts to solve problems
a) How to set any particular bit of an integer using bit manipulation:
To solve this problem we have to get an idea what the question is trying to say.
For eg : integer is 5 , its Binary equivalent is 0101
Let's say we want to set bit number 1 from the right side.
So after setting the bit we would get Binary equivalent as : 0111
How to solve it ?
Syntax : Firstly it would have taken the concept of the shifting which we had discussed above.
-
Do left shift the number ‘1’ Upto the given position where to set it.Let take it as ‘pos’.
After Step1 : step1 = 1 << pos; -
Now Do the OR operation between the result of step1 and the Number itself.
After Step2 : result = (n|step1);
In Proper syntax:
b) How to clear any particular bit of an integer using bit manipulation?
To solve this problem we have to get an idea what the question is trying to say.
For eg : integer is 5 , its Binary equivalent is 0101
Let's say we want to clear bit number 2 from the right side.
So after clearing the bit we would get Binary equivalent as : 0001
How to solve it??
Syntax : Firstly it would have taken the concept of the shifting which we had discussed above.
-
Do left shift the number ‘1’ Upto the given position where to set it.Let take it as ‘pos’.
After Step1 : step1 = 1 << pos; - After step1 , complement the result obtained in step1 to set all other bits in rather than ith bit in the result.
After Step2 : step2 = ~(step1); -
Now Do the AND operation between the result of step2 and the Number itself.
After Step3 : result = (n|step2);
In Proper syntax:
c) How to get any ith bit of an integer using bit manipulation?
To solve this problem we have to get an idea what the question is trying to say.
For eg : integer is 5 , its Binary equivalent is 0101
Let's say we want to get bit number 2 from the right side.
So the result we want is either ‘0’ or ‘1’ , in this case we want ‘1’.
How to solve it??
Syntax : Firstly it would have taken the concept of the shifting which we had discussed above.
-
Do right shift the number Upto the ith times which we want the bit.
After Step1 : step1 = n >> i; -
Now Do the AND operation between the result of step1 and the Number '1'.
After Step2 : result = (step1&1);
In Proper syntax:
d) How to toggle any particular ith bit of an integer using bit manipulation?
To solve this problem we have to get an idea what the question is trying to say.
For eg : integer is 5 , its Binary equivalent is 0101
Let's say we want to toggle bit number 2 from the right side.
So after toggle the bit we would get Binary equivalent as : ‘0001’.
How to solve it??
Syntax : Firstly it would have taken the concept of the shifting which we had discussed above.
-
Do left shift the number '1' Upto the given position where to set it.Let take it as ;pos.
After Step1 : step1 = 1 << pos; -
Now Do the XOR operation between the result of step1 and the Number itself.
After Step2 : result = (n ^ step1);
In Proper syntax:
e) How to Update any bit of an integer to a given Value using bit manipulation?
To solve this problem we have to get an idea what the question is trying to say.
For eg : integer is 5 , its Binary equivalent is 0101
Let's say we want to Update bit number 2 from the right side to value 0.
So after Update the bit we would get Binary equivalent as : ‘0001’.
How to solve it??
Syntax : Firstly it would have taken the concept of the shifting which we had discussed above.
-
Firstly mask all the bits and set to 1 except the ith position bit.
Step1 = ~(1 << pos); -
Now we have to clear this bit from the number so ,
Step2 : number = (number & step1); -
Now apply the logic in Topic ‘a’ to set the bit but not only ‘1’ , but the given value by the user,
So result = (number | (value << pos));
In Proper syntax:
3. Some Important Question which can be solved with the Help of Bit Manipulation
a) Check Number is in Power of Two or not:
- Here we have to do some simple calculations, not so complex, just we have to remember the concept of how it's going on.
- Many of us will directly solve using the naive approach but it can easily be done using bit manipulation.
-
Concept : Now let's take any number which is power of 2.
For eg : 8 is power of 2 and its binary equivalent is : 1000
Now we have to check the binary equivalent of (n-1) that is 7 = 0111. - From the above 2 numbers we can see that if we do the AND operation between n and n-1 , it always results in the 0. Where n is power of two.
- So from this login if we get any number ‘n’ we can find ‘n-1’ and simply do the ‘&’ operation between this , if the result is ‘0’ then its the power of 2 else not.
In Proper syntax:
b) How we can count the set bits in any given number :
- Many of us would first find the binary of the given number and would store in the string then would traverse each character and would check if it is 1 or not if it is ’1’ then will increment the count otherwise not.
- This Type of task would create greater complexity and more code size.
- So if we could do it by the use of bit manipulation it can reduce the complexity and also would reduce the codesize.
- So in this firstly we would take n and n-1 and would do the (n & n-1) upto we get the result ‘0’ and will count the number of steps to get the answer ‘0’.
- This would result in the number of setbits the number contains without actually converting to the binary.
In Proper syntax:
c) How to find the single unique element present in the array of duplicates elements occurring twice :
- This question is very easy to be done using the naive approach , just like traversing the array element and taking count of extra array array how many times the number occurring and then finally traverse another array to find the element with count 1 and return the index of it.
- This type of approach can take greater time complexity as well as space complexity as we are also using another array.
- So if we could do it by the use of bit manipulation it can reduce the complexity and also would reduce the codesize.
- Here we can use the concepts of the XOR , as initially to the blog there is the Truth table of the XOR logic.
- If we clearly see that table we can see that if two elements are the same then its xor is 0.
- Now applying this concept to the array elements we would find the XOR of each element by traversing the array and guess what , our final answer to get a unique element would be that only, because the duplicate element would get eliminated.
In Proper syntax:
d) How to Find the Xor of 1-n given the n is the last number?
- Simple method is that we directly start to traverse from 1 to n and do xor with the number, it would have more time complexity.
- Using the Concepts of the bit manipulation we can directly give the answer based on the n.
- That is if the given n is divisible by 4 , then our XOR from 1-n is n only.
- if the given n when divisible by 4 gives the remainder of 1 then our XOR from 1-n is 1.
- if the given n when divisible by 4 gives the remainder of 2 then our XOR from 1-n is n+1.
- If from the above 3 possibility is not come, then our xor from 1-n is : 0
In Proper syntax:
Hence we had seen some of the important concepts regarding bit manipulation which can be used in direct or indirect ways to solve the question. This is the least thing which we should know while doing any problem based on the bit manipulation, Not only to solve the question but while giving the interview it would really help to brush up your skills to solve such kind of problems.
Written By: HIT Kumar Bhalodia
Categories: BIT