Gosper's Hack Optimization

概述

当我们在n个数中选择m个数字，通常的做法是回溯法、状态压缩（二进制枚举）等等。这样的复杂度是 $O(2^n)$，而 Gosper’s Hack 可以在O(1)的时间内找到下一个枚举状态。

思路

  1. 从后往前找到第一个降序（即”01”），然后将其变为”10”，
  2. 最后将该”10”后面的序列逆转即可。

假设当前状态 cur 为 0110(01)1000，那么下一个状态为 0110(10)0001

  1. cur + lowbit = r, 前半部分，0110(10)xxxx
  2. r ^ cur，记录变化的位数（例如一位就是0001，两位就是0011），移除”01”变为”10”的2次。”10”后面就是变化次数-2。xxxxxx(10)0001

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> GospersHack(int m, int n) {
    std::vector<int> ans;
    int set = (1 << m) - 1;
    int limit = (1 << n);
    while (set < limit) {
        ans.push_back(next_status(set));
        int lowbit = set & -set;
        int r = set + lowbit;
        set = (((r ^ set) >> 2) / lowbit) | r;
        // set = next_status(set);
    }
    return ans;
}
1
2
3
4
5
6
int next_status(int cur) {
    int lowbit = cur & -cur;
    int r = cur + lowbit;
    return (((r ^ cur) >> 2) / lowbit) | r;
    // return ((r ^ cur) >> __builtin_ctz(lowbit) + 2) | r;
}
1
2
3
4
5
6
7
8
9
def next_status(cur: int):
    lowbit = cur & -cur
    r = cur + lowbit
    return (((r ^ cur) >> 2) // lowbit) | r
    '''
    def count_trailing_zeros(x):
        return (x & -x).bit_length() - 1
    return ((r ^ cur) >> count_trailing_zeros(lowbit) + 2) | r
    '''

Reference