Bit manipulation

Every integer is a row of bits, and bit manipulation works on those bits directly. It comes up when the data really is bits, like IP addresses, permissions or compressed data, and in puzzles where a bit trick turns an O(n) space answer into O(1).

A few moves cover most problems:

• Check bit i: (x >> i) & 1. Set it: x | (1 << i). Clear it: x & ~(1 << i).
• A mask keeps only the bits you care about: x & 0b111 keeps the last three.
• x & (x - 1) clears the lowest 1 bit. If the result is 0, x was a power of two.
• x ^ x is 0, so XOR-ing a list where everything appears twice except one number leaves that number.

Checking whether an IP address is inside a CIDR block, like 192.168.1.0/24, is a mask in action:

def ip_to_int(ip):
    a, b, c, d = (int(part) for part in ip.split("."))
    return (a << 24) | (b << 16) | (c << 8) | d


def in_block(ip, cidr):
    base, bits = cidr.split("/")
    bits = int(bits)
    mask = (0xFFFFFFFF << (32 - bits)) & 0xFFFFFFFF  # first bits ones
    return ip_to_int(ip) & mask == ip_to_int(base) & mask

/24 means the first 24 bits have to match. The mask has 24 ones followed by 8 zeros, so AND-ing both addresses with it keeps just the part that has to match.

Bit tricks are fast and compact, but they're hard to read. In an interview, write a small helper with a clear name, like in_block, rather than a one-line puzzle.

• Write numbers in binary on the side while you work. It catches most mistakes.
• Check edge cases like /0 and /32, zero, and the largest value.
• Explain each trick in plain words as you use it.

Packing small numbers into fewer bits

You need to store a long list of numbers that are all between 0 and 7. A normal integer uses 32 or 64 bits each, but 0 to 7 fits in 3 bits.

1. Three bits hold 8 values, 000 to 111, so each number needs exactly 3 bits.
2. Pack [5, 3, 7, 0] by shifting what you have left 3 places and OR-ing in the next number: 5 is 101, then 101011, then 101011111, then 101011111000.
3. That's 12 bits for four numbers, instead of 128 bits as four 32-bit integers.
4. To read the number at position i, shift right so it lands at the end, then mask with 0b111. Position 1 of 4: shift right by 3 × (4 - 1 - 1) = 6, giving 101011, and 101011 & 111 is 011, which is 3.
5. The decoder has to know how many numbers there are and how many bits each uses, so store those in a small header in front.
6. If one value doesn't fit, like a 9, either use more bits for everything or store the big values separately. Real formats pick the bit width per block of numbers.
7. Test it by packing and unpacking random lists, including empty ones, and checking you get the same list back.

Things interviewers tend to ask once you've brought this up.

How do you count the 1 bits in a number?

Keep doing x &= x - 1, which clears the lowest 1 bit, and count how many times until x is 0. Python also has int.bit_count().

Every number appears twice except one. Find it in O(1) space.

XOR them all. Pairs cancel to 0, and what's left is the single one.

How would you generate every subset of a list?

Count from 0 to 2ⁿ - 1. Each number's bits say which items are in that subset.

How do you store permissions compactly?

Give each permission a bit, like read = 1, write = 2, delete = 4. A user's permissions are one number, and checking one is a single AND.

• Forgetting that Python's ~ gives a negative number.
• Getting operator precedence wrong. In C, Java and JavaScript, == binds tighter than &, so a & b == c doesn't do what it looks like. Parentheses make it clear in any language.
• Off-by-one errors in shift amounts.
• Not testing the edges, like /0 and /32 for CIDR blocks.
• Writing a clever one-liner nobody can follow, including you.

• TriesStore words by prefix so autocomplete and prefix lookups are fast.
• Hash maps and sliding windowsSwap nested loops for a single pass.
• Binary searchCut the search in half, even when you're searching for an answer.