Working with the bits directly

Numbers are stored as bits, and operating on them directly is occasionally the whole solution rather than a micro optimisation.

The operators

  12 = 1100
  10 = 1010
  &    1000  = 8
  |    1110  = 14
  ^    0110  = 6

The idioms worth knowing

n & 1 == 0          # even
n >> 1              # divide by two
n & (1 << k)        # is bit k set
n | (1 << k)        # set bit k
n & ~(1 << k)       # clear bit k
n ^ (1 << k)        # flip bit k
n & (n - 1)         # clear the lowest set bit
n & (n - 1) == 0    # power of two, for n > 0

That second to last one deserves a look. Subtracting one flips the lowest set bit to zero and everything below it to one; the AND then clears it. Repeating it counts the set bits in as many steps as there are bits set, rather than scanning all 32.

XOR is the useful one

XOR has three properties that combine into a trick:

a ^ a = 0        anything cancels itself
a ^ 0 = a        zero changes nothing
order does not matter

So: every element of an array appears twice except one. Find it.

def find_single(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

Every pair cancels to zero and the lone value survives. O(n) time, O(1) space, no hash set, no sorting.

Where it genuinely matters

Sets of small size, where a 32 bit integer represents a subset and union, intersection and difference become one instruction each. This is what makes bitmask dynamic programming possible.

Flags, where eight booleans live in one byte.

Outside those, clarity usually wins. n % 2 == 0 is clearer than n & 1 == 0 and modern compilers produce identical code, so choosing the bit version for speed is optimising something that was never slow.