34

Bit Manipulation

Every int is 32 switches. Learn six moves and a whole family of problems becomes one line.

intermediate~60 min7 simulations11 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Big-O · Java Toolkit · Hashing · Backtracking

01 · why it exists

Why this exists, and the weight it carries

since1945

Two's complement integers

John von Neumann (EDVAC report); the EDSAC team at Cambridge

In his June 1945 "First Draft of a Report on the EDVAC", von Neumann stored a negative number through the complements of its digits, working modulo a power of two. To subtract, every digit is replaced by its complement and one unit is added in the last place — what we now call two's complement. Cambridge's EDSAC (1949) stored its numbers in two's complement too. Java's language spec fixes it for good: every int is a 32-bit signed two's-complement integer.

the problem it solvedOne adder for both addition and subtraction, and a single zero, instead of separate sign handling.

its jobs today

  • Every Java byte, short, int and long is stored this way (JLS §4.2), so one adder circuit handles +, − and negative numbers alike.
  • Wrap-around you can rely on: Integer.MAX_VALUE + 1 == Integer.MIN_VALUE, which hash functions and checksums depend on.

the weight it carries

Illustrative: 32 bits give 2³² = 4,294,967,296 patterns. Two's complement spends them on −2,147,483,648 … 2,147,483,647: exactly one zero, and one more negative than positive. That spare negative is why Math.abs(Integer.MIN_VALUE) is still negative.

without it

With sign-and-magnitude there would be two zeros (+0 and −0), and the CPU would need separate circuits to subtract and to compare signed numbers.

when · why · how

when
Whenever negative numbers meet bit operators: >> vs >>>, x & -x, overflow checks, Integer.MIN_VALUE edge cases.
why
Bit 31 counts as −2³¹ and −x = ~x + 1. Knowing that turns negative-number bit tricks from magic into arithmetic.
how
Integer.toBinaryString(-1) shows 32 ones; use >>> to treat the bits as unsigned; Integer.toUnsignedLong(x) reads them as 0 … 2³² − 1.

02 · plain english

The idea in 30 seconds

A Java int is a row of 32 bits. Operators like &, |, ^ and shifts act on all 32 at once, in one CPU step.

With a mask (1 << k) you can read, set, clear or flip any single bit in O(1).

Two facts unlock most interview problems: a ^ a = 0 (pairs cancel) and x & (x − 1) erases the lowest 1-bit.

picture this

An int is like an app's Settings → Permissions screen with 32 toggles. A mask names the toggles you care about: OR switches them on, AND-NOT switches them off, XOR flips them, and AND tells you which ones are on.

03 · remember

What you must know

  • Java int = 32 bits in two's complement. Bit 31 is the sign bit. Range is −2³¹ … 2³¹−1, and -x == ~x + 1.
  • The operators: & (both 1), | (either 1), ^ (different), ~ (flip all), << (shift left, ×2), >> (shift right, copies the sign bit), >>> (shift right, fills with 0).
  • With mask = 1 << k: check (x >> k) & 1, set x | mask, clear x & ~mask, toggle x ^ mask.
  • x & (x − 1) erases the lowest 1-bit. So n > 0 && (n & (n − 1)) == 0 means "power of two", and looping it counts 1-bits.
  • x & -x keeps only the lowest 1-bit (e.g. 12 = 1100 → 4 = 0100). It splits numbers into two groups in Single Number III.
  • XOR rules: a ^ a = 0, a ^ 0 = a, and order does not matter. XOR a whole array and every pair cancels.
  • An int is also a set of the numbers 0–31 (bit i on = i is in the set). Counting mask from 0 to 2ⁿ − 1 visits every subset of n items.
  • Bit operations are O(1) on a fixed-width word. A loop over the bits of a value V is O(log V), which is at most 32 steps for an int.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Check, set, clear, toggle on 8 bits

The mask lights up bit k. Watch which bits each operator touches, and which it leaves alone.

loading simulation…
sim

>> vs >>> on a negative number

Both slide bits right. `>>` copies the sign bit into the gap. `>>>` always fills it with 0.

loading simulation…
sim

Count 1-bits with n & (n − 1)

Each step erases exactly one 1-bit, so the loop runs once per 1-bit instead of 32 times.

loading simulation…
sim

XOR fold: pairs cancel

Each number flips some bits of x. A number seen twice flips the same bits back, so only the loner is left.

loading simulation…
sim

Counting Bits: a DP built from i >> 1

