CHAPTER 04 · Bit Manipulation

Bit manipulation

A 32-bit integer is 32 switches, each one either 0 or 1. AND, OR, NOT and XOR change those switches directly, one position at a time. This chapter lays an integer out as a row of lamps so you can see how the value is stored, including negative values. It then covers the few bit patterns that appear in almost every interview problem, and sets up the state compression DP of chapter 10.

§01

One int is 32 lamps: binary and two's complement

Lay an integer out as a row of switches, then see how negative values fit in

The 42 you normally write is decimal: each position carries when it reaches ten. A computer stores only two states per position, so it uses binary: each position holds 0 or 1 and carries when it reaches two. A 32-bit integer is a row of 32 lamps. Each lamp is on (1) or off (0), and lamp i is worth 2ⁱ. The value is the sum of the lamps that are on. 42 = 32 + 8 + 2 = 2⁵ + 2³ + 2¹, so lamps 5, 3 and 1 are on. Try it yourself below.

Bit lamps — click any lamp to flip that bit (bit 31 is the sign bit)

Decimal 42Hex 0x0000002A0000 0000 0000 0000 0000 0000 0010 1010

The value is 42. It is the sum of the powers of two for every lamp that is on. Click the leftmost lamp (bit 31) and the value jumps to a negative number. That lamp is the sign bit of two's complement.

Presets:

While clicking you probably noticed something odd: turning on the leftmost lamp (bit 31) makes the value negative. That raises the first question of this chapter. How is a negative number stored in lamps that hold only 0 and 1?

The simple idea is to use the top bit as a minus sign and the rest as the magnitude. That representation is called sign and magnitude, and it has two problems: it has two zeros (+0 and −0), and addition has to check the signs first. Real hardware uses two's complement instead. The rule is the pattern for −n is (~n) + 1: flip every bit, then add one. With this rule, positive and negative values go through the same adder. The addition never looks at the sign, and a result that goes past the top of the range wraps around to the other end.

Start

…0000 0101

A positive value is its plain binary form. The top bit is 0.

Flip every bit: ~5

= −6

…1111 1010

Every lamp swaps on and off. In two's complement this pattern means −6, so ~x always equals −x−1.

~5 + 1

= −5

…1111 1011

Flip, then add one, and you have the pattern for −5. A top bit of 1 means the value is negative.

Why is −1 all 1 bits?

Apply the rule: −1 = ~1 + 1 = 1111…1110 + 1 = all bits set. Check it by adding 1 to all ones. Every position carries, the final carry falls off the top and is discarded, and the result is 0, which is exactly what −1 + 1 should give. Two's complement is chosen for this reason: ordinary binary addition makes x + (−x) = 0 come out right with no special case for the sign. Two anchors are worth remembering: 0 is all 0 bits and −1 is all 1 bits. Every other negative value lies between them.

Where the word bit comes from

In 1948 Claude Shannon used bit, short for binary digit, in his paper A Mathematical Theory of Communication, and credited his colleague John Tukey with coining it. Before that the smallest unit of information was simply called a binary digit. One bit is one lamp deciding between on and off, which is the smallest yes-or-no answer information can carry.

§02

Six operators: six ways to change the switches

AND & · OR | · XOR ^ · NOT ~ · shift left << · shift right >>

Unlike + − × ÷, the bitwise operators never carry from one position to the next. Except for the shifts, each bit position is computed on its own, using only the bits at that position. That is why they are fast: one CPU instruction handles all 32 lamps at once. In the playground below you can click the lamps of A and B, then switch the operator and watch the result.

Operator playground — click the lamps of A and B, then switch operator to see the result (8-bit demo)

A = 202

B = 108

= 72

202 & 108 = 72 — A result bit is 1 only when both input bits are 1. Use it to keep the bits you care about and clear the rest (a mask).

Operator	Name	Rule for one bit position	Common use
&	AND	1 only when both bits are 1	Keep or test selected bits (a mask)
\|	OR	1 when either bit is 1	Turn selected bits on
^	XOR	1 only when the two bits differ	Flip selected bits, cancel pairs
~	NOT	0 becomes 1 and 1 becomes 0 (one operand)	Invert; with +1 it gives the negative
<<	Shift left	All bits move left, 0 fills in on the right	× 2^k, build a mask 1<<i
>>	Shift right	All bits move right (arithmetic: the sign bit fills in)	÷ 2^k rounded down, read one bit

The same expression behaves differently in the three languages

Integer width and signedness are part of what a bitwise operator does, and the three languages do not agree. This is the most important table in the chapter.

