Bit Manipulation Fundamentals, in depth: two's complement, masks, shifts across languages and the core idioms

How integers are stored

An n-bit unsigned integer is a sum of powers of two: bit i contributes 2 to the power i when it is 1. The byte 10110100 is 128 + 32 + 16 + 4 = 180. Bit 0 is the least significant bit; bit n-1 is the most significant.

Signed integers on every mainstream platform use two's complement. The most significant bit carries weight minus 2 to the power n-1 instead of plus, so in 8 bits 10110100 means -128 + 52 = -76. Three facts follow and are used constantly. Negation is -x == ~x + 1: flip every bit, add one. All ones is -1. And the range is asymmetric: 8 bits hold -128 to 127, so negating the most negative value overflows back to itself. C++20 and C23 require two's complement.

Addition is identical for signed and unsigned values; signedness matters for comparisons, division, widening and right shifts, which is where bugs appear.

The six operators

Useful algebra: XOR is its own inverse (a ^ b ^ b == a), a ^ a == 0 and a ^ 0 == a. AND with a mask keeps the masked bits; OR with a mask forces them on; XOR with a mask flips them. Shifting left by k multiplies by 2 to the power k as long as nothing overflows; shifting right by k divides by 2 to the power k, rounding toward negative infinity for signed values with an arithmetic shift.

Watch precedence in C, C++, Java and JavaScript: comparison operators bind tighter than bitwise ones, so x & 1 == 0 parses as x & (1 == 0) and is always 0. Always parenthesize: (x & 1) == 0. Python avoids this particular trap because its comparisons bind looser than the bitwise operators.

Shifts, and where languages disagree

Right shifts come in two kinds. A logical shift fills with zeros. An arithmetic shift copies the sign bit, so negative numbers stay negative. Languages map these differently, and the shift count has its own rules.

The C undefined-behavior cases bite in real code. 1 << 31 on a 32-bit int overflows the sign bit, which is undefined in C; write 1u << 31. x << n with n equal to the type's width is undefined, and on x86 the hardware masks the count so it often silently returns x, while an optimizing compiler may assume it never happens. Shifting a negative value left is undefined in C. The rule that avoids all three: do bit manipulation on unsigned types of explicit width (uint32_t, uint64_t) and keep shift counts below the width.

Arithmetic shift is not the same as division in C: -7 >> 1 is -4, but -7 / 2 is -3 because C division truncates toward zero. Python's // floors, so there the two agree.

Masks: single bits and packed fields

A mask is an integer whose 1 bits select positions. Four operations cover single bits:

#include <stdint.h>

static inline uint32_t set_bit(uint32_t x, unsigned i)    { return x |  (UINT32_C(1) << i); }
static inline uint32_t clear_bit(uint32_t x, unsigned i)  { return x & ~(UINT32_C(1) << i); }
static inline uint32_t toggle_bit(uint32_t x, unsigned i) { return x ^  (UINT32_C(1) << i); }
static inline int      test_bit(uint32_t x, unsigned i)   { return (x >> i) & 1u; }

/* A field of `width` bits starting at bit `pos` (width < 32). */
static inline uint32_t get_field(uint32_t x, unsigned pos, unsigned width) {
    return (x >> pos) & ((UINT32_C(1) << width) - 1);
}
static inline uint32_t set_field(uint32_t x, unsigned pos, unsigned width, uint32_t v) {
    uint32_t m = ((UINT32_C(1) << width) - 1) << pos;
    return (x & ~m) | ((v << pos) & m);
}

(1 << w) - 1 builds w low ones. set_field clears the field before ORing, and masks v so an oversized value cannot spill into neighbouring fields.

The core idioms

Nearly every bit trick is a combination of a few identities. They rely on how subtracting one changes a number: it flips the lowest set bit to 0 and every 0 below it to 1. The figure above shows this on 180.

Population count follows from the first identity: Kernighan's loop clears one set bit per iteration:

def popcount(x: int) -> int:
    n = 0
    while x:
        x &= x - 1
        n += 1
    return n

assert popcount(180) == 4 == (180).bit_count()   # int.bit_count needs Python 3.10+

The second identity is how a Fenwick tree moves between nodes: i += i & -i climbs to the next node that covers i, and i -= i & -i walks down the prefix. In C, compute x & -x on unsigned values: negating the most negative signed int is overflow.

Integers as sets

An n-bit integer is a subset of {0, ..., n-1}: bit i is 1 if element i is in the set. Union is OR, intersection is AND, difference is a & ~b and size is a popcount, each a single instruction for n up to 64, which is why bitmask dynamic programming over subsets is practical for n around 20.

Two enumeration patterns come up repeatedly. Enumerating all submasks of a mask m uses the subtract-and-mask step, and summed over every m of n bits it visits 3 to the power n pairs, not 4 to the power n. Gosper's hack steps to the next larger integer with the same popcount, which enumerates all k-element subsets in increasing order:

def submasks(m):
    s = m
    while True:
        yield s
        if s == 0:
            break
        s = (s - 1) & m

