位运算操作

摘要: 常见的位运算操作

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在编程中，经常会使用一些位运算操作，比如用位运算来实现集合的操作。本文我们总结一下常见的位运算操作，首先介绍基础的位运算的运算符，然后介绍各种集合操作用位运算的实现方式，最后整理一下其他比较常见的位运算的问题及其代码实现，建议收藏，以后用到的时候可以查看。

1. 位运算基础运算符(C++)

与位运算相关的运算符共有 6 种，&,|,^,~,>>,<<

• &与，x & y，将两个十进制数在二进制下进行与运算，返回其十进制下的值。
• |或，x | y，将两个十进制数在二进制下进行或运算，返回其十进制下的值。
• ^异或，x ^ y，将两个十进制数在二进制下进行异或运算，返回其十进制下的值。
• <<左移，x << y，将 x 在二进制下的每一位向左移动 y 位，最右边用 0 填充。
• >>右移，x >> y，将 x 在二进制下的每一位向右移动 y 位，最左边用 0 填充。
• ~取反，~x，将 x 在二进制下的每一位取反，返回其十进制下的值。

2. 位运算表示集合操作

用位运算可以表示集合的常见操作，如下，其中 A, B, 表示两个集合，c 表示某个元素。

• c 插入 A : A |= (1 << c)
• A 删除 c : A &= ~(1 << c)
• A 置空 : A = 0
• 并集 : A | B
• 交集 : A & B
• 全集 : (1 << n) - 1
• 补集 : ((1 << n) - 1) ^ A

• 子集 : (A & B) == B

• 枚举 A 的子集

for(int subset = A; ; subset = (subset - 1) & S)
{
    (...)
    if(subset == 0) 
        break;
}

• 枚举 A 的真子集

for(subset = (A - 1) & A; subset != A; subset = (subset - 1) & A)
{
    ...
}

• 枚举全集的子集

for(i = 0; i <= (1 << n) - 1; ++i)
{
    ...
}

3. 位运算的其它操作

• 判断是否是 2 的幂 : n & (n - 1) == 0
• 最低位的 1 变为 0 : n &= (n - 1)
• 统计 1 的个数

int ones(int x)
{
    int cnt = 0;
    while(x)
    {
        x = x & (x - 1);
        ++cnt;
    }
    return cnt;
}

• 最低位的 1: n & (-n)，最低位的 1 一般记为 lowbit(n)，表示 n 的二进制表达式中最低位的 1 所对应的值。

• 最高位的 1:

int p = lowbit(n)
while(p != n)
{
    n -= p;
    p = lowbit(n);
}
return p;

---