pattern heroPT–23LeetCode Extension

Bit manipulation

A number is a row of zeros and ones, and bit operations change all of them in one go. So many problems need no extra memory: XOR, for example, cancels equal numbers on its own.

Variant
P11 Bit manipulationXOR · 1×

Example problem: every number in [4, 7, 2, 4, 1, 7, 6, 1, 6] appears twice except one. Find that one.

041722344157667186421place valuenum—x000= 0
not reached yet; a 0 bitcurrent number; a bit that just flippedin x; a 1 bit of xa 1 bit of num: it flips xa pair that cancelled outthe number without a pair

x starts at 0 = 000: x xor 0 gives x back

x = 0 = 000num = –
01/21
restart · back · play · step
Speed
1function singleNumber(nums):
2 x = 0
3 for each num in nums:
4 x = x xor num
5 return x

← → step · space play/pause

How to recognise

numbers in pairs with one left over, counting or flipping bits, powers of two, adding binary strings, or "O(1) extra memory" over integers.

How to solve problems like this

  1. Write a few small inputs in binary and look at each bit column on its own.
  2. Pick the operation: xor cancels pairs, & tests or clears bits, | sets them, << and >> move them.
  3. Keep the answer in one integer and update it as you go, instead of keeping a set or a list.
  4. Check the edge cases: 0, a single number, the highest bit, and negative numbers in your language.

Variant: Bit by bit

The same, but take the number apart one bit at a time: look at the lowest bit, then shift the number so the next bit takes its place. Use it when something must be done with every bit, like counting the ones.

  1. Read the lowest bit with n & 1 and move to the next one with n >> 1.
  2. Do the work for each bit: count it, copy it into the answer, compare it with another number.
  3. n & (n - 1) clears the lowest 1 bit: loop on it to visit only the ones, or test a power of two with n & (n - 1) == 0.
  4. When every number appears three times but one, count the ones in each of the 32 positions; the positions whose count is not a multiple of 3 are the bits of the answer.

Where it's used

  • File permissions in Unix. Read, write and run are three bits, so chmod 755 is three groups of three bits. To check a permission, the system takes its bit with a mask.
  • RAID 5. Along with the data, RAID 5 stores its XOR. If one disk dies, the XOR of what is left restores it: everything except the lost data cancels out.
  • Search engines. Lucene and Apache Spark store sets of document numbers as bitmaps (Roaring Bitmaps). Intersecting two sets is a bitwise AND, 64 numbers per operation.