i and i >> 1 have the same bits except the last one, so ans[i] = ans[i >> 1] + (i & 1).

loading simulation…
sim

Every subset is a number

Bit i of the mask says "take nums[i]". Counting 0, 1, 2, … lists every subset exactly once.

loading simulation…
sim

Binary addition, column by column

Each column adds two digits and the carry: write sum % 2, carry sum / 2. A CPU's adder follows the same two rules.

loading simulation…

05 · cost

Time & space, explained

Cost of the core moves (int = 32 bits, long = 64)
Timewhy
&, |, ^, ~, <<, >>, >>>O(1)One CPU instruction that works on all 32 (or 64) bits in parallel.
Check / set / clear / toggle bit kO(1)One shift to build the mask plus one operator.
Integer.bitCount, numberOfTrailingZeros, highestOneBitO(1)Fixed-width tricks on one word. bitCount is a HotSpot intrinsic: it may compile to one POPCNT instruction on x86-64 CPUs that have it.
Count 1-bits with n &= n − 1O(k), k = number of 1-bitsEach loop erases one 1-bit. At most 32 for an int.
Loop over every bit of a value VO(log V)V has about log₂V bits. For an int that is at most 32 steps, so O(1) in practice.
Enumerate all subsets of n items with masksO(n · 2ⁿ)2ⁿ masks, and building each subset checks n bits. n ≈ 20 is the practical limit (about 2·10⁷ steps).
Enumerate every submask of every maskO(3ⁿ)Each item is in neither, only the mask, or both. That gives 3 choices per item.
Bit tricks vs the usual tools
TimeExtra spacewhy
Find the unpaired number: HashSetO(n)O(n)Stores up to n/2 values that are still waiting for a partner.
Find the unpaired number: XOR foldO(n)O(1)One int accumulator. Pairs cancel to 0.
Set of small ints (≤ 64): long maskO(1) per op8 bytesAdd, remove, contains, union and intersect are each one operator.
Set of ints 0…n−1: boolean[n]O(1) per op~n bytesThe JVM typically uses one byte per boolean.
Set of ints 0…n−1: BitSetO(1) per op~n/8 bytesOne bit per number, packed into a long[]. cardinality() is O(n/64).

06 · java

Raw vs Collections Framework

One bit at a time: raw operators vs Integer helpers

