位运算

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 943 阅读时长 ≈ 3 分钟
介绍位运算及其应用

位运算介绍

位运算由按位与、按位或、按位取反、按位异或、左移、右移。

与（&）：

与运算的真值表：

a b a & b
0 0 0
0 1 0
1 0 0
1 1 1

与运算的特点是：有 0 得 0，全 1 得 1.

例：对 35 和 47 进行与运算：

1
2
3
4
    35:  0 0 1 0 0 0 1 1
  & 47:  0 0 1 0 1 1 1 1
-----------------------
         0 0 1 0 0 0 1 1

或（|）：

a b a \| b
0 0 0
0 1 1
1 0 1
1 1 1

或运算的特点：有 1 得 1，全 0 得 0.

例：对 35 和 47 进行与运算：

1
2
3
4
    35:  0 0 1 0 0 0 1 1
  | 47:  0 0 1 0 1 1 1 1
-----------------------
         0 0 1 0 1 1 1 1

取反（~）：

a ~a
0 1
1 0

反运算的特点是：1 变 0，0 变 1.

异或（^）：

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

异或运算的特点是：相同为 0，不同为 1.

异或运算有如下性质：

  1. 交换律： \(a ^{\wedge} b = b ^{\wedge} a\).
  2. 结合律： \((a ^{\wedge} b) ^{\wedge} c = a ^{\wedge} (b ^{\wedge} c)\).
  3. \(a_{1} ^{\wedge} a_{2} ^{\wedge} a_{3} ^{\wedge} \cdots ^{\wedge} a_{n}\) 的结果与 \(a_{1}, a_{2}, a_{3}, \cdots ,a_{n}\) 的顺序无关。
  4. 0 ^ x = x、1 ^ x = ~x.

右移（>>）：

右移有算术右移和逻辑右移两种，对于负数来说，算术右移在最高位补 1，逻辑右移在最高位补 0.

左移（<<）：

右移丢弃最高位，在最低位补 0.

右移相当于乘除 2，左移相当于乘 2.

位运算经典应用

置 1 与置 0

把一个 1 字节数据的第 3 位和第 4 位置 0，我们可以这样写：

1
2
char data = 0xff;
data &= ~(1 << 3 | 1 << 4);

把一个 1 字节数据的第 5 位和第 6 位置 1，我们可以这样写：

1
2
char data = 0xff;
data |= (1 << 5 | 1 << 6);

把一个把一个 1 字节数据的第 3 位和第 4 位置 0，第 5 位和第 6 位置 1，我们可以这样写：

1
2
char data = 0x0f;
data = data & ~(1 << 3 | 1 << 4) | (1 << 5 | 1 << 6);

实现加法

1
2
3
4
5
6
7
8
int add(int a, int b) {
    while (b) {
        int temp = a ^ b;
        b = (a & b) << 1;
        a = temp;
    }
    return a;
}

去掉最后一位 1

1
a &= (a - 1);

统计二进制中 1 的个数

1
2
3
4
5
6
int a = 10;
int cnt = 0;
while (a) {
    ++cnt;
    a &= (a - 1);
}

判断奇偶

1
a & 1 == 0 // 为 true 说明是偶数

反转指定位

例如翻转 data 的第 3 位：

1
data ^= (1 << 3);

交换两个数

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

lowbit 函数

1
int lowbit(int x) { return x & (-x); }

奇数变偶数

1
a & -2

如果 a 是偶数则不变，如果 a 是奇数则变为小 1 的偶数。

位运算的一些题

题一

题目描述：一个数组中有一种数出现了奇数次，其他数出现了偶数次，请你求出这个数。

思路：把所有的数异或一遍即可。

参考代码：

1
2
3
4
5
6
7
void printOddTimesNum(std::vector<int> arr) {
    int res = 0;
    for (int a : arr) {
        res ^= a;
    }
   std::cout << res << '\n';
}

题二

本题是题一的进阶题。

题目描述：一个数组中有两种数出现了奇数次，其他数出现了偶数次，请你求出这两个数

思路：先假设所有这两个数为 a 和 b，将所有的数异或一遍得到 a ^ b，然后使用 lowbit 函数求出 a 或 b 的最低位，然后以这个最低位的数据为依据，将数据划分为两部分，将其中一部分全部异或一遍即可的到 a 或 b，然后就可以求出另外一个了。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void printOddTimesNum(std::vector<int> arr) {
    int eor {};
    int rightOne {};
    for (auto a : arr) {
        eor ^= a;
    }
    rightOne = eor & (~eor + 1);
    int a = 0;
    int b = 0;
    for (auto c : arr) {
        if ((c & rightOne) == 0) {
            a ^= c;
        }
    }
    b = a ^ eor;
    std::cout << std::format("{} {}\n", a, b);
}

参考