Gosper's Hack 优化

概述

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

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2024/01/04/gospers-hack/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！