Bit Manipulation: Power of Bits

Every integer hides a secret in its binary representation. Bit manipulation lets you exploit these hidden patterns to solve problems in O(1) space, perform arithmetic that seems to require division or multiplication, and encode information compactly. Interviewers love bit problems because they test whether you understand how computers actually work under the hood—and there are only a handful of classic patterns to master.

The six fundamental operations—AND, OR, XOR, NOT, left shift, and right shift—combine in surprising ways. XOR is particularly magical: a^a = 0 and a^0 = a, which makes it perfect for finding unique elements or swapping variables without temp storage. Left shift multiplies by 2; right shift divides by 2 (floored). Combining these primitives can replace expensive operations entirely.

Introduction

Every integer hides a secret in its binary representation. Bit manipulation lets you exploit these hidden patterns to solve problems in O(1) space, perform arithmetic that seems to require division or multiplication, and encode information compactly. Interviewers love bit problems because they test whether you understand how computers actually work under the hood—and there are only a handful of classic patterns to master.

The six fundamental operations—AND, OR, XOR, NOT, left shift, and right shift—combine in surprising ways. XOR is particularly magical: a^a = 0 and a^0 = a, which makes it perfect for finding unique elements or swapping variables without temp storage. Left shift multiplies by 2; right shift divides by 2 (floored). Combining these primitives can replace expensive operations entirely.

When to Use

Bit manipulation shines when:

• Space is at a premium — Flags, bitmaps, and compact encodings save memory
• Arithmetic constraints — “No multiplication/division” problems use shifts instead
• Finding unique element — XOR identifies the element appearing once among pairs
• Bit counting — Hamming weight problems for parity or similarity measures
• Power of 2 checks — Single bit means exactly one set bit

When Not to Use

• When readability matters more than optimization (bit hacks can obscure intent)
• Languages without unsigned integers or with platform-dependent shift behavior
• When standard library functions already solve the problem clearly

Core Operations Reference

Operation	Symbol	Truth Table	Common Use
AND	&	1&1=1, else 0	Clear bits, isolate masks
OR	|	0|0=0, else 1	Set bits
XOR	^	1^1=0, 0^0=0, else 1	Toggle, find unique
NOT	~	Flips all bits	Two’s complement math
Left Shift	<<	x << n = x × 2ⁿ	Multiply by power of 2
Right Shift	>>	x >> n = x ÷ 2ⁿ (floor)	Divide by power of 2

Production Failure Scenarios

Failure	Cause	Mitigation
Signed vs unsigned overflow	Right shift of negative numbers is implementation-defined	Use unsigned types or mask with 0x7FFFFFFF
Off-by-one in bit isolation	Confusing 1-indexed vs 0-indexed bit positions	Draw binary representation explicitly
NOT vs negative numbers	~x = -x - 1 in two’s complement catches everyone off guard	Always test with edge cases like 0, 1, -1
JavaScript bit operations	JavaScript treats all numbers as 64-bit float, then converts	Use >>> 0 to force unsigned 32-bit

Trade-off Table

Approach	Operation Count	Readability	Performance
Arithmetic	1	High	Slower on older hardware
Bit shift	1	Medium	Faster on all hardware
Lookup table	1	High	Fastest but uses memory
Modular arithmetic	Multiple	Medium	Variable

For most modern code, readability wins. If you’re writing crypto or low-level systems code, the bit tricks matter more.

Implementation

Bitwise Operations Reference

Reference: Bitwise Operations Reference

Swap Two Numbers Without Temp

def swap(a, b):
    """
    Swap using XOR (only works for distinct values).
    """
    a = a ^ b
    b = a ^ b  # b = (a ^ b) ^ b = a
    a = a ^ b  # a = (a ^ b) ^ a = b
    return a, b

Check if Number is Power of 2

def is_power_of_two(n):
    """
    Power of 2 has exactly one set bit.
    n & (n-1) clears the lowest set bit.
    If result is 0, exactly one bit was set.
    """
    return n > 0 and (n & (n - 1)) == 0

Count Set Bits (Hamming Weight)

def count_bits(n):
    """
    Count set bits using Brian-Kernighan algorithm.
    """
    count = 0
    while n:
        n &= (n - 1)  # Clear lowest set bit
        count += 1
    return count

Find Single Element in Array of Pairs

