我一直在研究列出布林值陣列的所有可能組合的演算法。
例如，一個包含兩個布林值的陣列可以有以下組合：[true, true]、[true, false]、[false, true]、[false, false]
我發現了幾個使用按位運算子的示例，雖然我查找了所用運算子的定義，但我仍然不了解它們在演算法中的背景關系使用。
我在下面列出了一個示例演算法（來源：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，因此當與 1 'anded' 時將評估為 false 為：
0000 0000 & 0000 0001 --> 0
'false' 推送到組合陣列
y=0 x=1
0 >> 1 仍為 0 并將“false”推入組合陣列
推到結果：[假，假]
y=1 x=0
1 >> 0 等于 0000 0001 沒有 shift(?) 所以 'anding' with 1 將評估為 true，'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 被推送到組合陣列
推到結果：[真，真]
回傳結果：[[false, false], [true, false], [false, true], [true, true]]
我可以直觀地看到嵌套回圈將有助于解決排列，我可以認識到這已經得出了正確的答案，但無法看到將 y 移動 x 和“與”之間的關系，并全面覆寫所有組合。
任何幫助表示贊賞！
uj5u.com熱心網友回復：
x是一個（從零開始的）位數。該位編號指的是二進制表示中的一個位y：最低有效位的編號為 0（在二進制表示的右側），最高有效位的編號為n-1。由于組合具有n布林值，因此位表示（of y）具有n位。零位轉換為false，1位轉換為true。
現在，要從 的二進制表示中提取第xth位y，我們可以使用移位運算子：
y >> x
在這個操作之后，我們感興趣的位一直向右移動。位于x第 th位右側的所有位都通過此>>操作“下降” 。剩下的就是去掉我們想要提取的位左邊的所有位。為此，我們使用& 1. 這就是隔離的二進制表示的x第 th位所需的全部內容y。
例子
假設我們有n=4并且外回圈已經迭代到y=13. 的二進制表示y為 1101。
回圈以x開始x=0，因此移位操作不會做任何事情，但該& 1操作會提取 1101 的最右邊位，即 1。
下一個內部迭代將具有x=1. 現在移位操作將把最右邊的位踢出去，我們剩下 110。& 1操作現在將提取 0。所以它繼續x=3和x=4。
這里用表格表示（forn=4和y=13）：
y |
x |
y >> x |
(y >> x) & 1 |
布林值 |
|---|---|---|---|---|
| 1101 | 0 | 1101 | 1 | 真的 |
| 1101 | 1 | 110 | 0 | 錯誤的 |
| 1101 | 2 | 11 | 1 | 真的 |
| 1101 | 3 | 1 | 1 | 真的 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340381.html
上一篇：具有O(logn)和θ(logn)時間復雜度的演算法
下一篇：將缺少的類別附加到行中