Bit Manipulation: Algorithms and Tricks

Bit manipulation is the art of using bitwise operators to solve problems efficiently. It is one of the oldest optimization techniques in computing — direct control over individual bits can replace expensive arithmetic and branching operations.

Bitwise Operators

Every programming language provides a set of bitwise operators. They operate on the binary representation of integers.

XOR is particularly useful because it is its own inverse: a ^ b ^ b = a. This property drives many bit manipulation tricks.

Essential Tricks

Check if a Number Is Even or Odd

if n & 1:
    print("odd")
else:
    print("even")

The least significant bit is 1 for odd numbers and 0 for even numbers. This is faster than n % 2.

Get, Set, Clear, Toggle Bits

# Get the k-th bit (0-indexed)
bit = (n >> k) & 1

# Set the k-th bit to 1
n = n | (1 << k)

# Clear the k-th bit (set to 0)
n = n & ~(1 << k)

# Toggle the k-th bit
n = n ^ (1 << k)

Power of Two Check

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

The trick: powers of two have exactly one bit set. Subtracting 1 flips all lower bits, so n & (n - 1) becomes zero.

Count Set Bits (Population Count)

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

Brian Kernighan’s algorithm runs in O(k) where k is the number of set bits, rather than O(n) for a naive loop through all bits.

Find the Only Non-Repeating Element

Given an array where every element appears twice except one, find the unique element:

