概述

当我们在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

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;
}

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

• ProgrammingForInsomniacs
• 2397. 被列覆盖的最多行数
• 31. 下一个排列