Bit Basics
Everything in this section rests on one idea: an integer is a row of switches. Once you can see the switches, "clever" bit tricks stop being clever and become obvious. This is the survival page - without it, nothing later makes sense. Core Techniques picks up from here with the actual set/clear/toggle vocabulary; this page is the model underneath it.
| If you are | Read |
|---|---|
| New to bits | Top to bottom. Do not skip the diagrams - they are the whole point. |
| Comfortable, rusty | Shifting and Negative numbers - what people forget first. |
| Interview prep | Python-specific gotchas, then straight to Core Techniques. |
| Revising | When bits are actually the answer alone - it is the "when does any of this matter" summary. |
Foundations
Number systems
A number system is just an agreed-on set of digits, used consistently, to write down values. The same digit sequence can mean different things in different systems - 10 is "ten" in decimal but "two" in binary - so a number is only meaningful together with the base it's written in.
If a system has n digits, its base (or radix) is n. Decimal is base-10 because it has ten digits; binary is base-2 because it has two.
| Number system | Base | Digits used |
|---|---|---|
| Binary | 2 | 0, 1 |
| Octal | 8 | 0, 1, 2, 3, 4, 5, 6, 7 |
| Decimal | 10 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 |
| Hexadecimal | 16 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F |
Decimal is the one you already think in: each column is worth ten times the column to its right, and the rightmost column - the least significant digit - is worth .
That "keep dividing by the base and read off the remainders" habit is the general recipe for writing any number in any base - decimal included, even though you never think about it that way. Repeatedly divide by 10 and keep the remainders; read them bottom to top and you have the digits back:
| n | n // 10 | n % 10 (digit) |
|---|---|---|
| 1256 | 125 | 6 |
| 125 | 12 | 5 |
| 12 | 1 | 2 |
| 1 | 0 | 1 |
Read the remainder column bottom-to-top: 1, 2, 5, 6. This is the same divmod-by-the-base trick that produces binary digits when the base is 2 instead of 10 - see bin(n) below, and the general form in Core Techniques.
Converting between any two bases is the same two ideas chained together: read the digits you have as a sum of place values to get a plain decimal number, then divide that decimal number back down by the target base to get its digits. Try it below - change the number or either base and both halves recompute:
| n | n ÷ 10 | n % 10 (digit) |
|---|---|---|
| 10 | 1 | 0 |
| 1 | 0 | 1 |
Of all these number systems, decimal and binary matter most for bit manipulation - decimal because it's how you think, binary because it's how the machine works. The rest of this page is about binary specifically.
Why bits, and why binary
A computer is built out of switches, and a switch reliably tells you exactly one thing: on or off. Building a switch that reliably holds one of ten stable voltage levels - so it could count in decimal - turns out to be a much harder engineering problem than building one that reliably holds one of two. Two states tolerate noise; ten states do not. That is the entire reason computers are binary: not elegance, not tradition, just "this is the version that is physically robust to build in bulk."
The logic to compute with true/false predates the hardware by nearly a century. George Boole formalized an algebra of true and false in 1854 - and, or, not - as a tool for logical reasoning, with no computing machine in mind at all. The binary place-value number system Boole's algebra would eventually operate on is older still: Gottfried Leibniz wrote it up in 1679. Both sat as pure mathematics for decades.
The bridge between the two was Claude Shannon's 1937 master's thesis, which showed that Boole's true/false algebra is exactly the algebra of a circuit built from on/off switches - AND is two switches in series, OR is two switches in parallel, NOT is a switch that inverts. That single observation is why every processor since has been built out of the same handful of logic gates you'll meet in the next section, and why "binary" and "logical" turned out to be the same problem wearing two names.
A number is a row of switches
Each switch is a bit, and each position is worth twice the one to its right. Add up the positions whose switch is on and you have the number. That is all binary is.
Two habits make binary readable at a glance:
- Count positions from the right, starting at 0. Bit 0 is the ones place, bit 3 is the eights place. "Bit
i" always means . - Learn the first ten powers of two. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512. Every mask you will ever write is built from these.
The diagram above always reads left-to-right as MSB down to LSB - that is not a convention, it is just what place value means: bit 7 is worth more than bit 0, in every language, on every machine, always. Endianness is a different question that only shows up once a number is more than one byte wide and has to be laid out in memory or sent over a wire. Which byte comes first is a real choice that varies by platform: big-endian stores the most significant byte at the lowest address (byte order matches the MSB-to-LSB reading order above); little-endian stores the least significant byte first instead. The 16-bit value 0x1234 sits in memory as the two bytes 12 34 on a big-endian machine, but 34 12 on a little-endian one (x86 and ARM in their default mode) - same number, two different byte-for-byte layouts.
bin(90) gives '0b1011010', int('1011010', 2) gives it back, and f'{90:08b}' pads to a fixed width - which is what you want when printing bits while debugging.
Operations
The four logic operators
Bitwise operators apply the same tiny rule to every column independently. There is no carry, no borrow, no interaction between positions. Learn the four rules and you know the operators.
The fourth operator, ~ (NOT), takes one operand and flips every bit. Read each operator by its intent, not its truth table - that is what makes code readable:
| Operator | Column rule | What you actually use it for |
|---|---|---|
a & b | 1 only when both are 1 | Keep / mask. Whatever is 0 in the mask is erased in the result. |
a | b | 1 when either is 1 | Set / merge. Turn bits on, union two sets, never turns anything off. |
a ^ b | 1 when they differ | Toggle / difference. Flip chosen bits, or find what changed. |
~a | flip every bit | Invert. Almost always used to build a clearing mask: x & ~mask. |
Applied to real bytes, every column is resolved on its own:
XOR earns its own list, because most of this section's problems are XOR problems. Four facts, four quadrants:
The pairs-cancel fact is the whole solution to Single Number, Missing Number and Find the Difference.
Shifting
<< slides every bit left, >> slides every bit right. Bits pushed off the end are gone; the vacated positions fill with zeros.
A shift is arithmetic. Scrub n below - click a bit or drag the slider - and
sweep the shift distance k. Both expressions follow both inputs.
n * 2**kNever loses information in Python (integers grow); overflows in fixed-width languages - the register above is 8 bits wide, so raise k and watch the top bits fall off.n << k0101100088n // 2**kFloor division. The discarded low bits are the remainder.n >> k000001015A shift is also how you build a mask. These two ignore n entirely - the
shift distance alone decides the shape - so sweep k and watch the columns
move.
k setThe single most-used expression in this whole section.1 << k000001004k onesTake low k bits with x & ((1 << k) - 1).(1 << k) - 1000000113Logical shift fills vacated bits with 0, always. Arithmetic shift fills them with a copy of the sign bit, so a negative number stays negative. They only differ on negative inputs.
Take an 8-bit -5 = 11111011, shifted right by 1:
- Logical:
01111101= 125 - a sign flip, since a0fills the top bit. - Arithmetic:
11111101= -3 - the sign bit (1) fills in, so the value stays negative.
In Python (and Java's >>, and C on signed ints) the right shift is arithmetic: -5 >> 1 is -3, not a huge positive number. Java's >>> is the explicit logical version; Python has none, because Python integers have no fixed width to fill. << doesn't have this split - left shift always fills with 0 on both variants. If a problem needs 32-bit unsigned (logical) behavior, mask explicitly with & 0xFFFFFFFF.
A shift throws bits away. Core Techniques covers the variant that doesn't - rotation, where the bits that fall off one end wrap around to the other.
Properties of bitwise operations
Everything above has been what each operator does, column by column. This is how they combine - the algebraic laws that let you rearrange a bitwise expression the same way you'd rearrange ordinary arithmetic, plus the identities that fall out once 0 and -1 (all bits set) are treated as first-class values.
| Law | AND | OR | XOR |
|---|---|---|---|
| Idempotent | a & a == a | a | a == a | fails - a ^ a == 0, not a |
| Commutative | a & b == b & a | a | b == b | a | a ^ b == b ^ a |
| Associative | (a & b) & c == a & (b & c) | (a | b) | c == a | (b | c) | (a ^ b) ^ c == a ^ (b ^ c) |
XOR is the odd one out on idempotence - & and | are "no-ops" applied to themselves, XOR is a cancellation applied to itself, which is exactly the self-cancellation fact above that makes single-number-style problems work.
| Law | Statement |
|---|---|
Distributive: & over | | a & (b | c) == (a & b) | (a & c) |
Distributive: | over & | a | (b & c) == (a | b) & (a | c) |
| De Morgan's, AND side | ~(a & b) == ~a | ~b |
| De Morgan's, OR side | ~(a | b) == ~a & ~b |
The distributive laws are the least obvious of the bunch - & and | distribute over each other, not just over themselves, which has no ordinary-arithmetic analogue (x * (y + z) distributes, but there's no everyday operator pair that distributes both ways like this).
Identity elements: 0, -1, and ~a. -1 is worth naming explicitly: in two's complement it is all bits set (~0), which makes it the identity element for & the same way 0 is the identity element for | and ^.
| Property | Meaning |
|---|---|
a & 0 == 0 | 0 is AND's absorbing element - anything ANDed with all-zeros is wiped out. |
a & -1 == a | -1 is AND's identity element - all bits set means nothing gets masked away. |
a & ~a == 0 | a value and its own complement share no set bit, by definition of complement. |
a | 0 == a | 0 is OR's identity element. |
a | ~a == -1 | between a and ~a, every bit position is set in one or the other. |
a ^ 0 == a, a ^ a == 0 | XOR's identity and self-cancellation - the pairs-cancel fact above. |
-1 == ~0 | flip every bit of zero and you get all bits set, which is -1 in two's complement. |
-a == ~(a - 1) | a restatement of -n == ~n + 1 (below, in Negative numbers) with the +1 moved inside: subtracting 1 from a first, then flipping, lands on the same value as flipping a and adding 1 after. |
Python integers have no fixed width, so ~a sign-extends forever instead of stopping at 8 or 32 bits - a & -1 == a holds exactly as written (Python's -1 is already infinite ones), but anything comparing against ~a directly (De Morgan's, a & ~a) needs both sides masked to the same width first, or the infinite leading 1s on one side never match the finite pattern on the other.
Two more identities are common enough to name here, but they already have their own full derivation elsewhere - no need to duplicate the walkthrough: clearing the lowest set bit, a & (a - 1), and isolating the lowest set bit, a & -a - both in Core Techniques.
Negative numbers
Two different questions live under one heading: how do you write a negative number in bits at all (original code, then one's complement, then two's complement - three attempts, each fixing the last one's flaw) and what does a given bit pattern mean (signed vs unsigned - a property of the type, not the bits).
Fixed widths, and how many values they hold
A real integer type doesn't get infinitely many bits - it gets a fixed width, and that width caps how many distinct values it can hold. A k-bit pattern has exactly distinct arrangements, full stop; whether those arrangements are read as signed or unsigned only decides how they're labeled, not how many there are.
| Width | Bits | Possible values |
|---|---|---|
| 1 byte | 8 | $2^8$ = 256 |
| 2 bytes | 16 | $2^{16}$ = 65,536 |
| 4 bytes | 32 | $2^{32}$ ≈ 4.3 billion |
| 8 bytes | 64 | $2^{64}$ ≈ 1.8 x $10^{19}$ |
Two vocabulary words make the rest of this section precise. The machine number is the raw bit pattern itself, sign bit included - it's what's physically stored. The truth value is the actual number that pattern is meant to represent. Machine number 10000010 and truth value -2 are two names for the same fact, one in bits, one in decimal.
Original code (sign-magnitude)
The most literal way to write a negative number: reserve the top bit to mean the sign (0 non-negative, 1 negative), and store the magnitude in the rest, untouched. No inversion, no arithmetic - just a sign flag glued onto the same bits you'd write for the positive value.
Original code is the easiest of the three to check by eye - the magnitude bits are the number's ordinary binary form, so there's nothing to decode. But 00000000 and 10000000 are both zero, and subtraction needs its own special-cased logic to route around the sign bit instead of just adding. One's complement, below, inherits the same dual-zero flaw from a different angle.
One's complement
The most obvious way to negate a number: flip every bit. One's complement does exactly that, no extra step.
It looks simpler, and it is - which is exactly why early computers used it. But this doesn't work cleanly: 00000000 and 11111111 both mean zero, comparing equal in value but not in bits, so every == 0 check either needs to know about both patterns or gets it wrong, and arithmetic needs an extra "end-around carry" fixup step just to work at all. One's complement survives today only as a history-class footnote (and, in an ironic twist, as the basis for the Internet checksum algorithm in TCP/IP, which still does end-around-carry arithmetic on purpose) - everything else moved to a fix.
Two's complement
That fix: flip every bit, then add one. This is not a convention chosen for elegance - it is chosen so that ordinary binary addition works on negatives with no special case, and it buys back a single, unambiguous zero.
That one extra step at negation-time - the +1 - is why every mainstream processor since has used two's complement instead. The useful consequence: adding one to ~n propagates a carry up through the trailing ones of ~n, which are exactly the trailing zeros of n, and stops at the lowest set bit of n. Everything above that point stays inverted, everything below is zero, and the lowest set bit itself matches. That is precisely why n & -n isolates the lowest set bit - see Core Techniques.
Why two's complement won
Stacking all three representations side by side, for 8 bits, makes the trade-off concrete:
| Representation | Range | Zero |
|---|---|---|
| Original code (sign-magnitude) | -127 to 127 | two patterns: 00000000 and 10000000 |
| One's complement | -127 to 127 | two patterns: 00000000 and 11111111 |
| Two's complement | -128 to 127 | one pattern: 00000000 |
Two's complement is strictly better on both axes: one canonical zero (so == 0 is a single bit-pattern check, and ordinary addition just works with no sign-bit special case), and it claims the one extra negative value (-128) that a spare zero pattern would otherwise have wasted. Generalizing the range to k bits: a signed integer holds to ; an unsigned integer of the same width holds to - same patterns, different labeling.
Signed vs unsigned, and how other languages enforce it
The exact same bit pattern means a different number depending on whether you are told it is signed (top bit is the sign, two's complement) or unsigned (top bit is just another place value, always non-negative). 11111111 is 255 unsigned, or -1 signed. Nothing about the bits themselves says which - that information lives entirely in the type, which is precisely what Python does not have.
| Language | How width is enforced | Signed overflow behavior |
|---|---|---|
| C / C++ | Fixed-width types you choose: int8_t, uint32_t, int64_t, etc. | Undefined behavior (pre-C++20, implementation-defined whether it is even two’s complement; C++20 mandates two’s complement, but overflow is still UB). |
| Java | Fixed-width int (32-bit) and long (64-bit) - no unsigned integer types at all. | Well-defined: silently wraps around, because Java mandates two’s complement. |
| Python | No fixed width - int is arbitrary precision, always effectively signed. | No such thing as overflow. Mask explicitly (& 0xFFFFFFFF) to simulate a fixed-width unsigned view, and re-derive the sign yourself for a signed view (the Python gotchas below cover exactly this). |
INT_MAX + 1 in C/C++ is not guaranteed to become INT_MIN - the language standard permits the compiler to assume signed overflow never happens at all, which means an optimizer is legally allowed to delete a bounds check that only fires "after" an overflow, since it can decide that path is unreachable. This is a real, exploited class of bug. Unsigned overflow in C/C++, by contrast, is well-defined: it wraps modulo 2**width, always. When you need guaranteed wraparound, use an unsigned type.
Applying it
Python-specific gotchas
~ is not "flip the bits of this number"~5 is -6, not 2. Python integers are conceptually infinite-width with infinite sign extension, so ~ flips an unbounded run of leading bits too. To flip only the bits n actually occupies, XOR with an all-ones mask of the right width:
Note (0).bit_length() is 0, so n = 0 needs its own branch.
x & 1 == 1 parses as x & (1 == 1). It happens to work for the mask 1, which is why the bug survives so long, but x & 3 == 3 parses as x & True, which is x & 1 - silently the wrong answer. Always parenthesize: (x & 3) == 3.
Python integers are arbitrary precision, so 1 << 100 is a perfectly good number and nothing ever wraps. Problems written for 32-bit signed integers (reverse bits, add two integers without +, count bits of a "32-bit" value) need you to impose the width yourself with & 0xFFFFFFFF, and to convert back to a signed value at the end when the top bit is set:
A one-liner that does the same conversion shows up often enough to recognize on sight: ~(result ^ MASK). It looks like black magic, but it is doing exactly the branch above in two operations instead of an if-statement:
result ^ MASKflips every one of the 32 bits (XOR-ing with an all-ones mask is the negate-bits-style trick, applied here to a fixed 32-bit width instead ofbit_length()).~is Python's infinite NOT:~yis defined as-(y + 1), no matter how many bitsyhas.
Chain them and the algebra collapses to exactly result - (1 << 32): if y = result ^ MASK, then (since MASK is 32 ones) y = (2**32 - 1) - result, so ~y = -(y + 1) = -(2**32 - result) = result - 2**32. Same answer, no if. Trace it on result = 0xFFFFFFFF (which should decode to -1): result ^ MASK is 0 (a number XORed with itself), and ~0 is -(0 + 1) = -1. It only does the right thing when result is already a genuine 32-bit unsigned pattern (0 to 0xFFFFFFFF) - applying it to an already-signed Python int gives nonsense. See Sum of Two Integers for this in a real solution.
bit_length() and bit_count() edge cases(0).bit_length() is 0, so any "width of n" formula collapses for zero - branch on it. int.bit_count() only exists on Python 3.10 and later; on older runtimes use bin(n).count('1'). Neither method works on negative numbers the way you would expect: bit_length ignores the sign, and bit_count counts the magnitude's bits.
bool are not and / orTrue & False works because bool is an int subclass, but & and | do not short-circuit and have different precedence from and / or. Use the keywords for logic and the symbols for bits; mixing them is how subtle evaluation-order bugs get in.
Python spells popcount/leading-zeros/trailing-zeros as n.bit_count() and n.bit_length() because it has no fixed word size to hand you a raw CPU instruction. Other languages expose the hardware directly: GCC/Clang have __builtin_popcount, __builtin_clz (count leading zeros), __builtin_ctz (count trailing zeros), and __builtin_bswap32 (byte-swap, for endianness conversion); ARM has __CLZ and a real bit-reversal instruction, __RBIT. Recognize these names when reading C/C++ solutions - they are exactly the Python idioms on this page, just compiled to one cycle instead of a loop.
When bits are actually the answer
Reach for bit manipulation when one of these is true:
- Pairs cancel. Anything phrased as "every element appears twice except one" is XOR.
- The universe is small and fixed. Up to ~20 items, a subset is an integer and DP over subsets becomes feasible.
- You need constant extra space. Bits let you carry state (a parity, a seen-set, a marker) inside numbers you already have.
- You are counting or testing structure. Set bits, trailing zeros, adjacent bits, powers of two.
And be honest about when it is not: a bitwise loop over a 32-bit word is , but a bitset sweep over n items is , not . Bit tricks change constants, not complexity classes, except in the bitmask-DP case where they change the representation and unlock where nothing polynomial exists.
Where to go next
- Core Techniques - set, clear, toggle, rotate, the two identities that carry most problems, and the full idiom cheatsheet.
- Counting Bits - popcount, Hamming distance, set-bit count as a key.
- Bit Patterns & Properties - powers of two, runs and gaps, folding across a range.
- Rebuilding a Number - complement, reverse, encode/decode, arithmetic without
+. - XOR - cancellation, single number, folding and inverting a sequence.
- Bitmask as a Set - one integer models a set of small values.