def find_single(nums):
    """
    XOR all elements. Pairs cancel out to 0, singles remain.
    """
    result = 0
    for num in nums:
        result ^= num
    return result

Bitwise AND Range [m, n]

def range_bitwise_and(m, n):
    """
    Find AND of all numbers from m to n.
    The answer is the common prefix of m and n.
    """
    shift = 0
    while m != n:
        m >>= 1
        n >>= 1
        shift += 1
    return m << shift

Power of Two Check Alternative

def is_power_of_two_v2(n):
    """
    Using n & (-n) isolates the lowest set bit.
    Power of 2 has only one set bit, so n & (-n) == n.
    """
    return n > 0 and (n & (-n)) == n

Common Pitfalls / Anti-Patterns

1. Confusing XOR with addition — XOR adds without carry; 1 ^ 1 = 0, not 2. This trips people up every time.
2. Off-by-one in bit ranges — The bit at position 0 is the least significant (2^0=1). Always draw it out.
3. Right shift of negatives — Result is implementation-defined in C; use masks for portability across compilers.
4. JavaScript quirks — Bitwise operations convert to 32-bit signed integers first, then convert back. Use >>> 0 to force unsigned.
5. Integer overflow — Shifting left past bit width is undefined behavior in C. Your compiler won’t always warn you.

Quick Recap Checklist

• XOR properties: a^a=0, a^0=a, a^b=b^a
• n & (n-1) clears lowest set bit
• n & (-n) isolates lowest set bit
• Left shift multiplies, right shift divides (floor for negatives)
• Two’s complement: ~x = -x - 1

Interview Questions

Further Reading

Books & Articles

• Hacker’s Delight (Henry S. Warren Jr.) — The definitive reference on bit manipulation tricks, covering everything from population count to cyclic redundancy checks.
• Matters Computational (Jörg Arndt) — Comprehensive coverage of bitwise algorithms including Gray codes, bit permutations, and low-level number-theoretic transforms.
• Bit Twiddling Hacks (Sean Eron Anderson) — A curated collection of battle-tested bit manipulation snippets collected from decades of real-world use.

Topic-Specific Deep Dives

Subset Enumeration Using Bitmasks

Represent any subset of an N-element set as an N-bit integer where the i-th bit is 1 if element i is included. Iterating from 0 to 2^N - 1 enumerates all subsets in Gray-code order when using s = s & (s - 1) to visit only set bits. This is the foundation of DP over subsets (e.g., traveling salesman problem with bitmask DP).

# Enumerate all subsets of a set represented by bitmask
mask = 0b1101  # elements 0, 2, 3
sub = mask
while sub:
    # process subset 'sub'
    sub = (sub - 1) & mask

Popcount (Hamming Weight) Variations

Beyond Brian Kernighan’s algorithm, hardware intrinsics like POPCNT on x86 and __builtin_popcount() in GCC offer O(1) popcount. For software implementations, the parallel-prefix divide-and-conquer method (also called “SWAR” — SIMD within a register) runs in O(log n) without loops:

def popcount_swar(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0F0F0F0F
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x3F

Gray Code Generation

Gray codes ensure consecutive values differ by exactly one bit, useful for Karnaugh maps, error correction, and analog-to-digital converters. The n-th Gray code is computed as n ^ (n >> 1).

Sign Extension and Endianness

When extracting bitfields from network protocols or binary file formats, sign extension (arithmetic right shift vs. logical) and endianness (byte ordering) become critical. Always mask before shifting to avoid platform-dependent behavior.

Online Resources

• Bit Twiddling Hacks — Stanford’s collection of bit manipulation tricks
• LeetCode Bit Manipulation Tag — Curated interview problems by topic
• Compiler Explorer (godbolt.org) — Inspect how bit operations compile to assembly across architectures

Conclusion

Bit manipulation lets you exploit patterns in binary representations to solve problems in O(1) space or replace expensive operations with cheap shifts. XOR is particularly useful: a^a = 0 and a^0 = a, which finds unique elements among pairs and swaps variables without temp storage. The n & (n-1) trick clears the lowest set bit—counting bits or checking power-of-two both use this. Left shift multiplies by powers of 2, right shift divides (floored). Watch out for signed vs. unsigned overflow on right shifts, and remember that JavaScript converts to 32-bit signed integers before bitwise operations (use >>> 0 for unsigned). When readability matters more than micro-optimization, use standard library functions instead—bit hacks can obscure intent.