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

Question

枚举1到n具有kth位设置的所有数字的最佳方法是什么？

例如:
何时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)但有没有更好的方法来做到这一点？

Answer 1

如果你增加数字并且从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