位运算的操作https://blog.xecades.xyz/articles/BitwiseOperation本文介绍位运算的简单应用及性质
常用变换
列举如下：
| 操作 | 举例 | 运算 |
|---|
| 去掉最后一位 | $101101\rightarrow 10110$ | $x \gg 1$ |
| 在最后加一个 0 | $101101\rightarrow 1011010$ | $x \ll 1$ |
| 在最后加一个 1 | $101101\rightarrow 1011011$ | $x \ll 1+1$ |
| 把最后一位变成 1 | $101100\rightarrow 101101$ | $x \mid 1$ |
| 把最后一位变成 0 | $101101\rightarrow 101100$ | $x \mid 1-1$ |
| 最后一位取反 | $101101\rightarrow 101100$ | $x \wedge 1$ |
| 把右数第 k 位变成 1 | $101001\rightarrow 101101,k=3$ | $x \mid (1$<<$(k-1))$ |
| 把右数第 k 位变成 0 | $101101\rightarrow 101001,k=3$ | $x$ & ~ $(1 \ll (k-1))$ |
| 右数第 k 位取反 | $101001\rightarrow 101101,k=3$ | $x \wedge (1 \ll (k-1))$ |
| 取末 k 位 | $1101101\rightarrow 1101,k=4$ | $x\ \&\ 15^※$ |
| 取右数第 k 位 | $1101101\rightarrow 1,k=4$ | $x \gg (k-1)\ \&\ 1$ |
| 把末 k 位变成 1 | $101001\rightarrow 101111,k=4$ | $x \mid (1 \ll k-1)$ |
| 末 k 位取反 | $101001\rightarrow 100110,k=4$ | $x \wedge (1 \ll k-1)$ |
| 把右边连续的 1 变成 0 | $100101111\rightarrow 100100000$ | $x\ \&\ (x+1)$ |
| 把右起第一个 0 变成 1 | $100101111\rightarrow 100111111$ | $x \mid (x+1)$ |
| 把右边连续的 0 变成 1 | $11011000\rightarrow 11011111$ | $x \mid (x-1)$ |
| 取右边连续的 1 | $100101111\rightarrow 1111$ | ($x \wedge (x+1)) \gg 1$ |
| 去掉右起第一个 1 的左边（lowbit） | $100101000\rightarrow 1000$ | $x\ \&\ \sim(x \wedge (x-1))$ 或 $x\ \&\ (-x)$ |
※其中取末 4 位用 $x\ \&\ 15$ 是因为 $15$ 二进制表示为$1111$。因此，取末尾 8 位用二进制为 $11111111$ 的数，转为十进制为 $255$，建议用 $(1 \ll 8)-1$ 来表示。
常用应用
交换数字
1
2
3
4
| a = a ^ b;
b = a ^ b;
a = a ^ b;
|
计算 32 位整数的二进制中 1 的个数的奇偶性
当输入数据的二进制表示里有偶数个数字 1 时程序输出 0，有奇数个时输出 1。（注意：对于 32 位整数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <iostream>
using namespace std;
int main()
{
int x;
cin >> x;
x ^= (x >> 1);
x ^= (x >> 2);
x ^= (x >> 4);
x ^= (x >> 8);
x ^= (x >> 16);
cout << (x & 1);
return 0;
}
|
获得int最大值（Max_Int）
1
2
3
4
5
6
| int Max_Int()
{
return (1 << 31) - 1;
}
|
获取int最小值（Min_Int）
1
2
3
4
5
| int Min_Int()
{
return 1 << 31;
}
|
取绝对值
1
2
3
4
| int abs(int x)
{
return (x ^ (x >> 31)) - (x >> 31);
}
|
取较大值
1
2
3
4
| int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y));
}
|
取较小值
1
2
3
4
| int min(int x, int y)
{
return y ^ ((x ^ y & -(x < y)));
}
|
从低到高，取 n 的第 m 位
1
2
3
4
| int getBit(int n, int m)
{
return (n >> (m - 1)) & 1;
}
|
从低到高，将 n 的第 m 位置 1
1
2
3
4
| int setBitToOne(int n, int m)
{
return n | (1 << (m - 1));
}
|
从低到高，将 n 的第 m 位置 0
1
2
3
4
| int setBitToZero(int n, int m)
{
return n & ~(1 << (m - 1));
}
|
计算 n + 1
计算 n - 1
计算 -n
完。
评论