了解按位二进制组合算法

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

0000 0000 & 0000 0001 --> 0

'false' 推送到组合数组

y=0 x=1

0 >> 1 仍然是 0 并且会将 'false' 推入组合数组

推送结果：[false, false]

y=1 x=0

1 >> 0 等于 0000 0001 没有移位（？）所以 'anding' 和 1 将评估为真， 'true' 推入组合数组

y=1 x=1

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

推送结果：[true, 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

推送结果：[false, true]

y=3 x=0

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

y=3 x=1

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

推送结果：[真，真]

返回结果：[[false, false], [true, false], [false, true], [true, true]]

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

感谢任何帮助！

Answer 1

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

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

y >> x

经过这个操作，我们感兴趣的位已经一路向右移动了。 x^th 位右边的所有位都被这个 >> 操作“掉落”了。剩下的就是去掉我们要提取的位 left 处的所有位。为此，我们使用 & 1。这就是隔离 y.

的二进制表示的第 x^th 位所需的全部内容

例子

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

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

下一次内部迭代将有 x=1。现在移位操作会将最右边的位踢出，我们剩下 110。& 1 操作现在将提取 0。因此它会继续 x=3 和 x=4。

这里用table表示（对于n=4和y=13）：

`y`	`x`	`y >> x`	`(y >> x) & 1`	boolean
1101	0	1101	1	true
1101	1	110	0	false
1101	2	11	1	true
1101	3	1	1	true

了解按位二进制组合算法

Understanding bitwise binary combination algorithm

algorithm

bitwise-operators

bit-shift

bitwise-and

例子