← Bits · guided lesson
Bit Manipulation
the story
Two's complement integers
Every tool here exists because something was too slow or broke without it. Here is what.
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 solved
One adder for both addition and subtraction, and a single zero, instead of separate sign handling.
why it matters: 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.
sources: von Neumann — First Draft of a Report on the EDVAC (1945), ed. Godfrey, IEEE Annals of the History of Computing (1993) ↗ · University of Cambridge Computer Laboratory — EDSAC simulator guide (number format) ↗ · Java Language Specification (Java SE 17), §4.2 Primitive Types and Values ↗
also in this chapter: Bitmasks as sets (and bitboards) · Clearing the lowest 1-bit: x & (x − 1) · XOR cancellation (parity) · Binary addition: sum bit and carry
the idea
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.
watch it
Check, set, clear, toggle on 8 bits
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Check, set, clear, toggle on 8 bits
The mask lights up bit k. Watch which bits each operator touches, and which it leaves alone.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
>> vs >>> on a negative number
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
>> vs >>> on a negative number
Both slide bits right. `>>` copies the sign bit into the gap. `>>>` always fills it with 0.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Java int = 32 bits in two's complement. Bit 31 is the sign bit. Range is −2³¹ … 2³¹−1, and -x == ~x + 1.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
The operators: & (both 1), | (either 1), ^ (different), ~ (flip all), << (shift left, ×2), >> (shift right, copies the sign bit), >>> (shift right, fills with 0).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
With mask = 1 << k: check (x >> k) & 1, set x | mask, clear x & ~mask, toggle x ^ mask.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
x & -x keeps only the lowest 1-bit (e.g. 12 = 1100 → 4 = 0100). It splits numbers into two groups in Single Number III.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
XOR rules: a ^ a = 0, a ^ 0 = a, and order does not matter. XOR a whole array and every pair cancels.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
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.
spot the pattern
When you see this, think this
"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
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Precedence:
==binds tighter than&, sox & 1 == 0does not even compile in Java. Also1 << k - 1means1 << (k − 1). Always add parentheses:(x & 1) == 0. 1 << kis anint.1 << 31is negative and1 << 32 == 1. Use1L << kfor long masks.
quick check
One question. No pressure.
What is 12 & (12 − 1)?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Single Number
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why is -x == ~x + 1 in Java?
Question 1: Why is -x == ~x + 1 in Java?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.