Topic 07 of 15
Bit Manipulation
A row of light switches.
Computers keep numbers as rows of light switches: 1 is on, 0 is off. Flipping, checking and combining switches is very fast. A few tiny tricks, like n & (n - 1) turning off the lowest switch, solve whole problems in one line.
What you will be able to do
AND, OR, XORChecking and setting a bitn & (n - 1)XOR to cancel pairsBitmasks for subsets
0/10
Meet the bits
01 / 04
13 is the switches 1101: eight plus four plus one.
- answer
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Count set bits in an integerCount how many 1s a number has in binary, by knocking out the lowest 1 again and again.Bit tricks
- 02Find the two non-repeating elements in an array of repeating elementsEvery number in the list has a twin except two loners; cancel the twins with XOR, then split the loners apart by one bit.XOR tricks
- 03Count number of bits to be flipped to convert A to BCount how many light switches you must flip so one row of switches looks exactly like another.Bit tricks
- 04Count total set bits in all numbers from 1 to nCount every 1 you would write if you wrote all numbers from 1 to n in binary, by counting each column with its repeating pattern.Bit column counting
- 05Program to find whether a no is power of twoDecide whether a number is 1, 2, 4, 8, 16 and so on, by checking that its bits have exactly one 1.Bit tricks
- 06Find position of the only set bitA number has exactly one bit switched on; find which spot it is in, or say -1 if there is not exactly one.Bit masks
- 07Copy set bits in a rangeLook through a window over the bits of N, and switch on the same bits in M wherever N has a 1.Bit masks
- 08Divide two integers without using multiplication, division and mod operatorShare stickers into packs without a divide button, by taking away the biggest boxes of packs first.Shift and subtract
- 09Calculate square of a number without using multiplication, division and pow()Find n times n using only adding and doubling, by splitting n into powers of two like 8 + 4 + 1.Shift and add
- 10Power SetList every possible bag you could pack from a set of items, by letting the bits of the numbers 0 to 2^n - 1 say which items go in.Bitmask enumeration