Bit Manipulation Field Notes

0Why bits are worth one lesson

NeetCode puts this lesson last on purpose. It is not an algorithm and not a data structure. It is a CS concept: a set of tricks that make some algorithms simpler or faster. These questions are less common in interviews than arrays or trees, but they show up, and they are hard to solve if you do not know the trick. You either know it or you do not. So learn the five operators and the four patterns below, and you are covered.

Recall from the first chapter: a bit (binary digit) is the most fundamental unit a computer uses to represent data. It holds 0 or 1. Eight bits make a byte. An int in most languages is 32 or 64 bits.

1Reading and writing binary

Binary to decimal and back

In decimal (base 10) each position is a power of 10: ones, tens, hundreds. In binary (base 2) each position is a power of 2. Counting from the right: 1, 2, 4, 8, 16, 32, ... So 001 is 1, 010 is 2, 100 is 4, and 10111 is 16 + 4 + 2 + 1 = 23. This one rule converts any binary number to decimal.

Going the other way, keep dividing by 2 and write down the remainders from last to first. 23 → 11 r1 → 5 r1 → 2 r1 → 1 r0 → 0 r1. Reading the remainders backwards: 10111. You will see this exact division in the countBits loop below, because n >> 1 is n // 2.

Python does the conversion for you

Three tools. bin() turns an int into a string that starts with 0b. int(s, 2) parses a binary string. format (or an f-string) gives you a padded string for printing traces. You can also type a binary literal directly with the 0b prefix.

bin(23)              # '0b10111'   (a string, prefix 0b)
bin(23)[2:]          # '10111'     (drop the prefix)
format(23, "08b")     # '00010111'  (pad to 8 places: the byte in the picture)
f"{23:b}"            # '10111'

int("10111", 2)      # 23          (string in base 2 → int)
int("00010111", 2)   # 23          (leading zeros are fine)
0b10111              # 23          (binary literal, no quotes)

2The five operators and their truth tables

A truth table lists every input combination and the output. For two bits there are only four combinations, so each table has four rows. The operators work on whole numbers by applying the table to each bit position separately: bit 0 with bit 0, bit 1 with bit 1, and so on.

• AND &: both bits must be 1 to get 1; otherwise 0.
• OR |: only one bit has to be 1 to get 1. Also 1 if both are 1. 0 only if both are 0.
• XOR ^ (exclusive or): 1 if only ONE of the bits is 1; otherwise 0. So 1 ^ 1 = 0. Think "are they different?".
• NOT ~ (negation): flips the bit. ~0 = 1, ~1 = 0. It takes one input, not two.
• Shift << left, >> right: slides every bit one position. Left shift multiplies by 2 (doubling). Right shift divides by 2 (halving).

The same operators in Python

This is the lesson's code, line for line. Every line here was run.

# AND
n = 1 & 1       # 1

# OR
n = 1 | 0       # 1

# XOR
n = 0 ^ 1       # 1

# NOT (negation)
n = ~n          # -2  (why not 0? see section 4: ~n is -n - 1 in Python)

# Bit shifting
n = 1
n = n << 1      # 2   (001 → 010, doubled)
n = n >> 1      # 1   (010 → 001, halved)

Left shift: slide left, a 0 comes in, the top bit can fall off

Start with 001 (decimal 1) in a 3-bit register and shift left three times. In the last step the 1 is truncated: it falls off the end and is replaced by 0. There is no room to keep it.

001 << 1 = 010   # 1 → 2
010 << 1 = 100   # 2 → 4
100 << 1 = 000   # 4 → 0   the 1 fell off the left edge

Right shift: slide right, the lowest bit falls off, the value halves

Right shift is the mirror. Every bit moves one box to the right, so every place value halves: the 16 becomes an 8, the 4 becomes a 2. The bit in the 1s box has nowhere to go and is dropped. That dropped bit is exactly the remainder of dividing by 2, which is why n >> 1 equals n // 2.

3Demonstration: count the 1 bits in 23

