Bit Manipulation

The operators, and what each is for

Six operators, each with one job. Learn the jobs rather than the truth tables.

Key idea

What each operator is used for

The truth tables are worth knowing and are not what you reach for. What you reach for is the job each operator does.

Operator	Job	Idiom
and	test or clear bits	n & 1 tests the lowest bit
or	set bits	n \| mask turns on everything in mask
xor	flip bits, or cancel pairs	n ^ n is 0
not	invert every bit	in Python this gives a negative number
left shift	multiply by a power of two	1 << k is a mask for bit k
right shift	divide by a power of two	n >> 1 drops the lowest bit

Those idioms cover most of what these problems need. Python also prints binary directly, which is worth using while learning rather than converting by hand.

Why it works

Walking the bits of a number

The standard loop tests the lowest bit and shifts right, which is the same shape as the digit loop from Unit 0 with two in place of ten.

It stops when the number reaches zero, so it runs once per bit up to the highest set one rather than a fixed number of times. That matters when a problem specifies a width.

Four steps for a four-bit number, so this loop runs once per bit rather than once per set bit.

Key idea

Clearing the lowest set bit

There is a faster loop, and the identity behind it is worth understanding rather than memorizing. Subtracting one from a number flips its lowest set bit to zero and turns every zero below it into a one.

Combining that with the original using and clears exactly the lowest set bit and leaves everything else. So n & (n - 1) removes one set bit per step, and the loop runs once per set bit rather than once per bit.

Three steps for 13 rather than four, because this loop runs once per set bit.

Tip

Read the middle line

For 8, which is a single set bit, subtracting one gives all ones below it and the and produces zero. That is also the test for whether a number is a power of two: n > 0 and n & (n - 1) == 0.

Deriving that test from the identity, rather than recalling it, is the difference between using this and reciting it.

Gotcha

Python's integers are not fixed width

These problems are written for languages with 32-bit integers. Python's integers are arbitrary precision and conceptually have infinitely many sign bits, so ~n gives a negative number and right-shifting a negative value never reaches zero.

That means a loop like the one above never terminates on a negative input. Handling that properly is the subject of the last lesson in this unit, and until then assume the inputs are non-negative.

Bit drills

Four small functions using the idioms above. is_power_of_two reports whether a positive number has exactly one set bit. lowest_set_bit returns the value of the lowest set bit, or 0. set_bits returns the indexes of every set bit, lowest first. swap_bits returns the number with the bits at two given indexes exchanged.

Python

Loading editor…

Tests

print(is_power_of_two(8), is_power_of_two(12), is_power_of_two(0))
print(lowest_set_bit(12), lowest_set_bit(8), lowest_set_bit(0))
print(set_bits(13), set_bits(0))
print(swap_bits(0b1001, 0, 1), swap_bits(0b1010, 1, 3), swap_bits(0b1010, 0, 1))

Output

Run the tests when you are ready.

Number Of 1 Bits

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Loading the workspace…