javaraw operatorsjava.util.*
class BitOps {    // k is the bit position: 0 = rightmost (least significant) bit.    static boolean isSet(int x, int k) { return ((x >> k) & 1) == 1; }    static int set(int x, int k)       { return x | (1 << k); }    static int clear(int x, int k)     { return x & ~(1 << k); }    static int toggle(int x, int k)    { return x ^ (1 << k); }    static int dropLowest(int x)       { return x & (x - 1); }    static int lowestBit(int x)        { return x & -x; }}
  • Write the raw operators when the trick is the question (Power of Two, Number of 1 Bits). Interviewers want to see n & (n − 1).
  • Use Integer.bitCount, numberOfTrailingZeros and similar helpers when bits are only a step. They are tested and fast, and every one has a Long. twin.
  • Integer.toBinaryString drops leading zeros for positive numbers. Pad with String.format("%32s", …).replace(' ', '0') when debugging.
  • Java has no unsigned int. When you need to read the bits as unsigned, use >>>, Integer.toUnsignedLong, Integer.toUnsignedString or Integer.parseUnsignedInt.

A set of small numbers: int mask vs BitSet

javaint as a set (0–31)java.util.*
class MaskSet {    int mask = 0; // bit i is 1  <=>  i is in the set (0 <= i < 32)     void add(int i)          { mask |= 1 << i; }    void remove(int i)       { mask &= ~(1 << i); }    boolean contains(int i)  { return (mask & (1 << i)) != 0; }    int size()               { return Integer.bitCount(mask); }    int union(int other)     { return mask | other; }    int intersect(int other) { return mask & other; }}
  • An int holds a set of 0–31 and a long holds 0–63. Union is |, intersection is &, and size is bitCount. Masks also make good HashMap keys and DP indices.
  • BitSet grows to any size and stores one bit per number in a long[], so it is 8× smaller than boolean[]. It has and, or, xor, andNot, cardinality and nextSetBit.
  • EnumSet is the same idea for enums. For enums with up to 64 constants it is backed by a single long (RegularEnumSet).

Shifts: >>, >>> and <<

javathe three shiftsjava.util.*
class Shifts {    static int arithmetic(int x, int k) { return x >> k; }  // copies the sign bit in    static int logical(int x, int k)    { return x >>> k; } // always fills with 0s    static int left(int x, int k)       { return x << k; }  // k is taken mod 32!}
  • >> is an arithmetic shift. It copies the sign bit, so -16 >> 2 == -4, which is division by 4 rounded toward −∞.
  • >>> is a logical shift. It always fills with 0, so -1 >>> 31 == 1. Use it whenever you treat an int as 32 raw bits.
  • The shift distance is taken mod 32 for int (mod 64 for long). So 1 << 32 == 1, not 0. Write 1L << k when k can be 31 or more.
  • byte, short and char are promoted to int before shifting. Mask with b & 0xFF to get the unsigned value of a byte.
Java API you will actually use
calldoescost
Integer.bitCount(x) / Long.bitCount(x)Number of 1-bits (popcount)O(1)
Integer.highestOneBit(x)Only the highest 1-bit kept (0 for 0). 12 → 8O(1)
Integer.lowestOneBit(x)Only the lowest 1-bit kept, same as x & -x. 12 → 4O(1)
Integer.numberOfTrailingZeros(x)Index of the lowest 1-bit (32 for 0)O(1)
Integer.numberOfLeadingZeros(x)Zeros before the highest 1-bit. 31 − nlz(x) = floor(log₂ x)O(1)
Integer.reverse(x)Reverse all 32 bitsO(1)
Integer.toBinaryString(x)Binary text without leading zeros (negatives show all 32 bits)O(32)
Integer.parseUnsignedInt(s, 2)Parse 32 binary digits even when the first one is 1O(len)
Integer.toUnsignedLong(x)Read the bits of x as 0 … 2³²−1O(1)
new BitSet(n); set / get / clear / flip(i)Growable bit array, one bit per indexO(1) each
bitSet.cardinality() / nextSetBit(i)Count the 1s / find the next 1 at or after iO(n/64)

A set of at most 32 (or 64) small values, e.g. visited cities, letters a–z

→ int / long mask

O(1) set operations, and the mask itself can be a DP index or map key.

A large set of flags over 0…n−1 (a sieve, a visited array)

→ BitSet

8× less memory than boolean[] and fast bulk and/or.

Count, find or reverse bits as a helper step

→ Integer.bitCount / numberOfTrailingZeros / reverse

Correct on every edge case (0, negatives) and usually compiled to single instructions.

The interviewer asks how it works

→ Raw operators

n & (n − 1), x & -x and the XOR fold are what is being tested.

A fixed set of named options (permissions, features)

→ EnumSet

Bitmask speed with readable names and type safety.

07 · recognise

Spot the pattern

"Every element appears twice except one"

XOR everything: pairs cancel

"…appears three times except one"

Count each bit position mod 3 (or the ones/twos state machine)

Numbers are exactly 0…n with one missing / one duplicated, O(1) space

XOR values with indices (or the Gauss sum)

"Without using + / - / *"

XOR = add without carry, (a & b) << 1 = the carries; shifts multiply by 2

"Power of two", "number of 1 bits", "binary representation"

n & (n − 1), Integer.bitCount

n ≤ ~20 and "all subsets" / "try every combination"

Loop mask from 0 to 2ⁿ − 1

State is a small set (visited nodes ≤ 16, letters a–z)

Store the set in an int mask, often as a DP dimension (bitmask DP)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Precedence: == binds tighter than &, so x & 1 == 0 does not even compile in Java. Also 1 << k - 1 means 1 << (k − 1). Always add parentheses: (x & 1) == 0.
  • 1 << k is an int. 1 << 31 is negative and 1 << 32 == 1. Use 1L << k for long masks.
  • Using >> in a loop like while (n != 0) n >>= 1; never ends for a negative n, because it sticks at −1. Use >>>.
  • Testing a bit with (x & mask) == 1 only works for bit 0. Write (x & mask) != 0.
  • Math.abs(Integer.MIN_VALUE) and -Integer.MIN_VALUE are both still Integer.MIN_VALUE. Two's complement has one more negative than positive.
  • Integer.parseInt(bits, 2) throws when 32 digits start with 1. Use Integer.parseUnsignedInt.
  • Forgetting n > 0 in the power-of-two test. Both 0 and Integer.MIN_VALUE pass (n & (n − 1)) == 0.

tricks

