While programming, we will come across many such problems that can be solved easily using bitwise programming. So, in this tutorial, we will learn about bitwise programming.
Hacks in Bitwise Programming
In C and C + + we can work with bits effectively. First, let us see the definitions of each bit operation and then move on to different techniques for solving the problems. Basically, there are six operators that C and C + + support for bit manipulation:
Bitwise AND
The bitwise Or tests two binary numbers and returns bit values of 1 for positions where both numbers had a one, and bit values of 0 where both numbers did not have one:
& 01001011
00010101
———————-
0000001
Bitwise OR
The bitwise OR tests two binary numbers and returns bit values of 1 for positions where either bit or both bits are one, the result of 0 only happens when both bits are 0:
01001011
| 00010101
————————–
01011111
Bitwise Exclusive – OR
The bitwise Exclusive – OR tests two binary numbers and returns bit values of 1 for positions where either bit or both bits are one, the result of 0 happens when both bits are 0:
01001011
^00010101
—————————–
01011110
Bitwise Left Shift
The bitwise left shift moves all bits in the number to the left and fills vacated bit positions with 0.
Bitwise Right Shift
The bitwise right shift moves all bits in the number to the right.
Note the use of ? for the fill bits. Where the left shift filled the vacated positions with 0, a right shift will do the same only when the value is unsigned. If the value is signed then a right shift will fill the vacated bit positions with the sign bit or 0, whichever one is implementation-defined. So the best option is to never right shift signed values.
Bitwise Complement
The bitwise complement inverts the bits in a single binary number.
Checking Whether Kth Bit is Set or Not
Let us assume that the given number is n. Then for checking the K th bit we can use the expression: n & (1 ≪ K 1). If the expression is true then we can say the K th bit is set
Setting Kth Bit
For a given number n, to set the K th bit we can use the expression: n | 1 ≪ (K – 1)
Clearing Kth Bit
To clear Kth bit of a given number n, we can use the expression: n&~(1<<K-1)
Example :
Toggling Kth Bit
For a given number n, for toggling the Kth bit we can use the expression: n^(1<<K-1)
Example:
Toggling Rightmost One Bit
For a given number n, for toggling rightmost one bit we can use the expression: n & n – 1
Example:
Isolating Rightmost one Bit
For a given number n, for isolating the rightmost one bit we can use the expression: n & – n
Isolating the Rightmost Zero Bit
For a given number n, for isolating the rightmost zero bit we can use the expression: ~n & n + 1
Checking Whether Number is Power of 2 or Not
Given the number n, to check whether the number is in 2 n form or not, we can use the expression: if(n & n – 1 == 0)
Multiplying Number by Power of 2
For a given number n, to divide the number with 2 K we can use the expression: n ≫ K
Example :
Finding the Modulo of a Given Number
For a given number n, to find the %8 we can use the expression: n & 0x7. Similarly, to find %32, use the expression: n & 0x1F
Note: Similarly, we can find the modulo value of any number.
Reversing the Binary Number
For a given number n, to reverse the bits (reverse (mirror) of binary number) we can use the following code snippet:
Time Complexity: This requires one iteration per bit and the number of iterations depends on the size of the number.
Counting Number of One’s in Number
For a given number n, to count the number of 1’s in its binary representation we can use any of the following methods.
Method 1: Process bit by bit with bitwise and operator
Method 2: Using toggling approach: n & n-1
Creating Mask for Trailing Zero’s
For a given number n, to create a mask for trailing zeros, we can use the expression: (n & – n) – 1
Note: In the above case we are getting the mask as all zeros because there are no trailing zeros
Swap all odd and even bits
Performing Average without Division
Is there a bit-twiddling algorithm to replace mid = (low + high) / 2 (used in Binary Search and Merge Sort) with something much faster? We can use mid = (low + high) >> 1. Note that using (low + high) / 2 for midpoint calculations won’t work correctly when integer overflow becomes an issue. We can use bit shifting and also overcome a possible overflow issue: low + ((high – low)/ 2) and the bit shifting operation for this is low + ((high – low) >> 1).
So, in this tutorial, we learned about bitwise programming techniques. Always, there are other methods for a programming question that can be solved using the bitwise programming method. But still, bitwise programming proves to be one of the very useful techniques which allows us to solve logical questions in a much easier way. Also, it reduces the time complexity to a great extent. Apart from all this, there is no need of allocating extra space. So, a solution using bitwise programming proves to be the optimal solution.
Attempt free Data Structures MCQ Test