1. Java: int is exactly 32-bit two's complement, and long is 64-bit. There are two right shifts: >> is arithmetic and copies the sign bit, >>> is logical and shifts in 0. When you treat an integer as a plain bit pattern rather than a number, use >>>, otherwise a negative value keeps filling with 1 bits. The shift distance is taken modulo 32 for int, so 1 << 32 is 1, not 0.

2. Python: integers have no fixed width. They grow as needed, so there is no overflow and no sign bit to shift. There is no >>> operator. Negative values behave like two's complement extended infinitely to the left, which is why ~5 is −6. To imitate a 32-bit unsigned value, mask with & 0xFFFFFFFF yourself. If the result should be negative, check bit 31 and subtract 1 << 32 to convert it back.

3. JavaScript: a Number is a 64-bit float, but every bitwise operator first converts it to a 32-bit signed integer and returns one. So 1 << 31 is negative, and the shift distance is taken modulo 32, which makes 1 << 32 equal 1. >>> exists and is the only operator that returns an unsigned value, in the range 0 to 2³²−1. For bitwise work on values above 2³¹, use BigInt.

§03

Three properties of XOR find the unpaired value

EASY

Worked example A · LC 136 Single Number

XOR (^) gives 1 at a bit position when the two input bits differ, and 0 when they are the same. Three properties follow from that, and together they solve a whole family of problems.

Property 01

a ^ a = 0

A value XORed with itself agrees at every position, so every bit becomes 0. A pair cancels.

Property 02

a ^ 0 = a

XOR with 0 leaves every bit as it was. The unpaired value passes through unchanged.

Property 03

Commutative · associative

The order does not matter: a^b^a = a^a^b = b. You may group the pairs together and cancel them.

The problem (LC 136): in an array every value appears twice except one, which appears once. Return that value. Direct approach: count with a hash map, which is O(n) time but O(n) extra space; sorting first and scanning for the odd one out costs O(n log n). Why XOR does better: combine the three properties. XOR the whole array into one variable. Each pair cancels because a^a = 0, and the remaining value survives because a^0 = a. One variable, so O(1) space. The animation walks through it step by step.

LC 136 · XOR everything: pairs cancel and the unpaired value is left

The array is [4, 1, 2, 1, 2]. Every value appears twice except 4. The plan is to make each pair cancel itself. The running XOR value acc starts at 0.

1 / 7

lc136_single_number.py

1class Solution:

2 def singleNumber(self, nums: list[int]) -> int:

3 ans = 0

4 for x in nums:

5 ans ^= x # a ^ a = 0 and a ^ 0 = a

6 return ans

7 # one-liner: from functools import reduce; from operator import xor

8 # return reduce(xor, nums)

In Python the exponent operator is ** and ^ is XOR. Beginners often confuse the two. This problem needs no fixed width: XOR works bit by bit, so Python's unbounded integers give the same answer.

Complexity and the follow-up questions

Time O(n), space O(1). Interviewers usually continue from here. 1. "What if two values each appear once?" That is LC 260: XOR everything to get a^b, then use the lowest set bit to split the array into two groups and XOR each group (the lowest set bit is covered in §04). 2. "What if the other values appear three times?" That is LC 137: XOR only cancels pairs, so switch to counting the 1 bits per position and taking the remainder modulo 3 (§05). 3. "Find the missing number (LC 268)?" XOR every index together with every value; each present value cancels its index, and the missing one is left.

Where XOR is used outside interviews

1. Recovering lost data. RAID disk arrays store the XOR of the data disks on a parity disk. If one disk fails, XORing all the remaining disks reproduces the missing block, because in a ^ b ^ c any two values determine the third. 2. Encryption. A one-time pad is plaintext ^ key, and XORing with the same key again returns the plaintext. 3. Swapping without a temporary variable: a^=b; b^=a; a^=b;. It is fine as an interview answer, but do not use it in real code: it is hard to read, and if a and b are the same location it sets both to 0.

§04

The bit expressions worth knowing by heart

EASY

Worked example B · LC 191 Number of 1 Bits, the main use of n & (n-1)

The table below lists the bit expressions that appear in almost every bit manipulation problem. Read the third column rather than memorising the second: each expression is short because of what the operator does to a single position. Here i is a bit position, counted from 0 at the lowest bit.

