位运算的应用

算法
位运算的操作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;
//或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/articles/BitwiseOperationUsage/

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

评论