有n个1的递增二进制序列 - 一道简单的面试题

题目是这样的:

 There is a sequence of increasing numbers that
 have the same number of binary 1s in them.
 Given n, the number of 1 bits set in each number.
 Write an algorithm or C program to find the n’th number in the series.

明显, 最小的满足条件的二进制数为n个1. 紧接着其后的数都是n+1位二进制数, 而序列中的第n个数为11…01, 即n个1加上倒数第二个0. 知道了这些, 不难用n表示出答案为2^(n+1)–3. 原题就是这样. 但是显然, 这道题目原意是要给出这个序列中第K个数而不是第n个数, 所以题目还没有完. 我们的这个无穷的二进制序列应该是怎么样的呢? 容易想到, 它应该是这样的: (n=4)

1111
10111
11011
....
100111
....
1000111
....

按照刚才的思路, 我们首先考虑这个二进制有几位. 对于一个n+k进制数, 第一位必须为1, 而剩下的n+k–1位共有C(n+k–1, k)种情况. 这也就是n+k位进制数, 并且其中一共有n个1的二进制数的个数. 那么给定数K, 我们要找最大的k, 使得K大于1+ C(n+1–1, 1) + C(n+2–1, 2) + C(n+3–1, 3) + … + C(n+k–1, k). 注意到, 1=C(n, 0), 利用组合公式C(m, n) = C(m–1, n–1) + C(m–1, n),以上和式可以化简为C(n+k, k). 这下就简单了, 我们只要找到能够使C(n+k, k) < K的最大的k, 那么我们的二进制数就是n+k位的. 接下来的思路是类似的. 我们要确定第二位是1还是0, 我们假设是0, 检查这种情况下, 余下的二进制位的组合可能共有多少. 这仍然是一个组合数N的计算. 如果K小于这个组合数N, 那么这位就是0, 反之, 这一位就应该是1, 并且我们用K-N继续进行计算, 直到最后一位. 可以看到, 这种方法虽然不能给出第K个二进制数的直接表达式, 但是如果说组合数的计算是基本操作的话, 我们只需要用log(K)步计算就能得到这个二进制数.