Bit Manipulation Fundamentals

Why Bit Manipulation Matters

Bit manipulation looks like a niche skill until you notice how often software quietly uses it. Permission systems store read, write, and execute as independent switches inside a single integer. Network protocols pack flags into headers because sending one compact machine word is cheaper than shipping a pile of booleans. Graphics, compression, cryptography, schedulers, and operating systems all rely on the fact that a computer ultimately stores state as bits. Learning the operations directly gives you a way to reason one layer closer to the hardware instead of treating integers like mysterious black boxes.

Interview problems use bit manipulation for a different reason: it rewards precise thinking. A brute-force solution often loops over many possibilities or stores extra memory, while a bit trick can encode the same idea in one arithmetic identity. That is not magic. It only feels magical when the underlying representation is skipped. Once you understand what each bit position means, expressions like n & (n - 1) or x ^ y stop being memorization targets and become short sentences about binary structure.

Thinking in Binary

A binary number is just a row of switches. The rightmost switch represents ones, the next represents twos, then fours, eights, sixteens, and so on. The decimal number 26 is 11010 in binary because it contains one sixteen, one eight, no four, one two, and no one. When you change a single bit, you are not changing the whole number at random. You are adding or removing exactly one power of two. That is why bitwise operations are so predictable once you translate each position back into its weight.

The core operators work bit by bit. AND keeps a 1 only where both inputs have a 1. OR keeps a 1 where at least one input has a 1. XOR keeps a 1 only where the bits differ. NOT flips every bit. Left shift moves bits to the left and usually multiplies by two for each shift as long as you stay within the integer width. Right shift moves bits to the right and usually divides by two, discarding low-order information. The operators are mechanical, so the best way to trust them is to run one concrete example all the way through.

26 = 11010
14 = 01110

26 & 14 = 01010 = 10
26 | 14 = 11110 = 30
26 ^ 14 = 10100 = 20
^26      = ...00101 in a 5-bit toy world, but on real machines NOT flips every stored bit
26 << 1  = 110100 = 52
26 >> 2  = 00110  = 6

Common Bit Tricks and Why They Work

Most interview tricks come from building a mask and then combining it with AND, OR, or XOR. Suppose you want to inspect bit k. The number 1 << k creates a mask with exactly one 1 at that position. AND the original number with that mask and every other position is forced to zero, so the result tells you whether bit k was present. To set a bit, OR with the mask. To clear a bit, AND with the inverse of the mask. To toggle a bit, XOR with the mask because XOR flips only the positions where the mask contains a 1.

1. Check bit k: n&(1<<k) != 0
2. Set bit k: n | (1<<k)
3. Clear bit k: n & ^(1<<k)
4. Toggle bit k: n ^ (1<<k)

Two famous identities are worth understanding deeply. First, n & -n isolates the lowest set bit. In two’s complement arithmetic, negating n flips the bits and adds one, which means every trailing zero stays zero and the first trailing one becomes the only shared one-position between n and -n. Second, a positive power of two has exactly one set bit. If you subtract one, every lower bit becomes 1 and the original set bit becomes 0. Therefore n & (n - 1) equals 0 exactly when n had only one set bit to begin with.

Worked Example: A Permission Mask

Imagine a file service stores five permissions in one integer: delete = bit 4, share = bit 3, execute = bit 2, write = bit 1, read = bit 0. The mask 10011 means delete, write, and read are enabled. In decimal that mask is 19. If an admin asks whether sharing is currently enabled, you do not need to inspect every permission separately. Build the share mask 01000, compute 10011 & 01000, and get 00000. Because the result is zero, share is currently off.

Now suppose the admin wants to enable share, disable delete, and toggle execute. Start with 10011. Setting share means OR with 01000, producing 11011. Clearing delete means AND with the inverse of 10000, producing 01011. Toggling execute means XOR with 00100, producing 01111. That final mask corresponds to share, execute, write, and read enabled. Notice how each operation changes exactly one conceptual switch even though everything is packed into a single integer.

Pitfalls and Pattern Recognition

Bit manipulation is most useful when the problem naturally talks about independent yes-or-no states, parity, powers of two, or compact subsets. It is less useful when you are forcing it into a problem that is really about strings, trees, or dynamic programming. A good interview heuristic is to listen for phrases like “flags,” “exactly one unique value,” “subsets,” “count set bits,” or “divide by two repeatedly.” Those phrases usually mean the binary representation itself contains the shortcut.

Also remember that cleverness is not the same thing as clarity. A bit trick is valuable when you can explain the invariant in plain language. If you cannot explain why it works on paper, you will struggle to adapt it when the problem changes slightly. The goal of this lesson is not to collect hacks. The goal is to build a mental model where an integer is a row of labeled switches, and each operator tells you exactly which switches survive, which turn on, and which flip.

Practice Problems

Quiz

Summary

• Binary numbers are weighted switches, not mysterious symbols.
• AND, OR, XOR, NOT, and shifts are predictable once you read them column by column.
• Masks let you check, set, clear, and toggle individual flags efficiently.
• n & -n isolates the lowest set bit, and n & (n - 1) removes it.
• Power-of-two tests and flag manipulation are simple consequences of bit structure, not memorized tricks.