如何枚举在1到n之间所有第k位为1的数字？

Question

什么是枚举1到n之间所有第k位设为1的数字的最佳方法？

例如： 当n = 12且k = 1时，答案将是1、3、5、7、9和11。 如果k = 2，则答案将是2、3、6、7、10和11。

一种简单的方法是循环遍历n并检查第k位是否设置（通过检查num & (1 << (k-1))是否为1或0），但是否有更好的方法来做到这一点？

- saurav

Answer 1

如果你增加一个数字，下面的第k位应该向上一位产生进位，那么进位会传播并使得第k位为0，否则它保持为1。

所以你需要做的就是重新设置第k位的值为1：

x = (x + 1) | (1 << k);

只需循环执行此操作，直到达到上限，就像这样（仅为示例）

for (int x = 1 << k; x < n; x = (x + 1) | (1 << k))
    print(x); // or whatever

- harold

---

看起来没错 :) 这应该比我的更好 +1 - Pham Trung

Answer 2

假设我们有n位，第k位固定为1，那么我们要寻找的数字看起来像是xxxx1xxxx，因此我们只需要生成所有(n-1)位的数字。

例如，如果我们有3位，并且我们希望第2位被设置，那么我们只需要生成2^(n-1)=4个数字，最终的数字看起来像是：x1x

因此，这些数字是0(00)、1(01)、2(10)、3(11)->在第2位添加，我们要寻找的最终数字是2(010)、3(011)、6(110)、7(111)

伪代码:

   int n = ...//User input
   int bit = numberOfBitUsed(n)
   for(int i = 0; i < (1<<bit); i++){
       int number = generateNumber(i, k);
       if(number > n){
          break;
       }

   }

注意：通过一些位操作，我们可以实现具有O(1)时间复杂度的generateNumber(int number, int k)函数。

 int generateNumber(int val, int k){
    int half = Integer.MAX_VALUE & ~((1<<k) - 1);//Mask for bit from 31 to k 
    int a = half & val;
    a <<=1;
    int b = ((1<<k) - 1) & val;
    int num = a | b | (1<<k);
    return num;
 } 

- Pham Trung

---

你通过移除一个比特位减少了一半的工作量，但同时增加了一些额外的开销。不确定这是否真的更快。 - Karoly Horvath

@KarolyHorvath 你说得没错！但是，我们可以在O(1)时间内生成数字（就像我更新的答案中一样），所以有改进的机会 :) - Pham Trung