Mastering bitwise operations: Practical tips for efficient coding

Bit manipulation involves the use of bitwise operators to directly manipulate bits of a binary number. It's a fundamental concept in programming, especially in low-level system design, algorithm optimization, encryption, and working with hardware interfaces. In this post, we'll dive into bit manipulation, listing all key operations and providing examples to demonstrate how these work.

What is bit manipulation?

Bit manipulation refers to the act of modifying individual bits of a binary number using bitwise operators. These operations allow programmers to optimize algorithms for speed and memory efficiency by performing operations directly on binary data.

In a binary number, each digit is called a bit. For example, the binary number 1011 (11₁₀) is composed of 4 bits. The individual bits represent powers of two, starting from the least significant bit (LSB) on the right to the most significant bit (MSB) on the left.

Bit manipulation operations allow us to:

• Set, clear, toggle, or shift individual bits.
• Perform logical operations on bits.

Common bit manipulation operations

Here's a list of common bit manipulation operations. We'll explore each operation in the next section.

Basic bitwise operations

AND (&)

The AND operation compares each bit of two numbers and returns 1 only if both bits are 1; otherwise, it returns 0.

5 & 3
// 5 in binary:  0101
// 3 in binary:  0011
// Result:       0001  (which is 1)

OR (|)

The OR operation compares each bit of two numbers and returns 1 if at least one of the bits is 1.

5 | 3
// 5 in binary:  0101
// 3 in binary:  0011
// Result:       0111  (which is 7)

XOR (^)

The XOR (exclusive OR) operation returns 1 only if the corresponding bits of the two operands are different. Otherwise, it returns 0.

5 ^ 3
// 5 in binary:  0101
// 3 in binary:  0011
// Result:       0110  (which is 6)

NOT (~)

The NOT operation is a bitwise negation. It inverts all the bits of the number (turning 1s into 0s and vice versa, 0s into 1s).

~5
// 5 in binary:  00000101
// Result:       11111010  (which is -6, due to two's complement representation)

Left Shift (<<)

The left shift operation shifts all the bits of a number to the left by a specified number of positions, effectively multiplying the number by 2 for each shift.

5 << 1
// 5 in binary:  0101
// Shift left:   1010  (which is 10)

Right Shift (>>)

The right shift operation shifts all the bits of a number to the right by a specified number of positions, effectively dividing the number by 2 for each shift.

20 >> 2
// 20 in binary:  00010100
// Shift right:   00000101  (which is 5)

Advanced bitwise usages and operations

Advanced bitwise operations go beyond basic shifts and include techniques that allow you to efficiently manipulate specific bits within a number.

Bit Masking

Bit masking is used to extract or modify specific bits of a number. By using a mask (a binary number), you can isolate particular bits using AND, OR, or XOR operations. Example: Extract the lowest 4 bits of a number:

int num = 29;  // 00011101
int mask = 15; // 00001111
int result = num & mask;  // Result: 00001101 (which is 13)

Setting a Bit

To set a specific bit in a number to 1, you can use the OR (|) operator with a mask where the desired bit is 1. Example: Set the 2nd bit (counting from 0) of the number 5 to 1.

int num = 5;   // 0101
int mask = 1 << 2;  // 0100
num = num | mask;   // Result: 1101 (which is 13)

Clearing a Bit

To clear a specific bit in a number, use the AND (&) operator with a mask where the desired bit is 0 and all other bits are 1. Example: Clear the 2nd bit of the number 13 (binary 1101).

int num = 13;  // 1101
int mask = ~(1 << 2);  // 1011
num = num & mask;      // Result: 1001 (which is 9)

Toggling a Bit

To toggle a specific bit (flip between 0 and 1), use the XOR (^) operator with a mask where the desired bit is 1. Example: Toggle the 1st bit of the number 5 (binary 0101).

int num = 5;   // 0101
int mask = 1 << 1;  // 0010
num = num ^ mask;   // Result: 0111 (which is 7)

Checking if a Bit is Set

To check if a specific bit is set (if it’s 1), use the AND (&) operator with a mask and compare the result with 0. Example: Check if the 3rd bit of the number 9 (binary 1001) is set.

int num = 9;   // 1001
int mask = 1 << 3;  // 1000
bool isSet = num & mask;  // True, because 1000 & 1001 = 1000

Swapping Bits

To swap two bits at given positions, you can use XOR (^) combined with shifts. Example: Swap the 0th and 3rd bits of the number 9 (binary 1001).

int num = 9;  // 1001
int pos1 = 0, pos2 = 3;
int bit1 = (num >> pos1) & 1;
int bit2 = (num >> pos2) & 1;
if (bit1 != bit2) {
    num ^= (1 << pos1) | (1 << pos2);
}
// Result: 9 becomes 1000, which is 8