def find_unique(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

XOR cancels pairs: a ^ a = 0, so the remaining value is the unique element.

Find the Rightmost Set Bit

rightmost = n & -n

Two’s complement negation (-n) flips all bits and adds 1. The result isolates the lowest set bit.

Swap Two Numbers Without a Temporary Variable

a ^= b
b ^= a
a ^= b

This XOR swap works because a ^ b ^ b = a and a ^ b ^ a = b.

Bitmasking

Bitmasks pack multiple boolean flags into a single integer. Each bit represents a distinct option or state.

# Define flags as powers of two
READ = 1 << 0    # 1
WRITE = 1 << 1   # 2
EXECUTE = 1 << 2 # 4

# Combine permissions
permissions = READ | WRITE  # 3

# Check permissions
has_write = permissions & WRITE  # True (2)
has_execute = permissions & EXECUTE  # False (0)

# Remove a permission
permissions &= ~WRITE  # 1 (read only)

Bitmasks are used extensively in operating systems (file permissions), graphics (color channels), and networking (flags in protocol headers).

Subset Enumeration

Generate all subsets of a set using bitmasks:

def subsets(elements):
    n = len(elements)
    result = []
    for mask in range(1 << n):
        subset = [elements[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

Each mask from 0 to 2ⁿ−1 represents a distinct subset. This is often useful for brute-force solutions to small instances of NP-hard problems.

Common Interview Problems

Single Number

Find the element that appears only once when others appear twice. Use XOR across the entire array.

Number of 1 Bits

Count set bits using n & (n - 1) in a loop, or use the built-in bit_count() in modern languages.

Reverse Bits

Reverse the bits of a 32-bit unsigned integer. Process bits one by one or use divide-and-conquer with masks. The divide-and-conquer approach uses masks like 0x55555555, 0x33333333, 0x0F0F0F0F to swap adjacent groups of bits, doubling the group size at each step.

Missing Number

Given an array of n distinct numbers from 0 to n, find the missing one. XOR all indices and values. Since i ^ i = 0, the missing number emerges as the only uncancelled value.

Power of Two

Check if a number is a power of two using the n & (n - 1) trick.

Find the Two Non-Repeating Elements

When two elements appear once and all others appear twice, XOR the entire array to get x ^ y. Then isolate any set bit of this result and partition the array into two groups based on that bit. XOR each group separately to recover both numbers.

Performance Considerations

Bitwise operations are the fastest operations a CPU can perform. They execute in a single clock cycle on most processors. Replacing modulo operations with bitwise AND, multiplication/division with shifts, and conditional branches with bit tricks can yield significant speedups in tight loops.

However, readability matters. Use bit manipulation when performance is critical or when the domain naturally involves bits (networking, graphics, compression). For general business logic, clarity is usually more important.

Best Practices

Always use unsigned types when working with bit manipulation to avoid sign extension surprises. Parenthesize expressions to make operator precedence explicit. Document unusual bit tricks with comments explaining the underlying logic. Test with edge cases like zero, negative numbers, and the maximum value for the type.

Advanced Bit Manipulation Patterns

Beyond the basics, several advanced patterns appear frequently in algorithmic problem solving. The Brian Kernighan trick (n & (n - 1)) can be extended to find the next power of two greater than or equal to a number: repeatedly apply the trick or use 1 << (n.bit_length()). The lowest set bit isolation (n & -n) is useful in Fenwick trees (Binary Indexed Trees) where updating and querying require traversing index bits from LSB to MSB.

Gray code generation uses bit manipulation: the i-th Gray code is i ^ (i >> 1). Gray codes are used in error correction, digital communication, and Karnaugh maps where only one bit changes between consecutive values. The recursive construction property of Gray codes makes them useful for hardware state machines and reducing switching noise in digital circuits.

Subset enumeration over a specific mask can be done efficiently using the submask enumeration pattern: sub = (sub - 1) & mask iterates through all submasks of mask in decreasing order, visiting exactly 2^k submasks where k is the number of set bits. This pattern is essential in bitmask DP for problems like the traveling salesman or vertex cover on small graphs.

Bit Manipulation in Different Languages

Languages expose bitwise operators with varying semantics. In C and C++, right shifts on signed integers are implementation-defined — the result may be arithmetic (sign-extending) or logical (zero-filling). Java provides both >> (arithmetic) and >>> (logical) shift operators. Python integers are arbitrarily large, so bitwise operations work on infinite two’s complement — negative numbers have an infinite prefix of 1 bits, which can cause surprises when porting algorithms from fixed-width languages. JavaScript treats bitwise operands as 32-bit signed integers, truncating results to 32 bits. Rust provides both arithmetic and logical shifts with explicit wrapping semantics through its type system, making it easier to avoid portability bugs.

Practical Use Cases

Beyond algorithmic puzzles, bit manipulation powers core systems software. The Linux kernel uses bit operations extensively for flags and state management in process schedulers, file systems, and device drivers. Networking stacks rely on bit manipulation for parsing packet headers where flags are packed into individual bits. Compression algorithms like zlib and LZ4 use bit-level operations for entropy coding. Graphics programming uses bitwise operations extensively for color channel extraction and blending — an ARGB color stored as a 32-bit integer is decomposed using shift and mask operations. Cryptography algorithms including AES and SHA operate directly on bits through substitution-permutation networks that rely on XOR and bit rotations.

FAQ

When should I use bit manipulation instead of arithmetic? Use bit manipulation when working with binary protocols, graphics, compression, cryptography, or any domain where individual bits carry meaning. Use arithmetic for general numeric computation — most compilers optimize arithmetic into bit operations internally anyway.

Is the XOR swap still useful today? No. Modern compilers optimize temporary variable swaps into register moves without extra memory access. The XOR swap is harder to read and can be slower due to data dependencies. Use a simple temporary variable.

How do I check if only one bit is set? Use n > 0 and (n & (n - 1)) == 0. This checks both that the number is positive and that clearing the lowest set bit produces zero.

What is the fastest way to count bits? Modern CPUs have a dedicated POPCNT instruction. Use int.bit_count() in Python, Integer.bitCount() in Java, __builtin_popcount() in GCC, or std::popcount() in C++20. These are faster than any loop-based implementation.

How do I iterate over all subsets of a set efficiently? Use the bitmask enumeration pattern for mask in range(1 << n). For iterating over submasks of a specific mask, use the submask iteration pattern sub = (sub - 1) & mask.

Internal Links

Recursion Guide — Data Structures Guide — Searching Algorithms