Integers with consecutive nonzero digits in base 2

Question

Note that $2016=11111100000$. How many integers $\le n$ have their nonzero bits consecutive in their binary (base $2$) expansion? The case $n=2^m-1$ is easy. The question is about a closed formula for the other cases.

Answer 1

(This follows @Snow's answer and comment.)

You say the case $n=2^m-1$ is easy. The job becomes easier for the general case if you know how many bits are in the decimal representation of $n$ (call it $m$) and how many consecutive bits, starting with the most significant bit, are ones (call it $k$). Here are "closed formulas" for those numbers.

$$m=\lfloor\log_2(2n+1)\rfloor$$ $$k=m-\left\lfloor\log_2\left(2^{m+1}-2n-1\right)\right\rfloor$$

The "$\lfloor\cdot\rfloor$" is the greatest integer function. If $n=0$ these formulas give the sensible values $m=k=0$: getting sensible defined values for $n=0$ and $n=2^m-1$ required some complications in my formulas.

For any given $2^j-1$, the numbers with consecutive nonzero bits that start with the first bit are

$$111\ldots 11,\ 111\ldots 10,\ \ldots,\ 110\ldots 00,\ 100\ldots 00 $$

which means $j$ of them. Such numbers not starting at the first bit of the original $2^j-1$ are counted as $1+2+3+\cdots+(j-1)=\frac{j(j-1)}2$.

For a given $n$, which has $m$ bits total and starting with $k$ consecutive one bits, there are $k$ relevant numbers that start at the first bit and $\frac{m(m-1)}2$ that do not. This makes the total count $k+\frac{m(m-1)}2$. Substituting the formulas I gave above until the only variable is $n$ and simplifying a bit gives our final answer:

$$\frac{(\lfloor\log_2(2n+1)\rfloor)(\lfloor\log_2(2n+1)\rfloor+1)}{2}-\left\lfloor\log_2\left(2^{\lfloor\log_2(2n+1)\rfloor+1}-2n-1\right)\right\rfloor$$

Messy, isn't it! Note that this does not include the number zero in the count. If this is desired, just add one to the formula. This formula checks in Microsoft Excel for $0\le n\le 511$.

Answer 2

Hint: Let $n$ be in $[2^m-1, 2^{m+1}-1)$. You know how many such numbers there are less than $2^m-1$. The remaining numbers begin with 1 in the $(m+1)$-th digit and then can have the following $i$ digits equal to 1 and remaining $m-i$ digits equal to 0.

Therefore, there are $i$ such numbers in $(2^m, 2^{m-1})$. Not all of these are going to be less than $n$, so write $n$ in binary and it should be clear how to count how many such numbers are less than $n$.