  • Simple hai — memorise six moves: check, set, clear, toggle, x & (x − 1) and x & -x. Almost every bit problem combines them.
  • Work examples on paper with 4-bit numbers (0–15). The patterns are the same as with 32 bits, and you can see them.
  • Say the identity out loud in interviews: "XOR is addition without carry, and a ^ a = 0, so pairs cancel."
  • Always test 0, 1, −1, Integer.MIN_VALUE and Integer.MAX_VALUE. These are where bit code breaks.
  • Write the raw version first, then mention the library call (Integer.bitCount). This shows you know both.
  • If the input size is around 20 and the problem says "choose any subset", reach for masks before recursion.

09 · why & how

Questions you might be too shy to ask

How do I read a binary number, and which one is "bit 0"?

Bit 0 is the rightmost bit and is worth 1. Bit 1 is worth 2, bit 2 is worth 4: bit k is worth 2ᵏ. So 1011 = 8 + 0 + 2 + 1 = 11. When a problem says "bit k", count from the right, starting at 0. 1 << k is exactly the number with only bit k on.

Isn't ^ the power operator? And is & the same as &&?

No to both, dhyan do. In Java ^ is XOR: 2 ^ 3 is 1 (10 XOR 11 = 01), not 8. For powers of two write 1 << 3; for anything else, Math.pow (it returns a double). & on ints works bit by bit: 6 & 3 is 2. && works only on booleans and stops early when the left side is false.

How are negative numbers stored, and why is −x = ~x + 1?

Java uses two's complement. Bit 31 counts as −2³¹ instead of +2³¹, and the other bits count as usual. So −1 is all 1s (−2³¹ + 2³¹ − 1). x + ~x is always all 1s, which is −1. Rearranged, that gives -x == ~x + 1.

To check odd or even, should I write x % 2 == 1 or (x & 1) == 1?

Use (x & 1) == 1 (or x % 2 != 0). In Java, % keeps the sign of the left side, so -3 % 2 is −1, and x % 2 == 1 wrongly calls −3 even. Bit 0 is 1 for every odd number, negative ones too, so (-3 & 1) is 1.

Why does Java have >>> when C and C++ don't?

Java has no unsigned int or long (only char is unsigned), so it needs a separate operator for "shift and fill with zeros". C picks the shift type from whether the variable is signed or unsigned. Java picks it from the operator: >> keeps the sign and >>> doesn't.

Why does x & (x − 1) erase exactly the lowest 1-bit? Show me on a number.

Take x = 12 = 1100. Subtracting 1 borrows from the lowest 1: that bit becomes 0 and every 0 below it becomes 1, so x − 1 = 1011. The bits above stay the same. AND keeps only the bits both share: 1100 & 1011 = 1000 = 8. One 1-bit gone, simple hai.

And why does x & -x keep only the lowest 1-bit?

-x is ~x + 1. For 12: x = 0000 1100, ~x = 1111 0011, and +1 carries into the first 0, giving 1111 0100. Above the lowest 1-bit, -x is the exact opposite of x; at that bit both have a 1; below it both are 0. So the AND leaves 0000 0100 = 4.

Why does XOR-ing the whole array work even though pairs are not next to each other?

XOR is commutative and associative, so you can reorder the terms freely. In your head, move each pair together: a ^ a = 0, and 0 ^ x = x. Only the unpaired value is left. The order in the array never matters.

Is bit manipulation actually faster, or just a party trick?

Single operations are as cheap as +. The big wins are elsewhere: O(1) space (XOR fold instead of a HashSet), packing 64 flags into one long, and bulk operations (BitSet.and works on 64 flags at a time, one long word per step). Don't write x >> 1 instead of x / 2 for speed. The JIT compiler already makes division by 2 fast, and the two differ for negative numbers: -3 / 2 is −1 but -3 >> 1 is −2.

When do I use int, long, or BitSet for a mask?

Up to 31 items → int. Up to 63 → long (with 1L << i). More than that, or a size known only at runtime → BitSet or boolean[]. For bitmask DP the limit is really the 2ⁿ table: n ≈ 20 is the most you can afford.

How do I see the binary of a number while debugging?

String.format("%32s", Integer.toBinaryString(x)).replace(' ', '0') prints all 32 bits with leading zeros. Integer.toBinaryString alone hides the leading zeros of positive numbers.

Single Number II: the ones/twos trick makes no sense to me. Do I need it?

Not to pass. The 32-column count is also O(n) time and O(1) space, and you can explain every line of it. A negative answer needs no special case: at bit 31, result |= 1 << bit is 1 << 31, which turns on the sign bit, so the rebuilt int is negative exactly like the single number. Learn ones/twos later, as a bonus for the follow-up.

Subsets with bitmasks or with backtracking: which should I use?

Both are O(n·2ⁿ). Masks are shorter, iterative and easy to get right. Backtracking is better when you can prune, i.e. skip whole branches (combination sum, constraints), or when n is unknown or large. Learn both. The backtracking chapter covers the other side.

Is using Integer.bitCount in an interview cheating?

It isn't cheating, but it may skip the point of the question. Say: "In production I'd use Integer.bitCount. Here's what it does underneath," and then write the n & (n − 1) loop. Interviewers love that answer.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #136
    Single Numbermust-do
    EasyAirbnbBloombergTCSAmazonGoogle+1
  2. #191
    Number of 1 Bitsmust-do
    EasyAppleMicrosoftGoogleAmazon
  3. #338
    Counting Bitsmust-do
    EasyMicrosoftGoogleAmazon
  4. #190
    Reverse Bits
    EasyNVIDIAAirbnbAppleAmazonMicrosoft
  5. #268
    Missing Numbermust-do
    EasyAmazonBloombergNVIDIAMicrosoftGoogle+1
  6. #67
    Add Binarymust-do
    EasyGoogleAmazonMetaMicrosoft
  7. #371
    Sum of Two Integers
    MediumGoogleAmazonMetaMicrosoft
  8. #137
    Single Number II
    MediumMicrosoftGoogleAmazon
  9. #260
    Single Number III
    MediumAmazonGoogle
  10. #231
    Power of Two
    EasyGoogleAmazon
  11. #201
    Bitwise AND of Numbers Range
    MediumGoogleAmazon

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #78
    Subsets
    Mediumin Backtracking

