Binary counter Pseudocode

Increment(A, k)

i = 0

while i < k and A[i] = 1

A[i] = 0

i = i + 1

if i < k

A[i] = 1

Think back to the binary counter whose subroutine, Increment, counts up from zero. Suppose we want to add a Decrement operation as well. Its pretty clear that allowing both operations slows everything down, even if we amortize. For example, an adversary could alternate between the two operations to end up with values 2k and 2k-1, each of which would flip about k bits.

Instead, we can represent a number as a pair of bit strings <b1, b2>, where for any bit position i,

at most one of the bits b1[i] and b2[i] is equal to 1. The actual value of the counter is b1 - b2. We can design this system such that a worst-case operation takes (lg k) time and the amortized cost of each operation is 4.

Write the two operations: increment and decrement. Both operations should take both b1 and b2 as parameters, and they should maintain the constraint that at most one of the bits b1[i] and b2[i] is equal to 1.