Bit Manipulation Algorithms

Bit manipulation algorithms are the secret tools of expert programmers, transforming seemingly complex problems into elegant, one-line solutions. By treating data not as abstract numbers or characters but as sequences of binary digits, you can achieve remarkable performance gains in both speed and memory usage. These techniques are foundational in systems programming, competitive coding, and any domain where computational efficiency is paramount, from graphics rendering to cryptography.

Foundational Bitwise Operations

All bit manipulation rests on a handful of bitwise operators that act directly on the binary representation of integers. Understanding these is non-negotiable. The core logical operators are AND (&), OR (|), XOR (^), and NOT (~). Each compares corresponding bits between two numbers. For instance, 5 & 3 (binary 101 & 011) results in 001, or 1, because only the rightmost bit is 1 in both numbers.

Beyond these, the shift operators are crucial for moving bits around. The left shift (<<) moves all bits left, filling vacated spots with zeros. This is equivalent to multiplication by powers of two: n << 3 is $n\ast 2^3$. The right shift (>>) moves bits right. For signed integers, this often fills with the sign bit (arithmetic shift), while for unsigned integers, it fills with zero (logical shift). These shifts are the workhorses for isolating specific bits within a number. A powerful pattern is using 1 << k to create a bit mask—a value with only the k-th bit set (counting from the right, starting at 0). This mask can then probe or modify that specific bit in another number.

Core Problem-Solving Techniques

Checking if a Number is a Power of Two

A common interview and optimization problem asks: "Is the integer n a power of two?" A naive solution might use loops or logarithms. The bit-manipulation answer is both brilliant and instantaneous. The key insight is that a power of two, like 8 (1000 in binary), has exactly one 1 bit. The number immediately before it, 7 (0111), has all lower bits set. Therefore, for any power of two, n & (n - 1) will be zero. The operation n & (n - 1) has the effect of dropping the lowest set bit. For a number with only one set bit, dropping it leaves zero. Your check becomes: n > 0 && (n & (n - 1)) == 0.

Counting Set Bits (Brian Kernighan's Algorithm)

Counting how many 1 bits (set bits) are in a number's binary form is called calculating its Hamming weight or population count. A simple approach checks each bit in a loop, taking $O(\text{number of bits})$ time. Brian Kernighan's algorithm is more efficient, running in $O(\text{number of set bits})$ time. It directly uses the n & (n - 1) trick we just learned. Each operation n = n & (n - 1) drops the lowest set bit. You simply count how many times you can perform this operation before n becomes zero.

def count_set_bits(n):
    count = 0
    while n:
        n = n & (n - 1)  # Drop the lowest set bit
        count += 1
    return count

For n = 13 (1101), the loop runs: 13 & 12 = 12 (1100), 12 & 11 = 8 (1000), 8 & 7 = 0. Count is 3, which is correct.

Finding the Single Element with XOR

The XOR (^) operator is uniquely powerful. It returns 1 only when bits differ. Crucially, it is commutative, associative, and has two magical properties: $x^x=0$ and $x^0=x$. This makes it perfect for solving problems involving pairs. The classic example: given an array where every element appears exactly twice except for one element which appears once, find the unique element. The solution is to XOR all elements together. All paired elements will cancel out to zero $a^a=0$, and the zero will then XOR with the unique element to yield the answer $0^b=b$.

$$\text{result}=\text{arr}[0]\oplus \text{arr}[1]\oplus \text{arr}[2]\oplus ...\oplus \text{arr}[n-1]$$

This elegant, $O(n)$ time, $O(1)$ space solution is a hallmark of bit manipulation thinking.

Representing Subsets with Bit Masks

Bit masks are perhaps the most versatile application. You can use a single integer to represent a subset of items from a set of size $k$, provided $k$ is less than the number of bits in the integer type (e.g., 32 or 64). Each bit position corresponds to one item: 1 means the item is in the subset, 0 means it is excluded. The integer 5 (binary 0101) represents a subset containing items 0 and 2. This enables incredibly efficient operations:

• Check membership: if (mask & (1 << item_index)) != 0
• Add an item: mask = mask | (1 << item_index)
• Remove an item: mask = mask & ~(1 << item_index)
• Toggle an item: mask = mask ^ (1 << item_index)

You can even iterate through all subsets of a set of size n by looping for mask in range(0, 1 << n):. This compact representation is essential for dynamic programming problems (like the Traveling Salesperson Problem) and efficiently tracking states.

Common Pitfalls

1. Operator Precedence Confusion: Bitwise operators have lower precedence than comparison operators. A condition like if (n & 1 == 0) intending to check if n is even will fail because 1 == 0 is evaluated first, becoming false (0). The correct form is if ((n & 1) == 0). Always use parentheses liberally with bitwise operations.

1. Logical vs. Bitwise Operators: Mistaking && for & or || for | is a critical error. The logical operators (&&, ||) evaluate to boolean true/false and short-circuit. The bitwise operators (&, |, ^) perform bit-by-bit calculations. Using if (n & 1) is valid (it checks if the result is non-zero), but if (n && 1) is always true for n != 0.

1. Shifting Beyond Bit Width: The behavior of shifting by a number greater than or equal to the bit width of the integer (e.g., int32 << 32) is undefined in languages like C/C++, leading to unpredictable results. In practice, it is often limited by the bit width modulo the size (e.g., x << 32 might behave as x << 0), but you should never rely on this. Ensure your shift amount k satisfies $0\le k<\text{bit width}$.

1. Ignoring Signed Integers (Sign Bit): Right-shifting a negative signed integer (>>) typically performs an arithmetic shift, preserving the sign bit. This means -8 >> 1 might yield -4, not the 60 you might expect if you were thinking of the binary pattern. For logical shift behavior with signed integers, cast to an unsigned type first or use an explicit mask.

Summary

• Bit manipulation uses direct binary operations (&, |, ^, ~, <<, >>) to create algorithms that are exceptionally fast and memory-efficient.
• The operation n & (n - 1) is fundamental: it drops the lowest set bit, enabling checks for powers of two and efficient bit counting via Brian Kernighan's algorithm.
• The XOR operator's self-canceling property $x^x=0$ provides elegant $O(n)$ solutions to problems involving finding unpaired elements.
• A bit mask uses the bits of a single integer to represent a subset, allowing for compact state representation and rapid set operations, which is invaluable in combinatorial and systems programming.
• Mastery of these techniques requires careful attention to operator precedence, the distinction between logical and bitwise operators, and the nuances of working with signed integers and shift boundaries.