DS: Using Bitwise Operators in Programming

If you've programmed before, you must have used some kind of numeric data type, such as an integer. But have you ever thought about how our computer actually stores these numbers? Instead of storing the data as decimal, computers store values using the binary system. Now, there are some operators that specifically act on the bits of the numbers in binary form, aptly named as Bitwise Operators. Now before going to these operators, we should know where these bit manipulation tactics are used. 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. In C and C++ we can work with these bits effectively.

In this article, we will first see each bit operation and then we will see some commonly used methods for solving the problems.

There are 6 bitwise operators namely:

Let’s go through the six bitwise operators one by one.

Bitwise AND operator &

The bitwise AND tests two binary numbers and returns bit values of 1 for positions where both numbers had a 1 and bit values of 0 where both numbers did not have 1. Let us see the bitwise AND operation of two integers 12 and 23.

12 = 00001100 (In binary)
23 = 00010111 (In binary)

  00001100
& 00010111
  ---------
  00000100 = 4 (In decimal)

Bitwise OR operator |

The bitwise OR tests two binary numbers and returns bit values of 1 for positions where either bit or both bits are 1 and the result of 0 when both bits are 0. Let us see the bitwise OR operation of two integers 12 and 23.

12 = 00001100 (In binary)
23 = 00010111 (In binary)

  00001100
| 00010111
  ---------
  00011111 = 31 (In decimal)

Bitwise Exclusive-OR operator ^

The bitwise Exclusive-OR(commonly known as XOR) tests two binary numbers and returns bit values of 1 for positions where both bits are different. If both bits are the same then the result is 0. Let us see the bitwise XOR operation of two integers 12 and 23.

12 = 00001100 (In binary)
23 = 00010111 (In binary)

  00001100
^ 00010111
  ---------
  00011011 = 27 (In decimal)

Bitwise Left Shift operator <<

The bitwise left shift moves all bits in the number to the left and fills vacated bit positions with 0. Let us take an example of the left-shift operator on integer 23.

23 = 00010111 (In binary)

  00010111
 << 2 (left shift by 2 bits)
  ---------
  01011100 = 92 (In decimal)

Bitwise Right Shift operator >>

The bitwise right shift moves all bits in the number to the right. The vacated positions after the right shift will be filled with 0 only when the value is unsigned. If the value is signed, the vacated position after the right shift will be filled with the sign bit or 0, depending on the implementation-defined in the problem. Let us take an example of the right-shift operator on integer 23.

23 = 00010111 (unsigned binary number)

  00010111
 >> 2 (right shift by 2 bits)
  ---------
  00000101 = 5 (In decimal)

Bitwise Complement operator ~

The bitwise complement inverts the bits in a single binary number. Let us take an example of the complement operator on integer 23.

23 = 00010111 (In binary)

  00010111
 ~
  ---------
  11101000 = 232 (In decimal)

Some frequently used methods in Bitwise programming

Checking K^th Bit

Let the given number be n. To check the K^th bit we can use the expression: n & (1 ≪ K-1). If the expression is true then we can say the Kth bit is set. That means, K^th bit is set to 1.

n = 00101100
K = 3
1 << K-1 (00000100)

n & (1 << k-1) = (00000100)

Setting K^th Bit

Let the given number be n. For setting the K^th bit we can use the expression: n | (1 ≪ K-1).

n = 00101000
K = 3
1 << K-1 (00000100)

n | (1 << k-1) = (00101100)

Clearing K^th Bit

Let the given number be n. To clear the K^th bit we can use the expression: n & ~(1 ≪ K-1).

n = 00101100
K = 3
1 << K-1 (00000100)
~(1 << K-1) (11111011)

n & ~(1 << k-1) = (00101000)

Toggling K^th Bit

Let the given number be n. To toggle the K^th bit we can use the expression: n ^ (1 ≪ K-1).

n = 00101100
K = 3
1 << K-1 (00000100)

n ^ (1 << k-1) = (00101000)

Multiplying Number by 2^K

Let the given number be n. To multiply the number with 2^K, we can use the expression: n << K.

n = 00000011 (In binary) or 3 (In decimal)
K = 3

(n << K) = 00011000 (In binary) or 24 (In decimal)

Dividing Number by 2^K

Let the given number be n. To divide the number with 2^K, we can use the expression: n >> K.

n = 00011000 (In binary) or 24 (In decimal)
K = 3

(n >> K) = 00000011 (In binary) or 3 (In decimal)

Toggling Rightmost 1 Bit

Let the given number be n. To toggle the rightmost 1 bit, we can use the expression: n & (n-1).

n = 00101101
n-1 = 00101100

n & (n-1) = (00101100)

Isolating Rightmost 1 Bit

Let the given number be n. To isolate the rightmost 1 bit, we can use the expression: n & -n.

n = 00101101
-n = 11010011

n & -n = (00000001)

Here, we use 2's complement representation for computing -n. We can compute 2's complement using the expression -n = ~n + 1.

Isolating Rightmost 0 Bit

Let the given number be n. To isolate the rightmost 0 bit, we can use the expression: ~n & (n+1).

n = 00101101
~n =  11010010
n+1 = 00101110
~n & (n+1) = (00000010)

Some interesting problems to solve using bitwise operations.

1. Find the element that appears once
2. Find the missing number
3. XOR Linked List
4. Reverse Bits
5. Divide Integers
6. Single Number
7. Different Bits Pairwise Sum

And that's it!

We've seen what bit manipulation is, operators involved in bitwise operations, and some frequently used methods for solving the questions. Whether you're new to bitwise operations or refreshing your knowledge, I hope this deep dive has been a good companion in understanding how bit manipulation works.

If you have any questions, feel free to leave a response or drop me a tweet!