Bit Manipulation

Reader guide and study workflow · Complete course map

An input contains pairs of repeated machine integers and one unpaired value. A frequency map solves it immediately, using space proportional to the distinct values. Can a fixed-size summary discard completed pairs without discarding the singleton?

Ordinary addition cannot erase two equal values: x+x is 2x. OR cannot erase anything once a bit is set. XOR does have the required cancellation, x XOR x=0, and zero leaves another value unchanged. The multiplicity promise selects the operation; the word “bits” alone does not.

Start from what information must survive

Fold [-7,4,4] with XOR. The two 4 patterns cancel regardless of their positions, leaving every bit of -7 unchanged. The accumulator means “XOR of all processed entries.” Associativity and commutativity let the final expression be regrouped into pairs, so order does not matter.

Now change pairs to triples. Three copies XOR to one copy, so the old summary fails. Count each bit position modulo three instead: repeated values contribute either zero or three ones at that position. The residue is the singleton’s bit. Reconstructing all 32 bits into an int32 preserves negative values; omitting the sign position silently changes the number.

This is state design: identify which contributions may be discarded and which must remain observable. A different repetition promise requires a different proof.

Separate a bit pattern from its width and interpretation

Reverse the bits of the value 1. If you reverse only its significant digit, the answer is 1. If the contract says an eight-position register, it is 128. If it says uint32, it is 2147483648. These are different operations, not competing optimizations.

After consuming k low bits in the fixed-width reversal, res holds those k bits in reverse order and the shifted input holds the rest. Even when the remaining input becomes zero, its remaining positions still have to be consumed. The unsigned type supplies logical right shifts; the fixed iteration count supplies the width.

Population count discards different information: the locations of ones do not matter, only their number. For binary 101100, subtracting one gives 101011; AND leaves 101000. Exactly one set bit disappears. The invariant is count + remaining set bits = original set bits, so repeated clearing reaches the answer when nothing remains.

Let local arithmetic explain the carry

Adding binary strings of ten thousand digits cannot rely on converting the whole input into a machine integer. At each position, however, two input bits and one carry total at most three. Its remainder modulo two is the next output bit; its quotient by two is the next carry.

For 111 + 1, low-to-high totals are 2,2,2,1. The emitted bits are 0,0,0,1; reverse them to obtain 1000. The final carry is ordinary remaining state, not an exceptional patch. The contract also preserves input width: 00 + 0 returns 00.

Range AND exposes a different danger: equal endpoint bits need not stay set inside the range. For [5,7], endpoints both end in 1 but the interior 6 ends in 0. Find the highest differing position, retain the common higher prefix, and zero the suffix only after proving the interval crosses a binary boundary that supplies the needed zeroes. The workshop below develops that argument.

Transfer: two singletons instead of one

In [4,9,2,4,2,7], every value except two appears twice. XORing the whole input gives 14. Why is returning 14 wrong? How can one set bit of 14 divide the data into two subproblems that the single-number idea can solve?

Model answer: preserve a distinction before cancelling

The two singletons are 9 and 7; total XOR gives 9 XOR 7=14, not either value. Binary 14 is 1110. Choose bit 1 (value 2), where the two singleton patterns differ. Partition all values by that bit.

The bit-clear group is [4,9,4], whose XOR is 9. The bit-set group is [2,2,7], whose XOR is 7. Every repeated pair stays together because equal values have equal bits; the singleton values separate because their XOR has the chosen bit set. Thus each group has exactly the original one-singleton promise. This is a reasoning extension; the pack’s SingleNumber API still asks for one singleton under its original promise.

Before implementing a bit loop, state width, signedness, the accumulator’s meaning, and the exact multiplicity or range promise. Test position-sensitive operations with one-hot inputs; test cancellation operations with separated repeats and negative patterns. An appealing operator identity is useful only when it matches the information the task may discard.

Prerequisites and readiness

Know positional binary notation, AND/OR/XOR, shifts, carry, and the distinction between uint32, int32, and machine-width int. Explain why a bit pattern and its signed numerical interpretation are different questions.

Reasoning workshop: width, invariant, and interpretation

Carry is information, not a special case

Try an unequal-width case: 1110 + 11. The first two low positions emit 1 then 0, leaving carry 1 after the shorter input is exhausted. What happens next? The remaining 1 from the longer input and the incoming carry total 2, so the next bit is 0 and carry remains 1. Repeat once, then emit the final carry: low-to-high output is 1,0,0,0,1, giving 10001.

The exhausted string contributes zero; it does not cancel the incoming carry. The bound carry≤1 follows from a local total at most 1+1+1=3, independent of input length. Use that bound to explain why a single carry bit is sufficient even for ten thousand input digits. Keep the separate string contract in view: leading input width is preserved, so mathematically equivalent canonicalization can still change the required result.

Do not confuse significant digits with a fixed-size register

Pause a 32-step reversal of 0x01000002 after eight iterations. The consumed low byte was 00000010, so the accumulator is now 01000000 (0x40), and the shifted input is 0x00010000. The accumulator is only the reverse of the consumed portion; it is not in its final location yet. Completing the remaining positions gives 0x40000080: original bit 1 moves to 30, and bit 24 moves to 7.

A double reversal should recover the input, but an incorrect identity function also passes that property. Exact one-hot checks supply the missing position evidence: every original bit i must move to 31-i. A test property and an independent exact result answer different questions.

Population count consumes information differently. From 10001000, subtracting one gives 10000111 and AND leaves 10000000. The next clear reaches zero: two iterations regardless of how far apart the two ones were. For a generalized W-bit register, work is O(popcount), at most O(W); for the API's fixed 32-bit input it is bounded constant work.