Goal	Expression	Why it works, and where it is used
Test odd or even	n & 1	The lowest bit is 1 for odd values and 0 for even ones, negative values included. Prefer it over n % 2, which is −1 for a negative odd n in Java and JavaScript.
Clear the lowest 1 bit	n & (n − 1)	The core of counting 1 bits (191) and testing a power of two (231)
Keep only the lowest 1 bit	n & (−n)	In two's complement −n agrees with n only at that one position. Used for splitting into groups (260) and in Fenwick trees
Set bit i to 1	n \| (1 << i)	Add element i to a set (§06)
Clear bit i to 0	n & ~(1 << i)	Remove element i from a set
Flip bit i	n ^ (1 << i)	Toggle one switch
Read bit i	(n >> i) & 1	Test whether element i is in a set, count per bit (137)
Multiply or divide by 2^k	n << k / n >> k	Exact as long as no bit is pushed off the top. For a negative n, >> rounds down while Java's int division rounds toward zero: −7 >> 1 is −4 but −7 / 2 is −3 (§07)

The most frequently tested of these is n & (n − 1). The problem (LC 191): given an integer, count how many 1 bits it has. That count is called the population count, or the Hamming weight. Direct approach: loop a fixed 32 times and read one bit each round with (n >> i) & 1. Can the work be spent only where a 1 actually is? The key observation: subtracting 1 borrows, so the lowest 1 bit of n becomes 0 and every 0 to its right becomes 1. ANDing that with n clears the lowest 1 bit and everything to its right, and leaves the higher bits unchanged. So the loop n = n & (n − 1) until n is 0 runs exactly once per 1 bit.

LC 191 · n & (n−1) clears the lowest 1 bit each round (n = 13)

n = 13, which is 1101 in the usual notation. The lamps below run the other way round: bit 0 is on the left and the number under each lamp is its bit position. Count how many 1 bits there are. count = 0.

1 / 5

lc191_number_of_1_bits.py

1class Solution:

2 def hammingWeight(self, n: int) -> int:

3 count = 0

4 while n:

5 n &= n - 1 # clear the lowest 1 bit

6 count += 1

7 return count

8 # shortest: return bin(n).count("1")

For a non-negative n, while n is enough, because n strictly decreases to 0. Python also has bin(n).count("1"), and n.bit_count() from version 3.10. Note that this loop does not terminate for a negative n: a Python negative integer has infinitely many leading 1 bits, so mask with & 0xFFFFFFFF first if the input can be negative.

Follow-up 01 · LC 231

Power of two

A power of two has exactly one 1 bit, so n > 0 && (n & (n−1)) == 0. Clearing the only 1 bit leaves 0. The n > 0 test is required: 0 and negative values pass the second test for a different reason.

Follow-up 02 · LC 461

Hamming distance

The number of positions where x and y differ is popcount(x ^ y). XOR marks the differing positions with a 1, and LC 191 counts them.

Follow-up 03 · LC 260

Two unpaired values

XOR everything to get a^b, take one differing position with x & (−x), split the array into two groups by that bit, and apply LC 136 to each group.

§05

Counting per bit: the method that works when XOR does not

MEDIUM

Worked example C · LC 137 Single Number II, where the other values appear three times

The problem (LC 137): every value in the array appears three times except one, which appears once. Return that value. Why the XOR from LC 136 fails: XOR removes values that appear an even number of times. With three copies, a^a^a = a, so nothing cancels.

Change what you look at: stop looking at whole numbers and look at one bit position at a time. At a given position, a value that appears three times contributes either 0 (its bit is 0) or 3 (its bit is 1). Both are multiples of 3. So add up all the 1 bits at that position and take the remainder modulo 3: the multiples of 3 divide out, and what is left is the bit of the value that appears once. Do that for all 32 positions and rebuild the answer.

LC 137 · count each column, then take it modulo 3 (nums = [2, 2, 2, 7])

bit

bit 2

bit 1

bit 0

Σ sum

nums = [2, 2, 2, 7]. Each number is written in binary as one row, so each column is one bit position. The plan is to work column by column and count the 1 bits in that column. The Σ and %3 rows are still unknown.

1 / 5

lc137_single_number_ii.py

1class Solution:

2 def singleNumber(self, nums: list[int]) -> int:

3 ans = 0

4 for i in range(32):

5 s = sum((x >> i) & 1 for x in nums)

6 if s % 3:

7 ans |= 1 << i

8 # Python integers have no fixed width: convert bit 31 back to a sign

9 if ans >= (1 << 31):

10 ans -= (1 << 32)

11 return ans

The Python trap of this chapter. Python integers have no fixed width, so nothing turns bit 31 into a sign automatically. An ans built bit by bit with bit 31 set is still a large positive number, so subtract 1 << 32 to get the negative value back. Note that (x >> i) & 1 is still correct for a negative x, because Python treats negatives as two's complement extended to the left without limit.

