Introduction to Bit Manipulation

Introduction to Bit Manipulation

Every integer your program touches is, underneath, a fixed-length row of bits — ones and zeros in hardware registers. Most of the time a language hides this from you: you write x + 1 and never think about the row. Bit manipulation is the skill of dropping down to that row on purpose — reading, setting, and combining individual bits — to solve a problem faster, with less memory, or more elegantly than arithmetic alone allows.

This page builds the foundation the rest of the module stands on: how a number is its bits, how negative numbers are encoded (two's complement), why the fixed width matters, and why a bitwise operation is one of the cheapest things a CPU can do. Assume no prior bit knowledge — we start from place values.

A number is a sum of powers of two

Decimal is base 10: the digits of 413 mean 4×100 + 1×10 + 3×1. Binary is base 2 with only two digits, 0 and 1, and the place values are powers of two. Reading a binary number is just adding up the place values wherever a bit is 1:

So 0000 1101 = 8 + 4 + 1 = 13. The rightmost bit is bit 0, the least significant bit (LSB, worth 1); the leftmost is the most significant bit (MSB). This positional meaning is the whole game — a shift left by one multiplies every place value by two, an AND keeps a bit only where both inputs agree, and so on. Keep the ruler above in mind and every trick later becomes arithmetic you can check by hand.

Unsigned vs signed

An unsigned n-bit value treats all n bits as magnitude: the range is 0 to 2ⁿ - 1. An 8-bit unsigned byte holds 0..255. But we also need negative numbers, and we refuse to spend a whole extra field on a sign — hardware wants one uniform adder. The answer the entire industry settled on is two's complement.

Two's complement — the encoding that makes hardware simple

In two's complement the top bit keeps its place value but that place value is made negative. For 8 bits the MSB is worth -128 instead of +128; the rest stay positive:

value = -128·b₇ + 64·b₆ + 32·b₅ + 16·b₄ + 8·b₃ + 4·b₂ + 2·b₁ + 1·b₀

So 1111 1011 is -128 + 64 + 32 + 16 + 8 + 2 + 1 = -128 + 123 = -5. An n-bit two's-complement integer covers -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1 — note the range is asymmetric: there is one more negative than positive, because zero uses up a positive slot.

How to negate: flip every bit, then add one — -x = ~x + 1. Here is why that is exactly right, not a coincidence. Flipping every bit turns x into (2ⁿ - 1) - x (the all-ones word minus x), because for each bit 1 - b is the flip. Add one and you get 2ⁿ - x. And 2ⁿ - x is precisely the bit pattern that, added to x, produces 2ⁿ — a 1 carried out past the top bit — which is discarded in an n-bit register, leaving 0. A number whose sum with x is 0 is -x by definition. That is the proof.

Trace -5 in 8 bits:

Why hardware loves this: subtraction disappears. a - b is just a + (-b) = a + (~b + 1), so one adder circuit does both add and subtract — no separate subtractor, no sign-magnitude special cases, no negative zero. Watch 7 - 5 done as an addition in 8 bits:

The carry out of the top bit is thrown away because the register is only 8 bits wide — arithmetic is done modulo 2ⁿ. That wrap-around is not a bug; it is the mechanism that makes the answer come out right.

Bit width: 32 and 64

The width is fixed and it matters. A Java int and a Go int32 are 32-bit two's-complement: range -2147483648 to 2147483647 (that is -2³¹ to 2³¹ - 1). A Java long / Go int64 is 64-bit. Go's plain int is platform-sized (64-bit on modern machines) — a real portability trap when a problem specifies "32-bit integer". Two consequences you will hit constantly:

• Overflow wraps silently. Integer.MAX_VALUE + 1 is Integer.MIN_VALUE, not an error. Any trick that shifts or sums near the top of the range must be reasoned about in the fixed width.
• The sign bit is bit 31 (or 63). Setting it makes the number negative. 1 << 31 is not two billion — it is -2147483648, because the bit you lit is the negative place value.

Why bit operations are O(1) — and genuinely fast

An AND, OR, XOR, NOT, or shift on a machine word maps to a single CPU instruction that processes all 32 (or 64) bits in parallel, in one cycle, with no data-dependent branching. The cost does not depend on the value — x & y costs the same whether x is 1 or 4 billion. That is the definition of O(1), and it is why replacing a loop or a hash lookup with a bit operation is such a common speed win: you collapse work that scaled with the input into one constant-time instruction. The catch is that it only works within one machine word — the O(1) is per word, so an algorithm over n bits packed into ⌈n/64⌉ words is O(n/64), not truly constant.

What this module covers

• The bitwise operators — & | ^ ~ << >> and the unsigned shift, per-operator truth tables and traps.
• Essential tricks — test/set/clear/toggle a bit; x & (x-1), x & -x, power-of-two tests, population count, low-k-bit masks — each proven, not just stated.
• XOR deep dive — the cancellation algebra behind Single Number, Missing Number, and swaps.
• Bitmasking & subset enumeration — an integer as a set, enumerating all 2ⁿ subsets and all submasks; the bridge to bitmask DP.
• Problems — popcount, Counting Bits, Missing / Single Number I–III, Reverse Bits, Sum of Two Integers, Bitwise AND of a range, Subsets, and Maximum XOR — each with the judgment call of when the bit trick is the right answer and when it is just a party trick.

Java: seeing the bits

public class BitsIntro {
    public static void main(String[] args) {
        int x = 13;
        System.out.println(Integer.toBinaryString(x));   // 1101

        int neg = -5;
        System.out.println((~5 + 1) == neg);              // true  (-x == ~x + 1)
        System.out.println(Integer.toBinaryString(neg));  // 32-bit two's complement:
                                        // 11111111111111111111111111111011

        System.out.println(neg & 0xFF);                  // 251  (low byte of -5)
        System.out.println(7 + (-5));                     // 2    (subtraction is addition)

        System.out.println(Integer.MAX_VALUE);            // 2147483647
        System.out.println(Integer.MIN_VALUE);            // -2147483648
    }
}

Go: seeing the bits

package main

import "fmt"

func main() {
	x := 13
	fmt.Printf("%b\n", x)                       // 1101

	neg := -5
	fmt.Println(^5+1 == neg)                    // true  (Go uses ^ as unary NOT)
	fmt.Printf("%032b\n", uint32(int32(neg)))   // 11111111111111111111111111111011

	fmt.Println(uint8(int8(neg)))               // 251  (low byte of -5)
	fmt.Println(7 + (-5))                        // 2

	fmt.Println(int32(2147483647))              // 2147483647   (max int32)
	fmt.Println(int32(-2147483648))             // -2147483648  (min int32)
}

Two language notes you will rely on all module: Go spells bitwise NOT as a unary ^ (not ~, which Go has no use for), so ^5 is -6 and ^5 + 1 is -5. And Go's int is 64-bit here, so to reason in exactly 32 bits you convert through int32/uint32 — the reinterpretation uint32(int32(-5)) is 4294967291, whose 32-bit pattern is the string printed above.

Takeaways

• An integer is a fixed-width row of bits; its value is the sum of place values where a bit is set.
• Two's complement makes the top bit's place value negative, so -x = ~x + 1 and one adder does add and subtract — arithmetic is modulo 2ⁿ, and the discarded carry is the point.
• Width is fixed (32 or 64); overflow wraps silently and lighting the top bit makes a value negative.
• Bitwise ops are one branchless CPU instruction per word — O(1), value-independent.

Foundations page for the Bit Manipulation module. First-principles treatment of positional binary, two's-complement negation and modular arithmetic, and machine-word cost; code verified against JDK and Go.