The Seven Bit Manipulation Bugs Nobody Warns You About

You opened the problem. XOR, popcount, maybe a bitmask. You've seen these before. You write clean code, it compiles, you submit, and then test case 47 involving -1 or zero or Integer.MIN_VALUE just eats it alive. Submission rejected.

What happened?

Bit manipulation problems are not actually hard. The algorithm is usually a one-liner once you see it. What bites candidates is the gap between "I know how XOR works" and "I know how XOR works on a signed 32-bit integer in Java with a negative input." That gap is exactly where interviews fall apart, and it is almost never the algorithm's fault.

These are the seven bugs that show up repeatedly. The trick is almost never the problem. The problem is knowing what your language quietly does with negative integers, zero, and overflow when you are not watching.

The Operator That Evaluates in the Wrong Order

Write this condition. It looks right:

if n & mask == 0:
    ...

It is not. In most languages, == has higher precedence than &. This parses as n & (mask == 0), not (n & mask) == 0. The expression mask == 0 evaluates to True or False (which is 1 or 0), and then you AND that with n. You get either 0 or n. Not what you wanted. Not even close.

This one has history. Brian Kernighan and Dennis Ritchie acknowledged it as a design flaw in "The C Programming Language." Early C had & where modern C has &&. When logical operators arrived, bitwise operators kept their original low precedence to avoid breaking production code. The mistake shipped. Java inherited it. Python inherited it. You inherited it right before your interview.

The same trap catches bitwise OR:

// Wrong: | has lower precedence than !=
if (a | b != 0) { ... }     // parsed as a | (b != 0)

// Correct
if ((a | b) != 0) { ... }

The fix is mechanical. Always wrap bitwise expressions in parentheses before comparing them. No exceptions. GCC even ships a warning for exactly this pattern, -Wparentheses. The compiler knows you will make this mistake. It has seen things.

# Wrong
if n & mask == 0: ...
if n | FLAG != 0: ...

# Correct
if (n & mask) == 0: ...
if (n | FLAG) != 0: ...

Zero Passes the Power-of-2 Test

The n & (n-1) trick is one of the cleanest in bit manipulation. It clears the lowest set bit of n, so a power of 2 (exactly one bit set) leaves zero. That makes n & (n-1) == 0 a fast power-of-2 check.

Except zero forgot to read the spec. 0 & -1 == 0. Zero passes the test. Is zero a power of 2? No. Your function returns true anyway.

Every power-of-2 check using n & (n-1) needs an explicit guard for zero.

# Wrong: 0 passes
def is_power_of_two(n):
    return (n & (n - 1)) == 0

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

The same logic applies to n & -n, which isolates the lowest set bit. For n = 0, two's complement gives -0 = 0, so you get zero back. Mathematically consistent, practically useless: the "lowest set bit" of zero is undefined. Zero as a boundary is one of the most commonly missed inputs in bit problems, and your coding interview edge cases checklist should always include it.

Brian Kernighan's bit-counting loop handles zero correctly by accident (the while n: condition exits immediately). If you are testing for a specific number of set bits, zero needs its own branch.

Python's `~` Operator Returns the Wrong Number

In every fixed-width language, ~n flips all bits. For an 8-bit unsigned integer, ~0b01100110 gives 0b10011001 (102 flipped to 153). In Python, ~102 gives -103.

Not 153. Negative 103.

Python integers have no fixed width, so ~n computes -(n+1), not a bitwise complement.

Python uses arbitrary-precision integers. There is no top bit. Two's complement with infinite width defines ~n = -(n+1). If your algorithm uses ~mask to invert a bit pattern, you will compute a negative intermediate value and produce garbage. The code looks right. The types are right. The result is completely wrong.

value = 0b11001100
mask  = 0b00001111  # want to clear bottom 4 bits

# Wrong: ~mask in Python is -16, not 0b11110000
result = value & ~mask   # (-16 in decimal, not what you want)

# Correct option 1: XOR with the mask to flip those bits
result = value ^ mask    # flips only the bits in mask

# Correct option 2: AND with an explicit complement in fixed width
result = value & (~mask & 0xFF)   # 8-bit complement

Use XOR to flip specific bits rather than NOT-then-AND. If you need NOT semantics, mask the result to your working width (0xFF, 0xFFFF, 0xFFFFFFFF).

Right-Shifting a Negative Number in Java Loops Forever

Here is a bit-counting loop that looks reasonable and runs forever on negative input:

int count = 0;
int n = -1;
while (n != 0) {
    count += n & 1;
    n >>= 1;   // arithmetic right shift: fills sign bit with 1
}

Java's >> on a negative integer fills incoming bits with 1, not 0. Shifting -1 right by one gives -1 again. The condition n != 0 is never reached. Your program does not crash or time out. It just loops forever while the interviewer watches and the clock runs down.

Java has two right-shift operators:

>>: arithmetic right shift. Preserves the sign bit. -8 >> 1 = -4.
>>>: logical right shift. Always fills with 0. -8 >>> 1 = 2147483644.

For bit counting, use >>> so the number moves toward zero regardless of sign:

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += (n & 1);
        n >>>= 1;   // logical: fills with 0, terminates
    }
    return count;
}

