[问题] 利用整数的位元运算,列举所有组合

楼主: xxxx9659 (嘎嘎嘎嘎嘎)   2022-01-24 19:22:40
最近在想一个问题,想要用一个整数,来代表一种组合
然后把 C(28, 5) 的所有组合,快速轮询过一遍
C(28, 5) = 98280 有点大不好举例,拿 C(6, 3) = 20 来当例子
var state = 56; //代表二进制的 111000
do {
console.log( state );
} while ( state = next(state) );
循环会印出以下20个值
56 //代表二进制的 111000
52 //代表二进制的 110100
50 //代表二进制的 110010
49 //代表二进制的 110001
44 //代表二进制的 101100
42 //代表二进制的 101010
41 //代表二进制的 101001
38 //代表二进制的 100110
37 //代表二进制的 100101
35 //代表二进制的 100011
28 //代表二进制的 011100
26 //代表二进制的 011010
25 //代表二进制的 011001
22 //代表二进制的 010110
21 //代表二进制的 010101
19 //代表二进制的 010011
14 //代表二进制的 001110
13 //代表二进制的 001101
11 //代表二进制的 001011
7 //代表二进制的 000111
位元运算 a & (a-1) 可以迅速的拔掉最低位元的1
左移右移 << >> 感觉也很好用
就在想说,能不能利用这种位元运算的高效率特性,来实作 next()
但是 next() 我还没有实作出来... 不知道是不是真的可行
想说问问看各位大大的看法
作者: fenzhang (分帐)   2022-01-24 20:05:00
作者: FRAXIS (喔喔)   2022-01-25 02:25:00
搜寻 Gosper's hack 就有了 Wikipedia 上有解释
楼主: xxxx9659 (嘎嘎嘎嘎嘎)   2022-01-25 17:14:00
感谢楼上两位大大!!

Links booklink

Contact Us: admin [ a t ] ucptt.com