The same method solves the appears-k-times variants

Replace % 3 with % k and you can solve every variant where the other values appear k times and one value appears once. That is the point of counting per bit. XOR only removes values that appear an even number of times. When that is not enough, fall back to the plainer but more general method: count the 1 bits at each position, then take the remainder. LC 137 also has an O(n) time, O(1) space version that keeps two variables, ones and twos, as a small state machine. Counting per bit is easier to derive during an interview and fast enough.

Follow-up questions

1. "Can you avoid the 32 iterations and still use O(1) space?" Use the state machine ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones;. Remember it if you can, but explaining the per-bit counting idea is an accepted answer too. 2. "What if the values are 64-bit?" Run the loop over 64 positions instead. 3. "What if the others appear five times?" Use % 5. The idea does not change at all.

§06

An integer as a set: the basis of state compression DP

Prerequisite for chapter 10

One integer is one set, and bit i says whether element i is in it

This section is what chapter 10, state compression DP, is built on. The idea is short: treat one integer as one set. If lamp i is on, element i is in the set. A set of up to 32 possible elements then fits in a single int. Adding, removing and testing an element each become one bitwise operation, and because the set is now just a number you can compare two sets with ==, use a set as an array index, or store it in a hash map. Try the lab first, then read the code.

Set lab — one integer is one set, and bit i says whether element i is in it

mask s = 0101₂ = 5set = { 🍎 , 🍇 }

Four elements give 2⁴ = 16 subsets, one per cell above. Click a cell to jump to that subset, or click a fruit to add or remove one element. Using an integer as a set is the foundation of state compression DP in chapter 10.

2 / 4 elements

bitset_as_set.py

1s = 0 # the empty set

2s |= 1 << i # add element i

3s &= ~(1 << i) # remove element i

4inside = (s >> i) & 1 # 1 if element i is in the set, else 0

5size = bin(s).count("1") # number of elements

7# enumerate all subsets of {0..n-1}

8for sub in range(1 << n):

9 ... # sub is one subset

11# enumerate the non-empty subsets of mask

12sub = mask

13while sub:

14 ... # handle sub

15 sub = (sub - 1) & mask

Python integers have no fixed width, so 1 << i never overflows. In practice state compression stays around n ≤ 20, because 2ⁿ states have to fit in memory and time. ~(1 << i) is a negative number in Python, but ANDing it with a non-negative s still clears exactly bit i, so it is safe. From version 3.10 you can write s.bit_count() instead of bin(s).count("1"). Like the Java version, the while sub loop never yields the empty set.

A short example · LC 318 Maximum Product of Word Lengths: find two words that share no letter and maximise the product of their lengths. Comparing two words character by character is slow, but a word only matters here through which of the 26 letters it uses, and that is a set. Compress each word into a 26-bit mask: if the word contains letter c, set bit c. Two words share no letter exactly when mask1 & mask2 == 0, that is, when the intersection is empty. Testing the intersection drops from a scan over characters to one AND.

Where an integer is used as a set in real systems

1. Linux file permissions. In chmod 755 each octal digit is 3 bits standing for read, write and execute, so one number encodes a group of switches. 2. Feature flags. One integer can hold dozens of boolean settings, which saves memory and makes two configurations easy to compare. 3. Board games. Chess engines represent the whole board as a 64-bit bitboard, one bit per square, and generate moves with bitwise operations. 4. State compression DP. Chapter 10 uses a mask to record which tasks are finished or which cities have been visited, which turns an exponential set of states into an array index.

§07

Shifting: multiplying and dividing by powers of two

Left shift multiplies by 2ᵏ, right shift divides by 2ᵏ, and three traps you have to know

In decimal, adding a 0 to the end of 35 gives 350, which multiplies by 10. Binary works the same way: move every lamp one position left and fill the right with 0, and the value is doubled. So n << k is n × 2^k, and for a non-negative n, n >> k is n ÷ 2^k rounded down. Shifts are among the cheapest CPU instructions, and compilers have long replaced × 8 with << 3 on their own. Go back to the playground in §02, choose << or >>, and watch the whole row of lamps move.

Shifting has three traps you have to know about.

Trap 01 · overflow

Bits fall off the top

In 32 bits, 1 << 31 sets the sign bit, so the value is negative; shifting once more pushes the 1 out and leaves 0. In Java and JavaScript the shift distance is taken modulo 32, so 1 << 32 is 1, not 0. Python has no width limit, so there 1 << 32 really is 2³².

