Binary Addition Algorithm

Question

I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n.

X = binary representation of 0. for i ← 1 to n

starting from right to left in X , find the first digit that is 0 and assume it is the kth digit

X ← flip the kth digit of X to 1 and flip 1,2,...,(k−1)th digit of X to 0 print X

We are thus incrementing by 1 n number of times. Essentially, the number of bit operations depends on the value of k in each iteration, but I can't seem to find a pattern for the first bit which is zero from the binary representation of 1,2,3...n. Any help?

Answer 1

The position of the first zero bit in $k$ (zero-indexed from the right; in other words, the number of $1$s the binary representation of $k$ ends with) is equal to number of times $2$ is a factor in $k+1$. (For example, $23 = 10111_2$ ends with three $1$s, and $23+1 = 24$ is divisible by $2^3$.)

There is no nicer formula for this number. The number of ending $1$s in $k=0,1,2,\dots$ is $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, \dots$$ which you can sort of see a pattern in.

But for your problem, we don't really need a formula. Instead, it's enough to observe that:

• At least $\frac12$ of the values $0,1,2,\dots,n-1$ end in $\dots0$. (And take one operation to increment.)
• At least $\frac14$ of them end in $\dots01$. (And take two operations to increment.)
• At least $\frac18$ of them end in $\dots011$. (And take three operations to increment.)

And so on. So the average number of operations it takes to increment a value between $0$ and $n-1$ is better than $$ \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \dots = \sum_{i=1}^\infty \frac{i}{2^i} = 2. $$ In other words, though some numbers take more operations than others to increment, and occasionally just before a power of $2$ you need lots of operations, the average number of bit operations to increment a number is $2$, a constant. Therefore the total number of bit operations to increment $0$ $n$ times is $O(n)$.

Answer 2

Normally we are looking for an upper bound on the number of operations. In this case there will be $\lfloor \log_2(X) \rfloor +1$ bits in the output. You are expected to produce something like this. You don't have to know how many $1$s are in the binary expansion of $X$, just an upper bound.