Python has no >>>. Python's >> always floors toward negative infinity, so -2 >> 5 is -1, not 0. For set bit counting in Python, bin(n).count('1') handles non-negative integers cleanly.

C and C++ add another wrinkle: right-shifting a signed negative integer is implementation-defined. GCC and Clang on x86 use arithmetic shift, but the C standard makes no such promise. Safe C code right-shifts only unsigned values.

Shift by the Word Width and Watch It Break

What does 1 << 32 return when the type is a 32-bit int?

In C and C++, it is undefined behavior. The standard says shifting by a value greater than or equal to the bit-width of the type is undefined. In practice, x86 reduces the shift amount modulo 32, so 1 << 32 often evaluates as 1 << 0 = 1. But that is an architectural accident. A sufficiently aggressive optimizer can legally assume undefined behavior does not occur and remove surrounding code entirely. The compiler is technically correct. You are just wrong.

In Java, shifts are reduced modulo the bit-width by specification: 1 << 32 == 1 << 0 == 1 for int. Surprising, but defined. Python sidesteps this entirely: 1 << 100 gives a 101-bit integer without complaint.

The practical trap: generating an n-bit mask with (1 << n) - 1 when n equals the type width. For 32-bit C++, (1 << 32) - 1 is undefined behavior. Handle the edge case explicitly:

// Wrong for 32-bit int: undefined when n == 32
uint32_t mask = (1u << n) - 1;

// Correct: handle full-width case explicitly
uint32_t mask = (n == 32) ? 0xFFFFFFFF : (1u << n) - 1;

// Java: use long to avoid wrapping behavior on int
long mask = (1L << n) - 1;   // safe up to n == 63

The Absolute Value That Refuses to Go Positive

In 32-bit two's complement, integers run from -2,147,483,648 to 2,147,483,647. One more negative number than positive. That extra one, Integer.MIN_VALUE, has no positive counterpart in the same 32-bit range.

Negating Integer.MIN_VALUE wraps back to Integer.MIN_VALUE. Not to some nearby wrong value. Back to itself. Same bit pattern, same number, same sign.

System.out.println(-Integer.MIN_VALUE);           // -2147483648
System.out.println(Math.abs(Integer.MIN_VALUE));  // -2147483648

This is not a Java quirk. It is a property of two's complement: the bit pattern 10000000 00000000 00000000 00000000 represents -2,147,483,648, and applying negation (flip all bits, add 1) produces the same bit pattern because the positive result would overflow. Python is immune since its integers are arbitrary precision. Java, C, C++, and Rust without overflow checking are not.

Where does this appear in interviews? Any problem involving negation, reverse-bits where input can be Integer.MIN_VALUE, or absolute-value distance calculations. The test case -2147483648 is placed there specifically to catch this. Handle it explicitly:

if (n == Integer.MIN_VALUE) {
    // handle separately: MIN_VALUE cannot be negated in 32 bits
}

The XOR Swap That Erases Both Values

The XOR swap is canonical: swap two variables without a temp by doing a ^= b; b ^= a; a ^= b;. It has one failure condition. It is absolute.

XOR-swapping a variable with itself sets it to zero.

a = 5
a ^= a   # a = 5 ^ 5 = 0
a ^= a   # a = 0 ^ 0 = 0
a ^= a   # a = 0

When a and b refer to the same memory location, the first step zeroes both. Original value: gone. In practice this means passing the same array index twice. The guard is a single pointer comparison before you start:

void xor_swap(int *x, int *y) {
    if (x != y) {   // only swap distinct locations
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

On modern hardware, the XOR swap is not faster than a temp-variable swap. Compilers eliminate the temp with register allocation. Use a temp. Save the XOR swap for explaining in interviews, not for actually implementing in them.

The Fix Is Simple. Just Narrate.

Most of these bugs only surface when candidates code without narrating. You write n >>= 1, your brain skips the sign case, and you submit. In a voice interview at SpaceComplexity, you are forced to say what you are doing at each step, and "I'm shifting right to move toward zero" immediately surfaces "wait, does this work for negative n?" The narration is the diagnostic.

The bugs are not obscure. They are exactly the edge cases interviewers expect you to articulate out loud. Know your shift semantics, guard for zero, and parenthesize your bitwise comparisons. For a full reference of the patterns these bugs appear in, see the bit manipulation interview cheat sheet.

Bit Manipulation Bug Reference

Operator precedence: & and | have lower precedence than == and !=. Always parenthesize: (n & mask) == 0.
Zero and power-of-2: n & (n-1) == 0 treats 0 as a power of 2. Guard with n > 0.
Python ~n: Returns -(n+1). To flip specific bits, use XOR or mask the complement: ~n & 0xFF.
Java >> on negatives: Infinite loop. Use >>> (logical shift) to guarantee termination.
Shift past word width: Undefined in C/C++ when shift amount >= bit-width. In Java, reduced modulo 32 or 64. Stay in range explicitly.
INT_MIN negation: -Integer.MIN_VALUE == Integer.MIN_VALUE. Handle this case separately.
XOR swap aliasing: a ^= a zeroes a. Guard: only swap distinct memory locations.