了解按位二进制组合算法

Question

我一直在研究列出布尔值数组所有可能组合的算法。

例如，两个布尔值的数组可以具有以下组合：

[真，真]，[真，假]，[假，真]，[假，假]我找到了几个使用按位运算符的示例，虽然我已经查找了所用运算符的定义，但我仍然不了解它们在算法中的上下文用法。

我在下面列出了一个示例算法(来源：http://zacg.github.io/blog/2013/08/02/binary-combinations-in-javascript/)，并附有注释来描述我查看它们时所看到的内容：

function binaryCombos(n){
var result = [];
for(y=0; y<Math.pow(2,n); y++){         // This cycles through the maximum number of combinations 
(power of 2 because it's binary)

var combo = [];                         // combo for particular iteration, eventually pushed to result
for(x=0; x<n; x++){                 // iterate over number of booleans in array
//shift bit and and it with 1
if((y >> x) & 1)                // right shifts and then masks for 1? i.e. tests if it's odd??
combo.push(true);           // I don't see how this ensures all combiantions are covered
else 
combo.push(false);          // I don't understand the criteria for pushing false or true :(        
}
result.push(combo);
}
return result;
}
//Usage
combos = binaryCombos(3);

for(x=0; x<combos.length; x++){               // This looks like driver code so have been ignoring this
console.log(combos[x].join(','));
}

下面是使用 n = 2 的示例：

y = 0 x = 0

0>> 0 仍然是 0，因此当 "anded" 为 1 时，计算结果为 false：

00000000 & 0000 0001 --> 0

"假"推送到组合数组

y=0 x=1

0>> 1 仍然为 0，并将"false"推送到组合数组

推送到结果：[假，假]

y=1 x=0

1>> 0 等于没有 shift(？) 的 0000 0001，因此带有 1 的"anding"将计算为 true， "真"推送到组合数组

y=1 x=1

1>> 1 与减半相同，但会评估为 0，因此 false 被推到组合数组

推送到结果：[真、假]

y=2 x=0

2>> 0 等于 false 被推送到组合数组，因为 0000 0010 & 0000 0001 = 0

y=2 x=1

2>> 1 等于 true 被推为 0000 0001 & 0000 0001 = 1

推送到结果：[假，真]

y=3 x=0

3>> 0 等于 true 被推送到组合数组，因为 0000 0011 和 0000 0001 = 1

y=3 x=1

3>> 1 等于 true 被推到组合数组

推送到结果：[真，真]

返回的结果： [[假， 假]， [真， 假]， [假， 真]，[真， 真]]

我可以直观地看到嵌套循环将有助于解决排列，我可以认识到这已经得出了正确答案，但看不到将 y 移动 x 然后"anding"与全面涵盖所有组合之间的关系。

任何帮助表示赞赏！

Answer 1

x

是一个(从零开始的)位数。该位号是指y二进制表示中的位：最低有效位的数字为 0(在二进制表示的右侧)，最高有效位的数字为n-1。由于组合具有n布尔值，因此(y)位表示具有n位。零位转换为false,1 位转换为true。

现在，要从y的二进制表示中提取^第x位，我们可以使用 shift 运算符：

y >> x

在此操作之后，我们感兴趣的位一直向右移动。第x位右侧的所有^位都通过此>>操作"掉落"。剩下的就是去掉我们要提取的位左侧的所有位。为此，我们使用& 1.这就是隔离y二进制表示的第^x位所需的全部内容。

例

假设我们有n=4，并且外部循环已经迭代到y=13的点。y的二进制表示形式是 1101。

x上的循环将从x=0开始，因此移位操作不会做任何事情，但& 1操作将提取最右边的位 1101，即 1。

下一个内部迭代将具有x=1。现在轮班操作将把最右边踢出去，我们剩下 110 个。& 1操作现在将提取 0。 就这样持续了x=3和x=4.

这里用表格表示(n=4和y=13)：

th style="text-align： center;">(y >> x) & 1style="文本对齐：居中;">1101style="文本对齐：居中;">1101style="文本对齐：居中;">1101style="文本对齐：居中;">1101

y	xy >> x<<thead>
	boolean
	0	1101	1	true
	1	110	0	false
	2	11	1	true
	3 1		1	true