# What is the formula for finding all binary numbers below B with the number of bits == 1 staying constant?

Maybe better explained with an example:

Binary number B = 1100, every number less than B is 1010, 1001, 0110, 0101, 0011. (With 2 bits == 1)

So the total ways of expressing the number B and all numbers less than B that contains 2 bits == 1 is 6, or 3+2+1.

I suspect this is a Combinations problem, but my math skills are kind of rusty, and I cannot deduce a consistent formula for different binary numbers.

I have done my search on the web, but could not find anything that gave me an answer to this particular problem.

Let $F(x,y) = \sum_{n = 0}^\infty x^n y^{s_2(n)}$, where $s_2(n)$ is the number of 1s in $n$'s binary representation. Then $$F(x,y) = F(x^2, y) + xy F(x^2,y)$$ Hence $$F(x,y) = (1 + xy)F(x^2,y)$$ For a given $n$, we want to calculate the number of $n' \le n$ which have the same number of 1s in binary as $n$. So let $G(x,y)$ be the generating function where the coefficient of $x^n y^k$ is the number of integers less than or equal to $n$ with $k$ 1s in their binary representation. Then $$G(x,y) = (1 + x + x^2 + \cdots) F(x,y) \implies F(x,y) = (1-x)G(x,y)$$ Hence \begin{align*} (1-x)G(x,y) &= (1 + xy)(1 - x^2)G(x^2,y) \\ G(x,y) &= (1 + xy)(1 + x) G(x^2,y) \end{align*}

The problem amounts to extracting the coefficients of the generating function $G(x,y)$. One can write an algorithm to do this, but an exact formula is probably not going to easy.

If $B$ is not of the form $2^k-1$, so the largest number with $k$ bits, it is easier to split the problem into two. Find $k$, the largest number such that $2^k-1 \lt B$. Let $n$ be the number of bits you want. Then up to $2^k-1$ there are $k \choose n$ such numbers. In the range $[2^k,B]$ you have to have the leading bit a $1$, so can choose $n-1$ more bits. It is the same as the number of numbers with $n-1$ bits in the range $[0,B-2k]$, which gives a recursive algorithm:

function nums(B,n): returns the number of numbers less than or equal to $B$ with $n$ bits in base 2

$k=\lfloor \log_2 (B+1) \rfloor$: let $k$ be the largest number such that $2^k-1 \le B$

if $B=2^k-1$: return $k \choose n$
else: return ${k \choose n} + \text{nums}(B-2^k,n-1)$

• Thanks for the quick answer! I do not understand the language of the algorithm. I wrote a recursive C function to find the actual binary numbers, and can get the number of possible binary numbers that way by simple counting. Not very elegant, so I hoped there was a simple formula taking into account the size of the number and the bits == 1 involved. Commented Sep 27, 2013 at 20:07
• It is pseudocode, but should be easy to translate to C. I think I improved the formatting-it is hard to get the spacing to stay as you want. It is implementing what I describe above-do you understand the $2^k-1$ case first? Commented Sep 27, 2013 at 20:19
• I suppose you mean B can not be a binary number with 1s only (no zeroes) The binary numbers I use will always contain at least one 0 and at least one 1. Commented Sep 27, 2013 at 20:29
• Sure, it could have all 1s. The reason the $2^k-1$ case is easy is because you have all strings of length $k$ available. You then just need to pick any $n$ positions to put 1s in. The hard part is if $B$ is not of that form, some of the numbers with $n$ 1 bits will be larger than $B$. The else case takes care of that. The first part is all the bit strings of length k, and the second part is the strings of length k+1 starting with 1 and having the rest of the n-1 1's in positions so the total is less than $B$ Commented Sep 27, 2013 at 21:07

Short version: if the number $n$ has $1$s in bit positions $\{i_1,i_2,\dots,i_k\}$ (where we count from the right starting with bit position $1$) then the number of binary numbers that are less than $n$ and have exactly $k$ $1$s is $$\binom{i_k-1}{k} + \binom{i_{k-1}-1}{k-1} + \dots + \binom{i_1-1}{1} .$$ In your example you have $k=2$, bit positions $\{3,4\}$ so the number is $\binom{3}{2}+\binom{2}{1}=5$.

Long version: I think of this problem as one of ranking and unranking $k$-subsets of $[n]=\{1,2,\dots,n\}$ in the colex order. We order subsets of $\mathbb N$ in the colex order by saying $B<A$ if $\max(A \Delta B) \in A$, or in other words the largest element that they treat differently is in $A$. The correspondence with numbers in binary is by positions of $1$s. If $A$ is a $k$-set then the number of predecessors in colex order is the union of $k$-sets $B$ with $\max(B)<\max(A)$, $k$-sets with $\max(B)=\max(A)$ but which differ in the second largest element, and so on down. These sets are counted by the terms in the sum above.

Thanks to all who posted answers. Some of your math is a mouthful (for me!).

http://en.wikipedia.org/wiki/Permutations gave me the answer, utilizing factorials. The figure called "Permutations of multisets" gave me the solution. See the rightmost column in the figure with 2 red balls and 2 blue balls. When we disregard the ordering of the balls, the solution is perfect for the stated problem.

• That is fine as long as $B$ has $n$ one bits first. It won't solve the problem if you want all numbers with two one bits up to $1010$, because it allows $1100$. If $B$ has $n$ one bits first, it is just like the $2^k-1$ case in my answer (as all the ones from $B$ to $2^k-1$ will have more than $n$ one bits) Commented Sep 27, 2013 at 23:57
• @RossMillikan I am not sure I understand, maybe I was unclear with my explanation of the problem. The number I start with will always be the highest number possible within the constraint of the number of digits, i.e. the binary digits 1 will always be the most significant bits. Commented Sep 28, 2013 at 4:57