The lesson's worked example. 23 in binary is 10111. The plan: look at the lowest bit, then shift right so the next bit becomes the lowest, and repeat until all bits are 0.

How do we look at the lowest bit? With AND. Because 1 & 1 = 1 and 0 & 1 = 0, the expression n & 1 keeps only bit 0 and zeroes everything else. If n & 1 == 1, the lowest bit is on and we increment count. Then n = n >> 1 throws that bit away.

# Counting Bits
def countBits(n):
    count = 0
    while n > 0:
        if n & 1 == 1:      # is the lowest bit a 1?
            count += 1
        n = n >> 1          # same as n // 2: drop the lowest bit
    return count

countBits(23)   # 4

Count = 4. Check it against the byte picture in section 0: 23 has 1s in the 16, 4, 2 and 1 boxes. Four boxes.

The one-liners Python gives you

In real code use the built-ins. In an interview, write the loop first, then mention these.

bin(23).count("1")   # 4   works on every Python version
(23).bit_count()      # 4   Python 3.10+, fastest; note the parentheses around the literal
(23).bit_length()     # 5   how many bits it takes to write 23 (10111)

4Python ints, negatives, and masks

Python ints do not overflow

In C, Java, or on the CPU, an int has a fixed width (32 or 64 bits). Shift a 1 past the top and it is gone, as in the 3-bit register above. Python ints are arbitrary precision: they grow as many bits as the value needs. 1 << 100 is simply 2¹⁰⁰, a 31-digit number. Nothing falls off on the left. The only bits Python ever drops are the ones you push off the right with >>.

1 << 3        # 8, not 0: Python has no 3-bit register
1 << 100      # 1267650600228229401496703205376
(1 << 100) > 0  # True, no wrap-around to negative

# when a problem says "32-bit", cut to 32 bits yourself:
MASK = 0xFFFFFFFF        # 32 ones
(1 << 35) & MASK          # 0: bits above 31 removed

Why ~n is -n - 1

Hardware stores negative numbers in two's complement: to get -x in a fixed width, flip every bit of x and add 1. The top bit then acts as the sign. In 8 bits, 5 is 00000101, flipping gives 11111010, adding 1 gives 11111011, which is -5. Python behaves as if the number had infinitely many sign bits on the left, so ~n (flip every bit) is always -n - 1: ~0 == -1, ~1 == -2, ~23 == -24. That is why the lesson's n = ~n on 1 gives -2, not 0.

~0              # -1
~1              # -2
~23             # -24
bin(-5)         # '-0b101'  Python prints sign + magnitude, not the bit pattern
(-5) & 0xFF     # 251 = 0b11111011  the 8-bit two's complement pattern
-8 >> 1         # -4  right shift keeps the sign (arithmetic shift)
-7 >> 1         # -4  rounds toward minus infinity, exactly like -7 // 2

Masks: 1 << k selects bit k

A mask is a number whose bits are chosen so that an operator touches only the positions you want. The most useful mask is 1 << k: a single 1 in box k, zeros everywhere else. OR with it to turn bit k on. AND with its NOT to turn bit k off. AND with it to ask whether bit k is on. XOR with it to flip bit k.

def get_bit(n, k):            # 1 or 0: is bit k on?
    return (n >> k) & 1

def set_bit(n, k):            # turn bit k on   (OR with the mask)
    return n | (1 << k)

def clear_bit(n, k):          # turn bit k off  (AND with the flipped mask)
    return n & ~(1 << k)

def toggle_bit(n, k):         # flip bit k      (XOR with the mask)
    return n ^ (1 << k)

get_bit(23, 3)     # 0    10111: bit 3 is the 8s box, it is off
set_bit(23, 3)     # 31   11111
clear_bit(23, 0)   # 22   10110
toggle_bit(31, 3)  # 23   back to 10111

5Four moves that solve most bit problems

The lesson gives you the operators. Interviews ask for these four moves built from them. Each one is short enough to write from memory.

