Bitwise Programming

260

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 2: Using toggling approach: n & n-1

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

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.

Previous articleReductions
Next articleTypes of Users in Database
I am Harshit Brijwasi. I am an engineer and a Technical Content writer. I am here to share my knowledge about technical topics and help researchers with them.

This site uses Akismet to reduce spam. Learn how your comment data is processed.