Maintaining fitstrings

Every non-negative integer can be represented as the sum of distinct positive Fibonacci numbers. (As a warmup exercise, prove this claim!) In other words, instead of a string of bits, we can represent any non-negative integer as an string of fits, where the \(i\)th least significant fit indicates whether the sum includes the Fibonacci number \(F_i\). For example, the fitstring \(101110_F\) represents the number \(F_6+F_4+F_3+F_2 = 8+3+2+1 = 14\).

Describe algorithms to increment and decrement a fitstring in constant amortized time. That is, starting with the all-zero fitstring, your algorithms must execute any intermixed sequence of \(n\) increments and \(m\) decrements in \(O(n+m)\) time, yielding a fitstring with value \(n-m\).

[Hint: Most numbers can be represented by more than one fitstring!]

Related Content