Gosper’s Hack 优化

发布于 2024-01-04  34 次阅读


概述

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


本当の声を響かせてよ