Bit manipulation

XOR cancels pairs; n & (n−1) clears the lowest set bit. Usually signalled by a space constraint.

Trigger in the prompt: 'Appears once', 'no extra space', 'count the bits', 'without arithmetic operators'.

easyNumber of 1 Bits

Count the set bits in an integer.

Trigger

'Population count', 'how many ones'.

Approach
  1. The loop-and-shift version is O(number of bits), 32 iterations.
  2. Better: `n & (n - 1)` clears the lowest set bit, so the loop runs once per set bit.
  3. Explain why that works: subtracting one flips the lowest one and everything below it.
Target complexity

O(number of set bits) with the Brian Kernighan trick.

Pitfall

Converting to a binary string and counting characters. It works, but the question is about bit operations.

Say it out loud

“The trick is that n and n minus one clears the lowest set bit, because subtracting one flips that bit and everything below it. So the loop runs once per set bit rather than once per bit position.”

Solve on LeetCode
easyReverse Bits

Reverse the bit order of a 32-bit unsigned integer.

Trigger

'Reverse the bits', fixed width.

Approach
  1. Loop 32 times: shift the result left, OR in the lowest bit of the input, shift the input right.
  2. Fixed width matters — the loop count is 32, not 'until zero', so leading zeros are preserved.
  3. Mention the divide-and-conquer version (swap halves, then quarters) as the O(log n) approach.
Target complexity

O(32) time, O(1) space.

Pitfall

Looping until the input reaches zero. Leading zeros then vanish and the result is wrong.

Say it out loud

“The fixed width is the whole point: I loop exactly 32 times rather than until the input is zero, otherwise the leading zeros disappear and the reversal is wrong. There's a divide-and-conquer version that swaps halves then quarters in log time, worth mentioning.”

Solve on LeetCode
easySingle Number

Find the one element that appears once when every other appears twice.

Trigger

'Appears once' plus 'constant space' — the XOR signature.

Approach
  1. A hash map is O(n) space. The constraint says constant, which is the hint.
  2. XOR everything: a ^ a = 0 and a ^ 0 = a, so the pairs cancel and the singleton survives.
  3. XOR is commutative and associative, so order does not matter — say that, it is the justification.
Target complexity

O(n) time, O(1) space.

Pitfall

Reaching for a Counter. It works and ignores the constraint the problem is testing.

Say it out loud

“The constant-space constraint is the hint. XOR is its own inverse, and it's commutative and associative, so XOR-ing the whole array cancels every pair regardless of order and leaves the one unpaired value.”

Solve on LeetCode
mediumSum of Two Integers

Add two integers without using the plus or minus operators.

Trigger

'Without arithmetic operators' — the adder question.

Approach
  1. XOR is addition without carry; AND shifted left by one is the carry.
  2. Loop until the carry is zero.
  3. In Python this needs a 32-bit mask, because integers are arbitrary precision and negative numbers never terminate the loop.
  4. Convert back at the end if the result's sign bit is set.
Target complexity

O(1) — at most 32 iterations. O(1) space.

Pitfall

Writing it as if in C. In Python, without masking, negative inputs loop forever.

Say it out loud

“XOR gives the sum without carries and AND shifted left gives the carries, so I loop until there's no carry left. The Python-specific part is masking to 32 bits — integers here are arbitrary precision, so a negative number would never terminate the carry loop.”

Solve on LeetCode