Bit manipulation

You’ll recognise it when

• A handful of yes/no flags (weekdays, chosen items, visited cities) would fit in the bits of one integer.
• Every value appears twice except one, and you must find the odd one out with O(1) extra space.
• The question is about the binary form itself: count the 1s, reverse the bits, test for a power of two.
• You’re handling IP addresses or masks, where the top k bits of a 32-bit number mean something.
• The rules ban +, or ask for O(1) space where a set would be the obvious answer.

It sits next to bitmask DP, which uses these same masks as the states of a DP table. This page is the toolkit that DP is built on.

The idea

Think of an integer as a row of light switches. Switch i is worth 2^i, so 13 is 1101: switches 0, 2 and 3 are on. A bitwise operator works on every switch at once, in a single machine instruction.

One bit at a time

1 << i is a number with only bit i on. Combine it with x to test, set, clear or toggle that bit:

(x >> i) & 1        # test: 1 if bit i is on, else 0
x | (1 << i)        # set bit i
x & ~(1 << i)       # clear bit i
x ^ (1 << i)        # toggle bit i

A mask of several bits works the same way. (1 << k) - 1 is k ones, so x & 0xFF keeps the low 8 bits and (x >> 8) & 0xFF reads the next 8. That’s how an IPv4 address packs into one 32-bit number: (a << 24) | (b << 16) | (c << 8) | d.

Three tricks worth knowing by heart

• x & (x - 1) clears the lowest 1. Subtracting 1 turns the lowest 1 into a 0 and every 0 below it into a 1. The AND keeps only the bits that didn’t change. So x > 0 and x & (x - 1) == 0 means x is a power of two, and repeating it counts the 1s (below).
• x & -x keeps only the lowest 1. For 12 (1100) it gives 4 (0100): the largest power of two that divides x.
• XOR cancels pairs. a ^ a == 0, a ^ 0 == a, and the order doesn’t matter. XOR a whole list together and every value that appears twice vanishes, leaving the one that appears once. XOR the list with 0, 1, …, n and the one missing number survives the same way.

Negative numbers: two’s complement

A 32-bit int stores a negative number by wrapping round. -1 is 32 ones, because adding 1 to it carries all the way off the top and leaves 0. In general -x == ~x + 1: flip every bit, then add one. The top bit ends up as the sign, 1 for negative, so an int holds −2³¹ to 2³¹ − 1.

An unsigned type reads the same 32 bits with no sign: 32 ones is 4,294,967,295, not −1. The bits are identical; only the reading differs. That’s also why x & -x works: -x is ~x + 1, and the + 1 carries up through the flipped zeros to land exactly on x’s lowest 1. Above that bit, -x is the opposite of x, so the AND clears everything else.

How it works

We’ll count the 1 bits of x with the lowest-bit trick, often called Kernighan’s method. The graphic follows the steps as you scroll. Try editing x: a power of two takes one round, and a negative number shows its two’s complement bits.

Why it’s correct: each round removes exactly one 1 and leaves every higher bit alone, and the bits below it were already 0. So after k rounds x has k fewer 1s, and the loop stops exactly when none are left.

def popcount(x):
    """Number of 1 bits in x, read as a 32-bit value (so -1 has 32)."""
    # Python ints never run out of bits: a negative number has infinitely
    # many 1s on the left. Keep the low 32 bits, as C++ and Java would.
    x &= 0xFFFFFFFF
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

#include <cstdint>
using namespace std;

// Number of 1 bits in x. Unsigned, so x - 1 and the shifts behave the same
// for every bit pattern, and -1 converts to 32 ones.
int popcount(uint32_t x) {
    int count = 0;
    while (x != 0) {
        x &= x - 1;
        count++;
    }
    return count;
}

class Bits {
    // Number of 1 bits in x. Java ints are 32-bit two's complement, so a
    // negative x works too: -1 has 32 ones.
    static int popcount(int x) {
        int count = 0;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        return count;
    }
}

The Python version masks with 0xFFFFFFFF first. Python integers never overflow, so -1 has infinitely many 1s on the left and the loop would never finish. The mask keeps the low 32 bits, the same pattern C++ and Java store.

Why it’s O(number of 1s)

Each round clears one 1 and never creates one, so the loop runs once per 1 bit: at most 32 times for a 32-bit value, and often far fewer. Checking every bit with (x >> i) & 1 always takes 32 steps.

Each bitwise operation on a fixed-width integer is O(1). Space is O(1).

Common mistakes

while x: x &= x - 1                  # ✗ never ends for x = -1
x &= 0xFFFFFFFF                      # ✓ keep 32 bits, as C++ and Java do
x - (1 << 32) if x >> 31 else x      # ✓ read a 32-bit pattern as signed again

long long bit = 1 << 40;      // ✗ shifted as an int, before the widening
long long bit = 1LL << 40;    // ✓ shift a 64-bit one (Java: 1L << 40)
uint32_t top = 1u << 31;      // ✓ unsigned, so no sign bit to hit

while (x != 0) { x >>= 1; }    // ✗ stuck at -1 when x is negative
while (x != 0) { x >>>= 1; }   // ✓ zeros come in from the left

if (x & 1 == 0)     // ✗ x & (1 == 0), always false
if ((x & 1) == 0)   // ✓ x is even

Variations

• Adding without +. a ^ b adds each column but drops the carries, and (a & b) << 1 is exactly those carries, moved to the column they go into. Replace a, b with those two and repeat until the carry is 0. In Python, mask both to 32 bits on every round, or a negative input keeps carrying for ever.
• Enumerating subsets. With n items (up to about 20), for mask in range(1 << n) visits every subset once, and item i is in it when (mask >> i) & 1. To walk the subsets of one mask, repeat sub = (sub - 1) & mask until it reaches 0. This is where bitmask DP starts.
• Counts for every number. ones[i] = ones[i & (i - 1)] + 1 fills a table of 1-counts from 0 to n in O(n), because i & (i - 1) is smaller than i and already done.
• Building a number bit by bit. ans = (ans << 1) | (x & 1) then x >>= 1 moves the lowest bit of x onto the end of ans. After 32 rounds the bits are reversed.
• Library versions. Python x.bit_count() (3.10+) and x.bit_length(), C++20 std::popcount and std::countr_zero from <bit> (unsigned types only), Java Integer.bitCount and Integer.numberOfTrailingZeros. Use them in real code, and know the loop for interviews.