Free the Chinese Rings

The Chinese rings puzzle is a row of rings on a bar. Number them 1, 2, 3 and so on from the right. A move puts one ring on the bar or takes one off, and only these moves are allowed:

• ring 1 can always be moved;
• for any k of 1 or more, ring k + 1 can be moved only when ring k is on the bar and every ring below it (rings 1 to k - 1) is off.

The state of the puzzle is a whole number n whose bit i (counting from 0 at the right) is 1 when ring i + 1 is on the bar. Write fewest_moves(n) that returns the smallest number of moves that take every ring off the bar, reaching state 0.

Examples

fewest_moves(3)   # returns 2
fewest_moves(4)   # returns 7
fewest_moves(6)   # returns 4
fewest_moves(0)   # returns 0

State 3 is 11: rings 1 and 2 are on. Ring 2 may move (ring 1 is on and there is nothing below it), so take it off, then ring 1: two moves. State 4 is 100, only ring 3 on, and freeing it takes seven moves: 100, 101, 111, 110, 010, 011, 001, 000.

Constraints

• 0 <= n <= 10**18