Move 1: Count the set bits

Two versions. The first is the lesson's n & 1 loop: it visits every bit. The second is Kernighan's trick: n & (n - 1) clears the lowest set bit, so the loop runs once per 1 bit and skips the 0s. Both are fine; the second is what you say when the interviewer asks "can you do better?".

def countBits(n):                 # visit every bit: O(number of bits)
    count = 0
    while n > 0:
        count += n & 1            # adds 1 or 0, same as the if in section 3
        n >>= 1
    return count

def countBitsKernighan(n):        # visit only the 1 bits: O(number of 1s)
    count = 0
    while n:
        n &= n - 1                # erase the lowest 1
        count += 1
    return count

countBitsKernighan(23)   # 4: 10111 → 10110 → 10100 → 10000 → 00000

Why does n - 1 do that? Subtracting 1 borrows from the lowest 1: that 1 becomes 0 and every 0 to its right becomes 1. Everything to the left is untouched. AND-ing the two numbers keeps the untouched left part and zeroes the rest.

Move 2: XOR cancels pairs

Two facts from the truth table: x ^ x = 0 (a number XOR itself is nothing) and x ^ 0 = x (XOR with nothing changes nothing). XOR is also commutative, so order does not matter. XOR a whole array together and every value that appears twice cancels itself out. Whatever appears once is left over. That solves "Single Number" with no hash map and O(1) extra space.

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x        # pairs cancel to 0, the loner survives
    return result

singleNumber([4, 1, 2, 1, 2])   # 4

def missingNumber(nums):     # nums holds 0..n with one missing
    result = len(nums)       # start with n, the index that has no slot
    for i, x in enumerate(nums):
        result ^= i ^ x      # every present number meets its own index and cancels
    return result

missingNumber([3, 0, 1])   # 2

Move 3: An integer is a set (bitmask)

If you have at most 20 or so items, one int can be the whole set: bit i on means "item i is in". Then set union is |, intersection is &, membership is (mask >> i) & 1, and the numbers 0 to 2ⁿ - 1 are all the subsets. This replaces the backtracking subsets generator with a plain for loop, and it is how DP over subsets stores its state.

def subsets_by_mask(items):
    n = len(items)
    out = []
    for mask in range(1 << n):                        # 0 .. 2**n - 1, every subset once
        sub = [items[i] for i in range(n) if mask >> i & 1]  # bit i on → items[i] is in
        out.append(sub)
    return out

subsets_by_mask(["a", "b", "c"])   # 8 subsets, mask 0b101 → ['a', 'c']

A = 0b0110          # {1, 2}
B = 0b0011          # {0, 1}
A | B               # 0b0111  union {0, 1, 2}
A & B               # 0b0010  intersection {1}
A & ~B              # 0b0100  difference {2}
(A >> 2) & 1        # 1       is 2 in A? yes

Move 4: Power of two in one line

A power of two has exactly one 1 bit: 1, 10, 100, 1000. Move 1 said n & (n - 1) erases the lowest 1. If erasing one 1 leaves zero, there was only one. Guard against n = 0, which also gives 0 but is not a power of two, and against negatives.

def isPowerOfTwo(n):
    return n > 0 and n & (n - 1) == 0

isPowerOfTwo(16)   # True   10000 & 01111 = 00000
isPowerOfTwo(12)   # False  01100 & 01011 = 01000
isPowerOfTwo(0)    # False  the n > 0 guard

6Big-O summary

Bit operations are the fastest thing a CPU does: one instruction each on a fixed-width int. The loops cost as many turns as there are bits, and a number n has about log₂(n) bits, so "per bit" is O(log n), not O(n).

7Mistakes to watch for

8Practice, in this order

Each of these is a five-line function once you see the trick. The point is to see the trick fast. Do them with no notes open, then compare with the moves above.

Your next step today: LeetCode 191. Write the n & 1 loop from memory, run it on 23 and check you get 4, then rewrite it with n &= n - 1 and check again.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.