A recurrence over bit patterns

Counting for every number up to n, where doing each one separately is the obvious approach and a recurrence is better.

Why it works

Drop the lowest bit and look it up

Any number is its own value shifted right by one, with the lowest bit put back. Shifting right produces a strictly smaller number whose answer is already known.

So the count for n is the count for n right-shifted by one, plus one if n is odd. One lookup and one test, per number.

1for value in range(1, 6):2    print(f"{value} = {bin(value):>5}: halving gives {value >> 1} = {bin(value >> 1):>4},"3          f" and its own low bit is {value & 1}")

Halving is a right shift, so every answer is one already-computed answer plus a single bit.

Key idea

A second recurrence, using the other identity

There is another route using the clear-the-lowest-set-bit identity from the last lesson: the count for n is one more than the count for n & (n - 1), since that value has exactly one fewer set bit.

Both are one line and both are linear. Knowing two recurrences for the same quantity is a good sign you understand it rather than remember it.

The value it reaches back to is different, and just as reliably smaller.

1for value in (5, 6, 7, 8):2    print(f"{value} = {bin(value):>5}: clearing its lowest set bit gives"3          f" {value & (value - 1)} = {bin(value & (value - 1)):>5}")

Always strictly smaller, so iterating upward works here for the same reason it does for halving.

Predict the output· 5 min

Predict the output: the value each answer reaches back to

Two different recurrences for the same quantity are compared, by printing what each one reaches back to. Type the five lines it prints.

Python

1for value in range(1, 6):2    print(value, "-> halving reaches", value >> 1, ", clearing reaches", value & (value - 1))

Printed output

Problem· 20 min

Counting 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.

Bit Manipulation

162 / 170

Bit ManipulationLesson 2 of 5About 36 min