Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.