概述
Gosper's Hack 是一种生成 N 元集合所有 K 元子集的算法,它巧妙地利用了位运算。
思想
假如把所有符合要求的二进制数 排序 后得到的数组是 S,通过任意给定的 Si,都可以计算出 Si+1。这样就可以递推出所有可能得二进制数。
而这其实很容易实现:我们只需要把最后一个 01 变成 10 ,然后把它右边的 1 全部集中到最右边即可。例如, 00111→01011 , 10110→11001 。
示例,求 0 ~ 128 之间所有二进制表示中1的数量为4的集合:
// 满足条件的数在以下区间
// 初始数 00001111
// 末尾数 11110000
// 根据上述思想可以看出, 最开始从 00001111 递推到 11110000 即可获得所有符合要求的结果集
代码实现
// 计算初始值
int subset = (1 << numSelect) - 1;
while (subset < (1 << n)) {
// 总体可以分成 两个部分,一个左边,一个右边
// 计算 lowbit
int lb = subset & -subset;
// 左边 部分计算
// subset + lb 达到的效果就是 将 最右边的 01 变成 10
int x = subset + lb;
// (subset ^ x) / lb >> 2 右边部分公式。 也就是将 左边部分 之后的 1 全部集中到 最右边。右移 两位 是把 左边部分改变的两位影响 去除
// | x 将两个 数 的 1 合并起来,不使用 + 避免影响 1 的位置
subset = ((subset ^ x) / lb >> 2) | x;
}
练习题目
leetcode: https://leetcode.cn/problems/maximum-rows-covered-by-columns/
附录
lowbit
lowbit ( n ) 定义为非负整数 n 在二进制表示下 “ 最低位的 1 及其后面的所有的 0 ” 的二进制构成的数值。
int lb = subset & -subset;