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?
Implementing addition for a binary counter
algorithms;data structures;efficiency
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 $k\in O(\log c)$ the repeated increment might be efficient though.