首页 算法学习

常见位运算的技巧

更详细参考：分享｜从集合论到位运算，常见位运算技巧分类总结！ - 力扣（LeetCode）

计算一个数的二进制表示中1的个数

假定x是一个32位整型变量
最容易想到的做法如下：

1
2
3
4
5
6
7
8
9
unsigned popCount(int x)
{
    unsigned ans = 0;
    while (x){
        ans += (x & 1) == 1 ? 1 : 0;
        x >>= 1;
    }
    return ans;
}

还可以Brian Kernighan 算法，这个算法说的是对于一个数x，x&(x-1)可以获得x删去二进制表示中最右侧的1后的结果。

1
2
3
4
5
6
7
8
9
unsigned popCount(int x)
{
    unsigned ans = 0;
    while (x){
        x = x & (x - 1);
        ans++;
    }
    return ans;
}

还可以利用与运算的技巧

1
2
3
4
5
6
7
8
9
unsigned popcount (unsigned x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);//计算原数[k, k+1]区间内的1的总数，并将结果放在[k,k+1]，k=1,3,5,...31
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);//计算原数[k, k+3]区间内1的总数，并将结果放在[k,k+3]，k=1,5,9,...29
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);//计算原数[k, k+7]区间内1的总数，并将结果放在[k,k+7]，k=1,9,17,25
    x = (x & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);//计算原数[k, k+15]区间内1的总数，并将结果放在[k,k+15]，k=1,17
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);//计算原数[k, k+31]区间内1的总数，并将结果放在[k,k+31]，k=1
    return x;
}

上面的x&0x55555555可以将x的偶数位全置0，其余类似，这种做法在位运算中很常见。

lowbit

x&(-x)可以获得x的最低位的1，例如6&(-6)=(110)&(010)=010，举例

1
2
3
4
5
6
7
int ans = 0;
// 计算x的二进制中1的个数
while(x > 0)
{
    x -= x & -x;
    ans++;
}

lowbit所在的位数

可以用c++内置函数

1
__builtin_ctz(x&-x)

删除x的二进制形式中最右边的1，其余保持不变

x&(x-1)，可参考如何理解x&(-x)和x&(x-1) - 一只小阿狗 - 博客园 (cnblogs.com)，等价于x-x&(-x)

枚举一个数的二进制子集

1
2
3
4
// 枚举s的二进制子集
for (int i = s; i; i = (i - 1)&s){
    
}

枚举一定范围内固定大小的子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def count_trailing_zeros(x):
    return (x ^ (x - 1)).bit_length() - 1

def count(m, n):
    """
    枚举小于2^n的所有m位二进制数
    """
    cur = (1 << m) - 1
    limit = 1 << n
    while cur < limit:
        lb = cur & -cur
        r = cur + lb
        cur = ((r ^ cur) >> count_trailing_zeros(lb) + 2) | r
        print(bin(cur))

一图流

1686879866-VArRlW-Binar_Fundamentals_00

编程语言实现

术语 Python Java C++
集合大小（元素个数） s.bit_count() Integer.bitCount(s) __builtin_popcount(s)
二进制长度（减一得到集合中的最大元素） s.bit_length() 32-Integer.numberOfLeadingZeros(s) 32-__builtin_clz(s)
集合中的最小元素 (s&-s).bit_length()-1 Integer.numberOfTrailingZeros(s) __builtin_ctz(s)
更新于 阅读次数 次