Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Bit Manipulation

Medium6 min readdsabit-manipulation

Introduction to Bit Manipulation

Bit manipulation problems test something different from most interview problems. Where arrays and strings test pattern recognition and algorithmic structure, bit manipulation tests whether you can think at the level of individual binary digits. The problems are often short - five or ten lines of code - but the reasoning required to write those lines is dense.

This chapter gives you the foundation. The operators, the common tricks, the mental models. Most bit-manipulation problems are variations on a small set of patterns; once you've internalized the patterns, the problems become routine.

Why Bit Manipulation Matters

There are three reasons interviewers ask bit-manipulation questions:

1. It tests low-level thinking. Many candidates are comfortable with high-level abstractions (lists, maps, classes) but struggle when forced to reason at the bit level. The discomfort itself is the test.

2. The optimal solutions are often dramatically faster. A problem solved with a hash map in O(n) time and O(n) space might also be solvable with XOR in O(n) time and O(1) space. The bit-level solution is often more elegant and uses fewer resources.

3. It comes up in real systems. Bit manipulation appears in compression algorithms, networking protocols, cryptography, graphics, and any code where bits represent state efficiently (flags, bitmaps, bloom filters).

For interviews, bit manipulation problems are typically 10-20% of the questions you'll face. Not central, but not negligible.

The Operators

Six bitwise operators that you'll use constantly.

Two right-shift operators exist in Java specifically because the language has signed integers:

• >> preserves the sign bit ("arithmetic shift"). -4 >> 1 = -2.
• >>> fills with zeros ("logical shift"). -4 >>> 1 = 2147483646.

For most bit-manipulation problems, use >>> when you want to treat the number as unsigned. Use >> when sign matters (rare in interview problems).

The Five Patterns Worth Memorizing

These are the bit tricks that come up over and over.

Pattern 1: Check if bit k is set

boolean isSet = (n & (1 << k)) != 0;

1 << k produces a mask with only bit k set. AND-ing with n isolates that bit. If the result is non-zero, bit k of n is 1.

Pattern 2: Set bit k

n = n | (1 << k);

OR with the mask. Bits already 1 stay 1; bit k becomes 1.

Pattern 3: Clear bit k

n = n & ~(1 << k);

~(1 << k) is a mask with all bits 1 except bit k. AND-ing with n clears bit k while leaving others intact.

Pattern 4: Toggle bit k

n = n ^ (1 << k);

XOR flips bit k. Bits where the mask is 0 are unchanged; the bit where the mask is 1 flips.

Pattern 5: Isolate the lowest set bit

int lowest = n & (-n);

This one looks magical until you see why it works. In two's-complement representation, -n equals ~n + 1. When you AND n with -n, all bits above the lowest set bit cancel out (because ~n inverts them and the +1 only carries up through the trailing zeros). The result is a mask with only the lowest set bit.

Example: n = 0b101100. -n = ...11010100. n & -n = 0b000100.

This trick is the basis for Fenwick trees (Section 27) and many bit-counting tricks.

XOR - The Most Important Operator

XOR shows up in more interview problems than the other operators combined, so it deserves a section of its own.

Properties of XOR

These four properties combined give XOR its power. The self-inverse property means XOR is its own inverse - applying XOR twice cancels out. The commutative and associative properties mean the order of XOR operations doesn't matter.

graph LR
    A["a"] -->|"XOR with b"| B["a ^ b"]
    B -->|"XOR with b again"| A
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This diagram shows the self-inverse property of XOR. Starting from a, XOR-ing with b gives a XOR b. XOR-ing with b again recovers a. Applying the same XOR twice cancels out.

The Canonical XOR Trick: Find the Unique Element

Suppose you have an array where every element appears twice except one. The unique element can be found in O(n) time and O(1) space by XOR-ing all elements together.

int unique = 0;
for (int num : nums) unique ^= num;
// unique now holds the lone element

Why does this work? Pair-XOR cancels (a ^ a = 0), so all the duplicated elements vanish. The remaining XOR of 0 with the unique element yields the unique element itself.

This is the basis for Single Number (topic 8.2), Missing Number (8.3), Set Mismatch (8.4), and many other problems in this section.

Common Tricks That Aren't Obvious

A few tricks worth knowing because they appear in interview problems.

Count bits using Brian Kernighan's algorithm

int count = 0;
while (n != 0) {
    n &= n - 1;  // Clear the lowest set bit
    count++;
}

n - 1 flips all bits from the lowest set bit downward. AND-ing with n clears that lowest bit. Each iteration removes one bit. Runs in O(set bits) instead of O(total bits) - useful when set bits are sparse.

Check if a number is a power of two

boolean isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);

Powers of two have exactly one set bit. n - 1 flips all bits from that bit downward (so the set bit becomes 0 and lower zeros become 1). AND with n gives 0 iff n was a power of two.

Swap without a temp variable

a ^= b;
b ^= a;  // b is now (a ^ b) ^ b = a
a ^= b;  // a is now (a ^ b) ^ a = b

Cute, but the temp variable version is clearer and just as fast in practice. Worth mentioning in interviews; don't use in production code.

Multiply or divide by 2 with shifts

int doubled = n << 1;     // n * 2
int halved  = n >> 1;     // n / 2 (rounds down for positive numbers)

Modern compilers do this optimization automatically, so you rarely need to write it manually. Useful in interview problems where you want to make the bit-level structure explicit.

Two's Complement and Negative Numbers

Java's integers are 32-bit two's complement. This affects bit manipulation in two important ways.

The leftmost bit is the sign bit. Bit 31 of a 32-bit int is 1 for negative numbers, 0 for non-negative.

Negation flips bits and adds 1. -n equals ~n + 1. This is why n & -n isolates the lowest set bit.

For most interview problems, you can treat integers as their bit patterns without worrying about sign. Use >>> for logical right shifts. Use 0xFFFFFFFF (or -1) as the "all bits set" mask.

What This Section Covers

The 12 problem topics in Module 8 are organized by technique:

• XOR Tricks (5 topics): Single Number, Missing Number, Set Mismatch, Single Number II, Single Number III. These teach the cancellation property of XOR and its generalizations.
• Bit Counting (3 topics): Number of 1 Bits, Counting Bits, Hamming Distance. These teach techniques for efficient bit counting.
• Bit Masking (4 topics): Power of Two, Reverse Bits, Bitwise AND of Numbers Range, Sum of Two Integers. These teach how to use masks for state representation and arithmetic.

By the end of Module 8, you'll have seen the standard repertoire of bit-manipulation techniques. The patterns reappear constantly in later modules - bit DP, subset enumeration, Fenwick trees, hash-set replacements, and many others.

A Note on Difficulty

Bit manipulation has a steep learning curve. The first time you see XOR cancel duplicates, it feels like a magic trick. The second time, it's still surprising. By the fifth or sixth problem, it becomes routine.

If a problem in this section feels impossible, take a step back and work through the bit patterns by hand for small examples. Write the binary representations of the inputs. Trace what each operation does bit by bit. The mechanics will become clear, and the high-level pattern will follow.

Let's start with the canonical XOR problem: Single Number.

Back to DSA Mastery - Interview Prep, End to End