Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.