【 C/C++】应该知道的位操作总结

Fivk

2021 年 09 月 12 日

1575 次浏览

暂无评论

1239字数

知识总结

在解题之前理解一下为什么需要位运算？它的本质是什么？

力扣上不少位运算相关的题，并且很多题也会用到位运算的技巧。这又是为什么？

### 位运算的由来

在计算机里面，任何数据最终都是用数字来表示的（不管是我们平时用的软件，看的图片，视频，还是文字）。

并且计算机运算单元只认识高低电位，转化成我们认识的逻辑，也就是 0 1 。

这就是导致计算机里面任何数据最终都是用二进制（0 1）来保存的数字。只是我们平时看到的图片、文字、软件都只从二进行数字转化而来的。

### 位运算符

![](https://blog.fivk.cn/usr/uploads/2021/09/2198980815.png)

### 常用位操作

1. 判断奇偶
   * (x & 1) == 1 ---等价---> (x % 2 == 1)
   * (x & 1) == 0 ---等价---> (x % 2 == 0)
2. x / 2 ---等价---> x >> 1
3. x &= (x - 1) ------> 把x最低位的二进制1给去掉
4. x & -x -----> 得到最低位的1
5. x & ~x -----> 0

### 指定位置的位运算

1. 将X最右边的n位清零：x & (~0 << n)
2. 获取x的第n位值：(x >> n) & 1
3. 获取x的第n位的幂值：x & (1 << n)
4. 仅将第n位置为1：x | (1 << n)
5. 仅将第n位置为0：x & (~(1 << n))
6. 将x最高位至第n位（含）清零：x & ((1 << n) - 1)
7. 将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))

### 异或结合律

> x ^ 0 = x, x ^ x = 0
> x ^ (~0) = ~x, x ^ (~x) = ~0
> a ^ b = c, a ^ c = b, b ^ c = a
>
> (有没有点乘法结合律的意思)
> 字母表示：(a ^ b) ^ c = a ^ (b ^ c)
> 图形表示：(☆ ^ ◇) ^ △ = ☆ ^ (◇ ^ △)

### 例题：二进制中1的个数

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

#### 输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

#### 输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

#### 数据范围

1≤n≤100000,
0≤数列中元素的值≤109

#### 输入样例：

```
5
1 2 3 4 5
```

#### 输出样例：

```
1 1 2 1 2
```

```cpp
#include<iostream>
using namespace std;
int lowbit(int x){
    return x&(-x);
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        int res=0;
        while(x) x-=lowbit(x)
		res++;
        cout<<res<<' ';
    }
    return 0;
}
```

最后修改：2022 年 01 月 04 日