位运算的应用

位运算的操作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;
// 或 a ^= b ^= 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;
// 或 return ~(1 << 31);
// 或 return (1 << -1) - 1;
}

获取int最小值(Min_Int

1
2
3
4
5
int Min_Int()
{
return 1 << 31;
// 或 return 1 << -1;
}

取绝对值

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

1
-~n

计算 n - 1

1
~-n

计算 -n

1
~n + 1

完。

本文作者:Xecades

本文链接:https://blog.xecades.xyz/drafts/BitwiseOperationUsage.html

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论