print([bin(s) for s in submasks(0b1011)])
# ['0b1011', '0b1010', '0b1001', '0b1000', '0b11', '0b10', '0b1', '0b0']
n = 10
print(sum(1 for m in range(1 << n) for _ in submasks(m)), 3 ** n)   # 59049 59049

def next_same_popcount(x):          # Gosper's hack, x > 0
    c = x & -x
    r = x + c
    return (((r ^ x) >> 2) // c) | r

v, out = 0b0111, []
for _ in range(5):
    out.append(bin(v)); v = next_same_popcount(v)
print(out)   # ['0b111', '0b1011', '0b1101', '0b1110', '0b10011']

Python and JavaScript specifics

Python integers are unbounded, so there is no fixed width and ~5 is -6 (it is -x - 1). To emulate a 32-bit unsigned value, mask after every operation that can grow the number: (a + b) & 0xFFFFFFFF, (x << k) & 0xFFFFFFFF. To reinterpret as signed, subtract 2 to the power 32 when bit 31 is set:

def to_signed32(u: int) -> int:
    u &= 0xFFFFFFFF
    return u - (1 << 32) if u & 0x80000000 else u

print(~5, (~5) & 0xFF, -1 & 0xFFFFFFFF)            # -6 250 4294967295
print(to_signed32(0xFFFFFFFE), to_signed32(0x80000000))   # -2 -2147483648

JavaScript numbers are doubles, but every bitwise operator first converts its operands to 32-bit signed integers, so bits above 31 are silently dropped and 0xFFFFFFFF | 0 is -1. Use x >>> 0 to view the result as unsigned, and BigInt for wider masks. In Java, 1 << 40 on an int is 1 << 8 because the count is masked; write 1L << 40.

What the hardware gives you

Modern CPUs implement the expensive loops above as single instructions: population count (x86 POPCNT, ARM via the vector CNT instruction), count trailing zeros and count leading zeros (x86 TZCNT/LZCNT, ARM CLZ and RBIT), and on x86 with BMI2 the parallel bit extract and deposit instructions PEXT and PDEP, which gather or scatter the bits selected by a mask. Reach them through portable functions rather than inline assembly: C++20's <bit> header (std::popcount, std::countr_zero, std::countl_zero, std::has_single_bit, std::bit_ceil), GCC and Clang's __builtin_popcount and __builtin_ctz, Java's Integer.bitCount and Long.numberOfTrailingZeros, and Python's int.bit_count and int.bit_length. Note that __builtin_ctz(0) is undefined, while std::countr_zero(0) returns the width. Compilers emit POPCNT only when the target flags allow it, such as -march=native.

These are the building blocks of compressed bitmaps such as Roaring bitmaps, whose set operations reduce to word-wide AND/OR plus popcount.

Worked example: a packed telemetry record

A telemetry system sends compact event records. Each record packs four fields into one 32-bit word: a 4-bit event type in bits 28-31, a 12-bit device id in bits 16-27, a 1-bit error flag in bit 15 and a 15-bit value in bits 0-14. Encoding type 9, device 1234, error set and value 20000:

def pack(kind, device, err, value):
    assert 0 <= kind < 16 and 0 <= device < 4096 and err in (0, 1) and 0 <= value < 32768
    return (kind << 28) | (device << 16) | (err << 15) | value

def unpack(w):
    return (w >> 28) & 0xF, (w >> 16) & 0xFFF, (w >> 15) & 1, w & 0x7FFF

w = pack(9, 1234, 1, 20000)
print(hex(w), unpack(w))   # 0x94d2ce20 (9, 1234, 1, 20000)

The receiver is written in Java, and the word arrives as an int. Because bit 31 is set (type 9 is 1001 in binary), the int is negative, and w >> 28 returns -7, not 9: the arithmetic shift copied the sign bit. The fix is (w >>> 28) & 0xF; the trailing mask makes the code correct even if someone later changes the shift. This exact bug, a sign bit in the top field, is common in protocol parsers; always round-trip test values that set the top bit.

The asserts in pack matter too: a device id of 5000 would otherwise corrupt the type field.

Trade-offs

Bit tricks trade readability for speed and space. A uint64_t set beats a hash set of small integers but caps you at 64 elements. Packed records need versioning when a field must grow. XOR swap is slower than a temporary and breaks when both operands alias. Use bit manipulation where the data really is a set of flags or a packed format, or where a profiler says the loop matters, wrap it in named helper functions, and test the boundaries: zero, all ones, the top bit and the maximum field value. Probabilistic structures such as Bloom filters are a good next example of these operations doing real work.

What to do next

1. Write the four single-bit helpers and the field get/set pair in your main language, using unsigned fixed-width types.
2. Check your language's shift rules: what happens at a count equal to the width, and what right shift does to negatives.
3. Implement Kernighan popcount and compare it with the built-in on random inputs.
4. Solve one bitmask DP problem over subsets, then rewrite its inner loop with submask enumeration.
5. Pack and unpack a record across two languages, with a test value that sets the top bit.
6. Replace one hash set of small integer flags in real code with a bitmask, and measure before keeping it.