A binary counter of k bits starts at zero and is incremented n times. Give the exact total number of bit flips, then extend to a counter supporting both increment and decrement and say what breaks.

A binary counter of k bits starts at zero and is incremented n times. Give the exact total number of bit flips, then extend to a counter supporting both increment and decrement and say what breaks.

Approach: Count how often each bit position changes across n increments, then look for a potential function for the two-operation version and check whether one exists.

2n - s_2(n), where s_2(n) is the number of ones in the binary form of n. Bit i flips once every 2^i increments, so the total is the sum over i of floor(n/2^i), which telescopes to 2n - s_2(n) and is therefore below 2n. The potential argument gives the same bound: with Phi equal to the number of ones currently set, an increment that clears t trailing ones costs t + 1 actual flips and changes Phi by 1 - t, so the amortised cost is 2. Adding decrement breaks it. From the state 0111...1, alternating decrement and increment flips all k bits every operation, so m operations cost Theta(mk), and no potential function can rescue it since Phi would have to fall by k on the decrement and fall by k again on the increment that undoes it. A redundant representation with digits in {-1, 0, 1} restores O(1) amortised for both operations.

Follow-up: How does the redundant binary representation achieve O(1) worst case rather than only O(1) amortised?

Key concepts: amortised cost, potential function, bit flips, trailing ones.