Problem Detail: A binary counter is represented by an infinite array of 0 and 1. I need to implement the action $text{add}(k)$ which adds $k$ to the value represented in the array. The obvious way is to add 1, k times. Is there a more efficient way?
Asked By : student
Answered By : A.Schulz
Well, surely there is. As a first thing I would convert $k$ to its binary representation $text{bin}(k)$. If $c$ is the current value of your counter then in order to perform $text{add}(k)$ just update the counter by setting it to $text{bin}(c)+text{bin}(k)$. If you don’t know how to add binary numbers efficiently, think how you would have done it using pen and paper. For small $kin O(log c)$ the repeated increment might be efficient though.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6627
