位运算技巧

lowbit

1inline int lowbit(int x)2{3    return x & -x;4}

lowbit返回最右侧的1例如：lowbit(0b0011) == 0b1lowbit(0b001100) == 0b100lowbit(0b10101010) == 0b10lowbit(0b100) == 0b100

gcc内置位运算函数

•int __builtin_ffs (unsigned int x)返回x的最后一位1的是从后向前第几位，比如7368（1110011001000）返回4。•int __builtin_clz (unsigned int x)返回前导的0的个数。•int __builtin_ctz (unsigned int x)返回后面的0的个数，和__builtin_clz相对。•int __builtin_popcount (unsigned int x)返回二进制表示中1的个数。•int __builtin_parity (unsigned int x)返回x的奇偶校验位，也就是x的1的个数模2的结果。

gosper’s hack

用于生成$n$元集合所有的$k$元子集

 1void GospersHack(int k, int n) 2{ 3    int cur = (1 << k) - 1; 4    int limit = (1 << n); 5    while (cur < limit) 6    { 7        do_stuff(cur); 8        // do something 9        int lb = cur & -cur;10        int r = cur + lb;11        cur = ((r ^ cur) >> __builtin_ctz(lb) + 2) | r;12        // 或：cur = (((r ^ cur) >> 2) / lb) | r;13    }14}

枚举子集

1subset = mask2while subset != 0 do3    // subset 是 mask 的一个子集，可以用其进行状态转移4    ...5    // 使用按位与运算在 O(1) 的时间快速得到下一个（即更小的）mask 的子集6    subset = (subset - 1) & mask7end while

位运算技巧

lowbit

1inline int lowbit(int x)2{3    return x & -x;4}

lowbit返回最右侧的1例如：lowbit(0b0011) == 0b1lowbit(0b001100) == 0b100lowbit(0b10101010) == 0b10lowbit(0b100) == 0b100

gcc内置位运算函数

gosper’s hack

用于生成$n$元集合所有的$k$元子集

 1void GospersHack(int k, int n) 2{ 3    int cur = (1 << k) - 1; 4    int limit = (1 << n); 5    while (cur < limit) 6    { 7        do_stuff(cur); 8        // do something 9        int lb = cur & -cur;10        int r = cur + lb;11        cur = ((r ^ cur) >> __builtin_ctz(lb) + 2) | r;12        // 或：cur = (((r ^ cur) >> 2) / lb) | r;13    }14}

枚举子集

1subset = mask2while subset != 0 do3    // subset 是 mask 的一个子集，可以用其进行状态转移4    ...5    // 使用按位与运算在 O(1) 的时间快速得到下一个（即更小的）mask 的子集6    subset = (subset - 1) & mask7end while

位运算技巧

lowbit

1inline int lowbit(int x)2{3    return x & -x;4}

lowbit返回最右侧的1例如：lowbit(0b0011) == 0b1lowbit(0b001100) == 0b100lowbit(0b10101010) == 0b10lowbit(0b100) == 0b100

gcc内置位运算函数

gosper’s hack

用于生成$n$元集合所有的$k$元子集

 1void GospersHack(int k, int n) 2{ 3    int cur = (1 << k) - 1; 4    int limit = (1 << n); 5    while (cur < limit) 6    { 7        do_stuff(cur); 8        // do something 9        int lb = cur & -cur;10        int r = cur + lb;11        cur = ((r ^ cur) >> __builtin_ctz(lb) + 2) | r;12        // 或：cur = (((r ^ cur) >> 2) / lb) | r;13    }14}

枚举子集

1subset = mask2while subset != 0 do3    // subset 是 mask 的一个子集，可以用其进行状态转移4    ...5    // 使用按位与运算在 O(1) 的时间快速得到下一个（即更小的）mask 的子集6    subset = (subset - 1) & mask7end while