Bits and math tutorial

Name: Bits and math tutorial
Uploaded: 2026-10-05T03:10:10.000Z
Duration: 46 s
Description: Bits and math tutorial: Every number is a row of lamps, on or off. AND, OR and XOR flip them all at once, and x XOR x is zero, so pairs cancel.

AND, OR and XORWorld 8 tutorial

0:00 / 0:00

Every number is a row of lamps, on or off. AND, OR and XOR flip them all at once, and x XOR x is zero, so pairs cancel.

▼

Transcript

Bits and math. Every number is a row of lamps, each one on or off: thirteen is one, one, zero, one.

AND, OR and XOR hit every lamp at once. x XOR x switches every lamp off, and x XOR zero is x, so pairs cancel.

x AND x minus one knocks out the lowest lit lamp, and a shift by one doubles or halves.

The clue: every number appears twice except one, count the one bits, power of two, no extra space, no plus or minus.

The cost: one step per operation on fixed-width numbers, so one pass is linear time, constant space. Now let's use it on Single Number.