Trap 02 · negative values

Arithmetic vs logical

>> copies the sign bit, so −8 >> 1 is −4. >>> shifts in 0 and turns a negative into a large positive value. Use >>> when the integer is a bit pattern rather than a quantity. Python has only the arithmetic shift.

Trap 03 · precedence

Add the parentheses

In Java and JavaScript, == binds tighter than &, so a & 1 == 0 means a & (1 == 0). In Python the comparison binds more loosely, so the same line means (a & 1) == 0. The rule differs by language, so always write (a & 1) == 0.

shift_arithmetic.py

1a = 5

2mul8 = a << 3 # 40

3div2 = a >> 1 # 2

4neg = -8 >> 1 # -4 (Python's >> is arithmetic and rounds down)

5# Python has no >>>; to imitate a 32-bit unsigned shift:

6u = (-8 & 0xFFFFFFFF) >> 1 # mask to unsigned first, then shift

Python's >> rounds toward negative infinity, and so does //, so the two agree: −7 >> 1 and −7 // 2 are both −4, not −3. There is no unsigned shift, so mask with & 0xFFFFFFFF first when you need one.

§08

Problem set: 11 bit manipulation problems

Core set

Grouped as XOR, counting 1 bits, an integer as a set, and simulation, easiest first

LC 136Single NumberXORWorked exampleEASY

LC 191Number of 1 Bitsn & (n-1)Worked exampleEASY

LC 231Power of Twon & (n-1)ReuseEASY

LC 268Missing NumberXORSummationEASY

LC 461Hamming DistanceXORPopulation countReuseEASY

LC 190Reverse BitsShiftingBit by bitEASY

LC 137Single Number IIPer-bit countingWorked exampleMEDIUM

LC 260Single Number IIIXORLowest set bitGroupingMEDIUM

LC 318Maximum Product of Word LengthsBitmask as a setState compressionMEDIUM

LC 1356Sort Integers by The Number of 1 BitsPopulation countReviewEASY

LC 67Add BinarySimulationCarryEASY

§09

Chapter quiz

✎ Quiz

Answer all 8 questions correctly to mark this chapter complete

QUESTION 01 / 8

In a 32-bit signed integer (two's complement), what is the binary representation of -1?

QUESTION 02 / 8

What does the expression n & (n - 1) do?

QUESTION 03 / 8

Compute 5 ^ 3 (XOR). Answer in decimal.

QUESTION 04 / 8

LC 136 (every value appears twice except one) is solved by XORing everything. Which set of XOR properties makes that correct?

QUESTION 05 / 8

Which of these bitwise expressions are correct? (Select all that apply.)

QUESTION 06 / 8

In Java, what are the values of -8 >> 1 and -8 >>> 1?

QUESTION 07 / 8

Bit i of an integer s records whether element i is in a set. Which expression correctly tests whether element i is in s?

QUESTION 08 / 8

n & (-n) keeps only the lowest 1 bit of n, together with the place value that bit stands for. What is 12 & (-12)? Answer in decimal.

What to take away from this chapter

One int is 32 lamps, and lamp i is worth 2ⁱ. Negative values are stored in two's complement: −n = (~n) + 1. Two anchors: 0 is all 0 bits, −1 is all 1 bits.
The six operators work one position at a time: & keeps bits, | turns them on, ^ flips them and cancels pairs, ~ inverts all of them, << doubles, >> halves. One instruction handles all 32 positions, which is why they are fast.
The three XOR properties, a^a=0, a^0=a, and reordering is allowed, solve a whole family: the unpaired value (136), the differing bits (461), and the missing value (268).
Two expressions to remember: n & (n−1) clears the lowest 1 bit (counting 1 bits, testing a power of two), and n & (−n) keeps only the lowest 1 bit (splitting into groups).
When XOR does not help, because values appear three or more times, fall back to counting the 1 bits per position and taking the remainder modulo k (137). It is plainer but more general: change k and it solves the other variants.
An integer as a set: bit i says whether element i is present. Add with |(1<<i), remove with &~(1<<i), test with (s>>i)&1. Enumerating the non-empty subsets of a mask with sub = (sub−1) & mask costs 3ⁿ in total, and this is the basis of state compression DP in chapter 10.
The three languages differ, and it matters: Java and JavaScript have >>>, the logical right shift. Python integers have no fixed width, there is no >>>, and you mask with & 0xFFFFFFFF yourself. JavaScript converts to 32-bit signed before every bitwise operator, so 1<<31 is negative and 1<<32 is 1.