    Bitmask enumeration: the numbers 0 … 2ⁿ − 1 are exactly the in/out patterns of n elements (see its bitmask approach).

  2. #52
    N-Queens II
    Hardin Backtracking

    Three int masks hold every attacked column; free & -free peels off the safe ones.

  3. #421
    Maximum XOR of Two Numbers in an Array
    Mediumin Tries

    Greedy on bits from the top, with a binary trie: XOR again, but now maximised.

  4. #779
    K-th Symbol in Grammar
    Mediumin Recursion

    The answer is the parity of Integer.bitCount(k − 1) — popcount in disguise.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    A Java int is 32 bits in two's complement. &, |, ^, ~, <<, >>, >>> work on all 32 at once, in O(1).

  2. template

    With m = 1 << k: check (x & m) != 0 · set x | m · clear x & ~m · toggle x ^ m.

  3. pro tip

    x & (x − 1) erases the lowest 1-bit (popcount, power of two). x & -x keeps only the lowest 1-bit (Single Number III).

  4. use it when

    "Twice except one", "missing from 0..n", "without + or −", "power of two", "all subsets" with n ≤ 20 → think bits.

  5. pro tip

    XOR: a ^ a = 0, a ^ 0 = a, any order. XOR everything and every pair cancels, in O(1) space.

  6. cost

    One operator: O(1). A loop over a value's bits: O(log V) ≤ 32. All subsets by mask: O(n·2ⁿ). Every submask of every mask: O(3ⁿ).

  7. trap

    == binds tighter than &: write (x & m) != 0. And (x & m) == 1 is only right for bit 0.

  8. trap

    1 << 32 == 1 (the shift is taken mod 32): use 1L << k for long masks. >> keeps the sign; use >>> for raw bits.

  9. trap

    One extra negative: -Integer.MIN_VALUE == Integer.MIN_VALUE. A power-of-two test needs n > 0 first.

  10. pro tip

    Binary numbers as long strings: add column by column from the right with a carry. Integer.parseInt(s, 2) overflows past 31 digits.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

Why is -x == ~x + 1 in Java?

tap or Space to flip ↻

Question 1: Why is -x == ~x + 1 in Java?

13 · check yourself

Quick quiz

  1. What is 12 & (12 − 1)?

  2. In Java, what is -8 >>> 28?

  3. Which expression correctly tests whether bit k of x is set?

  4. What does XOR-ing all of [4, 1, 2, 1, 2] give?

  5. What is the value of `1 << 32` for an int in Java?

  6. nums = [a, b, c, d]. Which mask represents the subset {a, c}?

  7. Why does `n > 0 && (n & (n − 1)) == 0` need the `n > 0` part?

  8. What is the bitwise AND of every number from 12 to 15?

  9. Add Binary: why does the loop also run while `carry > 0`?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one