Multiplicity is the algebraic precondition

XOR cancellation solves the pair promise because x XOR x = 0. It does not solve triplets: three copies XOR back to x. For triplets, count each bit modulo three. A repeated value contributes three copies of each set bit and therefore vanishes modulo three.

The singleton -2 has the signed-32-bit pattern 111...110. Reconstructing only 31 bits loses its sign. The input contract bounds every value to signed 32 bits, even though the signature uses Go int. The reference converts to int32, reconstructs all 32 positions, then widens the signed result back to int. This preserves -2 rather than interpreting its pattern as unsigned 4294967294.

A range is more than its endpoints

Explain the suffix using [26,31], whose endpoint patterns are 11010 and 11111. The higher prefix 11 stays fixed. The highest differing position is bit 2: the left endpoint already supplies a zero there. The interval also includes the boundary 28=11100, which supplies zeros at positions 1 and 0. Thus the AND is 11000, or 24.

Which part of this reasoning generalizes? At the highest differing bit, the lower endpoint is in the zero half and the upper endpoint is in the one half of the same higher-prefix block. The first value of that one half lies inside the interval and has every lower bit zero. The differing bit is cleared by the lower endpoint, the lower suffix by the boundary value, and no higher bit changes anywhere in between. This proves the common-prefix rule without assuming that equal low endpoint bits remain set inside the range.

Reconstruct without operator memorization

For every bit loop, name the width, the consumed part, the remaining part, and the meaning of the accumulator. Then ask whether zero, a negative pattern, or an extreme shift changes that meaning. A printed four-bit trace is useful for intuition, but include 32-bit boundary tests before claiming the implementation matches its actual type contract.

Reconstruction lab and answer key

Add Binary

Add 10111 and 00101. After the first two low positions, emitted bits are 00 and carry is 1. Complete the next column, including its outgoing carry, then finish the result. Why would resetting carry before using it fail?

Model answer

The next column totals 1+1+1=3, so emit 1 and retain carry 1. The next total is 0+0+1=1, then the final total is 1+0=1. Emitted low-to-high bits are 0,0,1,1,1, giving 11100. Resetting the incoming carry drops a contribution from the already-processed suffix and breaks the positional-addition invariant.

Reverse Bits

A byte-oriented implementation reverses the eight bits inside each byte but leaves byte order unchanged. On uint32(1), it returns 0x00000080. What second transformation repairs full 32-bit reversal, and why?

Model answer

Reverse the order of the four bytes as well, producing 0x80000000. A bit at byte position q and within-byte position r must move to byte 3-q and bit 7-r. Reversing only within bytes handles the second coordinate and misses the first; composing both transformations maps bit i to 31-i.

Number of 1 Bits

A proposed test checks HammingWeight(x)+HammingWeight(^x)==32 for uint32 inputs. A broken implementation always returns 16. Would it pass, and what independent exact cases should accompany that property?

Model answer

It passes for every input because 16+16=32. Add exact expectations such as zero→0, all-one uint32→32, and a one-hot input→1. The complement identity is valid, but a property relating two outputs can be satisfied by a wrong implementation. Ground it in exact known behavior as well.

Single Number

Both [0,4,4] and [1,2,3] have total XOR zero. Does a zero result prove that a valid singleton zero exists? Explain what the algorithm assumes instead of checking.

Model answer

No. The first input has the promised paired values and singleton zero. The second has three different singletons and violates the promise, even though 1 XOR 2 XOR 3=0. The fold computes an algebraic summary, not a validation of occurrence counts; correctness depends on the input multiplicity precondition.

Single Number II

While reading [6,6,6,-1], after the first two entries some bit-count residues equal 2. Are those residues already the singleton’s bits? Identify when cancellation becomes a valid reconstruction argument.

Model answer

No. A prefix may contain only part of a promised triple, and a residue of 2 is not a binary bit. After every input is processed, each repeated value contributes exactly three copies per set bit, leaving residues 0 or 1 from the singleton. Reconstruct the complete signed-32-bit pattern only at that point; for this input it represents -1.

Bitwise AND of Numbers Range

Change the input from a contiguous interval to the sparse set {9,11}. Its smallest and largest values have common prefix 10 in four-bit notation. Would zeroing the suffix still compute the set’s AND?

Model answer

No. 9=1001 and 11=1011 AND to 1001, or 9. The common-prefix interval rule gives 1000 because the full interval also includes 10=1010, which supplies the missing low zero. The proof uses every integer between the endpoints; it does not extend to an arbitrary sparse subset.

Problems in this module

• Add Binary
• Reverse Bits
• Number of 1 Bits
• Single Number
• Single Number II
• Bitwise AND of Numbers Range

Interactive checkpoint

Open the Bit Manipulation quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable

Earlier-edition pattern links

The opening now derives the choices above before naming individual recipes. These headings preserve prior bookmarks.

Pattern A: Bit-wise addition

Continue with the current reasoning workshop.

Pattern B: Fixed-width bit reversal

Continue with the current reasoning workshop.

Pattern C: Counting set bits

Continue with the current reasoning workshop.

Pattern D: XOR for unique elements

Continue with the current reasoning workshop.

Pattern E: Bit counts mod k

Continue with the current reasoning workshop.

Pattern F: Range AND by common prefix

Continue with the current reasoning workshop.

When to use Bit Manipulation (checklist)

Continue with the current reasoning workshop.

Common failures (checklist)

Continue with the current reasoning workshop.

Problem mapping

Continue with the current reasoning workshop.