枚举第1位到第n位的第k位数的最佳方法是什么？

什么是最好的方法来枚举所有的数字1至nkth位设置？枚举第1位到第n位的第k位数的最佳方法是什么？

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

一个平凡的方法是遍历n并检查是否kth位设置（通过检查num & (1 << (k-1))是1或0），但有没有更好的方式来做到这一点？

来源

2014-10-17 saurav

假设我们有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; 
     } 

    }

注意：一些位操作，我们就可以实现generateNumber(int number, int k)与O（1）时间复杂度

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; 
}

来源

2014-10-17 07:40:01

由于您删除了一位，因此您将工作减半。并增加了一些额外的开销。不知道这是否实际上更快。 – 2014-10-17 08:28:41

@KarolyHorvath你可能是对的！然而，我们可以生成O（1）中的数字（因为在我的更新的答案中），所以有机会改进:) – 2014-10-17 09:01:20

这似乎不必要的复杂.. – harold 2014-10-17 09:02:44

如果递增的数量和应该有从下方k中的部分，以上述k中的一部分的进位，其进位将跨越传播并离开第k比特0，否则它保持1

因此，所有你需要做的是开关的第k个位回：

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

只是循环，直到您已经达到上限，有点像这样（只是一个例子）

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

来源

2014-10-17 09:04:51 harold

什么是'x '在你的代码中？ – 2014-10-17 09:06:37

@PhamTrung现在更清楚了吗？ – harold 2014-10-17 09:09:25

看起来正确:)这应该比我的+1更好 – 2014-10-17 09:09:28

枚举第1位到第n位的第k位数的最佳方法是什么？

回答

相关问题