我需要生成所有2^(n-1)
n
位数,其中位i
始终是0
,j
是可能数字列表中数字的索引。下面是一个简单的表格,当i
从0到2变化,n
是3时,j
从0到3变化。结果是一个3位数,因此n
将是3,可能的数字数将是4。
j 0 1 2 3
i
0 0 2 4 6
1 0 1 4 5
2 0 1 2 3
或者在binary中:
j 00 01 10 11
i
00 000 010 100 110 // Note the LSB (1s place) bit is never set in this line
01 000 001 100 101 // The 2s place bit is not set in this line
10 000 001 010 011 // The 4s place bit is not set in this line
这是我能想到的最好的:
unsigned result = (j&1)<<(i==0)|(j&2)<<(i!=2);
然而,通过比较单独检查i
不会缩放,并且仅适用于上述表,而不适用于n
或i
的任意值。
有没有人能想出一种更通用,更有效的方法来生成所有n
位的数字,其中i
位为0?
3条答案
按热度按时间k2fxgqgv1#
使用
j >> i << i
清除低i
位,并将其添加到j
以使高位加倍,有效地将它们左移一位:t = j + (j >> i << i);
esyap4oy2#
下面是一个生成这些数字的经典方法:
实现
setNlowestBits
无论你想要的,有各种各样的实现在互联网上。mask
在允许改变的每一位都有一个1,x - mask
就像从整数中减去-1,但有一些“洞”。任何借入都通过“洞”传播,因为“洞”中有零。然后& mask
重置“孔”中的任何位,这些位是通过借位设置的。在这种情况下,只有一个孔,但这种技术也适用于更多的孔。使用x86平台的现代指令,您可以在一个步骤中直接将
j
转换为所需的数字:其中
mask
与前面的相同,或者如果您喜欢,只需~(UINT32_C(1) << i)
。oogrdqng3#
你要求的是比不起作用的东西“更简单”的东西。对我来说,最好是从真正有效的东西开始。一旦你有了它,你可以寻找改进和优化。
这里值得一提的是一个应该工作的函数(为了简单起见,省略了边界检查):
看看它的实际效果:
输出量: