Bit Manipulation Pattern

The Bit Manipulation pattern uses binary logical operators (AND, OR, XOR, NOT, and shifts) to perform low-level arithmetic and boolean evaluations on integers in constant time.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks to perform calculations “without using standard arithmetic operators (+, -, *, /)”.
• You need to count the number of set bits (Hamming weight) or reverse binary representations.
• The input is represented as binary strings or bitmasks.
• The task requires finding unique elements where all other elements appear exactly twice (XOR property).

How It Works

Instead of loop divisions or string parsings, you apply logical operators:

• AND (&): Checks if bits are set. n & (n - 1) clears the lowest set bit.
• XOR (^): Flips bits when they differ. Cancel duplicate pairs: x ^ x = 0.
• Shift (<<, >>, >>>): Moves bits. Logical shift >>> shifts sign bits correctly on signed numbers in Java.

For example, to check if a number is a power of two:

1. A power of two in binary contains exactly one set bit (e.g. 8 = 1000).
2. If n > 0, calculate n & (n - 1).
3. If it equals 0, the single set bit was cleared. Return true.

Complexity, With Caveats

• Time Complexity: O(1) time because the bit width of standard integers is fixed (e.g. 32-bit or 64-bit). The operations run directly on hardware.
• Space Complexity: O(1) auxiliary space.

Minimal Code Template

public class BitManipulationTemplate {
    // Brian Kernighan's Algorithm to Count Set Bits
    public int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // clears lowest set bit
            count++;
        }
        return count;
    }
}

# Brian Kernighan's Algorithm to Count Set Bits
def count_set_bits(n: int) -> int:
    count = 0
    while n != 0:
        n = n & (n - 1)  # clears lowest set bit
        count += 1
    return count

class BitManipulationTemplate {
public:
    // Brian Kernighan's Algorithm to Count Set Bits
    int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // clears lowest set bit
            count++;
        }
        return count;
    }
};

Where This Pattern Falls Short

• Python arbitrary precision integers: Unlike Java and C++ where integers overflow at 32 or 64 bits, Python integers grow dynamically. This means left-shifts and operations on negative numbers can result in infinite loops unless you manually mask them (e.g. n & 0xFFFFFFFF).
• Readability: Bitwise code is often hard to read and debug. If the constraints are relaxed, writing standard arithmetic equations is preferred.

Related Patterns, Compared

• Math & Geometry: choose this instead when the problem requires floating-point calculations or geometric relationships that cannot be modeled as bitwise masks.
• Dynamic Programming: choose this instead when matching states can be modeled in a 1D or 2D table rather than bitwise combinations.

Frequently Asked Questions

What is the difference between logical right shift (>>>) and arithmetic right shift (>>)? Arithmetic right shift >> preserves the sign of the number by padding the left with the sign bit (1 for negative, 0 for positive). Logical right shift >>> (used in Java) always pads the left with 0s, regardless of the sign.

Why does x ^ x equal 0? Because the XOR operator returns 1 only if the bits differ. Since a number compared against itself has identical bits, every position results in 0, clearing the entire value.

What does this pattern test in interviews? It tests your comfort with binary representations, understanding hardware boundaries, and applying math shortcuts.