x & (x - 1) and three other bit tricks, and the one that lies about negative numbers

Bit manipulation questions look like trivia until you see that almost all of them come from four facts. Here they are, why each one works, and the shortcut that gives the wrong answer on negative numbers.

1. x & 1 tells you if a number is odd

The lowest bit is the 1s column. It's 1 for every odd number and 0 for every even one, so x & 1 is the parity without a division.

def is_odd(x):
    return (x & 1) == 1

2. x & (x - 1) clears the lowest set bit

Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1. ANDing with the original keeps everything above that bit and zeroes the rest:

x         = 1011 0100
x - 1     = 1011 0011
x & (x-1) = 1011 0000

Two classic questions fall straight out of it:

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0   # a power of two has exactly one set bit

def count_set_bits(x):                     # LeetCode 191; loops once per set bit
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

The x > 0 guard matters. Without it, 0 passes the check, because 0 & -1 is 0.

3. x ^ x == 0 finds the element without a pair

XOR is its own inverse, and order doesn't matter. XOR every element of an array where each value appears twice except one, and the pairs cancel:

from functools import reduce
from operator import xor

def single_number(nums):                   # LeetCode 136
    return reduce(xor, nums, 0)

4. Shifts multiply and divide by powers of two, mostly

x << k multiplies by 2^k and x >> k divides by 2^k. For non-negative numbers that's exactly true. For negative numbers the right shift rounds down, while integer division in Java, C and C++ rounds toward zero:

Expression	Result
-7 >> 1	-4
-7 / 2 in Java, C, C++	-3
-7 // 2 in Python	-4

So replacing / 2 with >> 1 "for speed" changes the answer on negative input in Java and C. Compilers already make that optimisation where it's safe, so writing it by hand saves nothing. In C, shifting a negative number right is technically implementation-defined; every mainstream compiler gives -4.

Recognising a bit manipulation question

The problem statement usually gives it away. Look for "single number", "number of 1 bits", "power of two", "subsets of a small set" (a bitmask of length n enumerates all 2ⁿ subsets), or a hard O(1) space limit on a counting problem.

Watching the columns

Bitwise operators are easiest to understand as a column-by-column rule, and that's easier to see than to read. I built a free bit manipulation visualizer that shows AND, OR, XOR and shifts on the binary representation step by step, with the code in Python, Java, C++, JavaScript, TypeScript and C.

Disclosure: FaangPrep is my site. This lesson and the other introductory lessons open with no account; the other visualizers are free with an account, and the pattern courses are paid. This post was drafted with AI assistance and reviewed before publishing.