位运算的操作https://blog.xecades.xyz/articles/BitwiseOperation本文介绍位运算的简单应用及性质
优先级
同其他运算符号一样,位运算也是有优先级的:
优先级 | 运算符 |
---|
1 | ~ |
2 | <<、>> |
3 | & |
4 | ^ |
5 | \ | |
6 | &=、^=、\ | =、<<=、>>= |
常用变换
列举如下:
操作 | 举例 | 运算 |
---|
去掉最后一位 | $101101\rightarrow 10110$ | $x$ >> $1$ |
在最后加一个0 | $101101\rightarrow 1011010$ | $x$ << $1$ |
在最后加一个1 | $101101\rightarrow 1011011$ | $x$ << $1+1$ |
把最后一位变成1 | $101100\rightarrow 101101$ | $x \mid 1$ |
把最后一位变成0 | $101101\rightarrow 101100$ | $x \mid 1-1$ |
最后一位取反 | $101101\rightarrow 101100$ | $x$ ^ $1$ |
把右数第k位变成1 | $101001\rightarrow 101101,k=3$ | $x \mid (1$<<$(k-1))$ |
把右数第k位变成0 | $101101\rightarrow 101001,k=3$ | $x$ & ~ $(1$ << $(k-1))$ |
右数第k位取反 | $101001\rightarrow 101101,k=3$ | $x$ ^ $(1$ << $(k-1))$ |
取末k位 | $1101101\rightarrow 1101,k=4$ | $x$ & $15^※$ |
取右数第k位 | $1101101\rightarrow 1,k=4$ | $x$ >> $(k-1)$ & $1$ |
把末k位变成1 | $101001\rightarrow 101111,k=4$ | $x \mid (1$ << $k-1)$ |
末k位取反 | $101001\rightarrow 100110,k=4$ | $x$ ^ $(1$ << $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$ ^ $(x+1))$ >> $1$ |
去掉右起第一个1的左边($lowbit$) | $100101000\rightarrow 1000$ | $x$ & ~ $(x$ ^ $(x-1))$或$x$ & $(-x)$ |
※其中取末$4$位用$x$ & $15$是因为$15$二进制表示为$1111$.因此,取末尾$8$位用二进制为$11111111$的数,转为十进制为$255$,建议用$(1$ << $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
评论