C++ 位运算

本节主要学习C++中的位运算。

位运算符列表如下:

操作符 功能 用法
~ 位求反 ~expr
<< 左移 expr1 << expr2
>> 右移 expr1 >> expr2
& 位与 expr1 & expr2
^ 位异或 expr1 ^ expr2
| 位或 expr1 | expr2

C++ 位运算

简介

位是数据存储的最小单位。在 计算机中的二进制数系统中,位,简记为b,也称为比特,每个0或1就是一个位(bit)。

经典用法

1. 求二进制中1的个数

1
n&n-1

2. 把 data上调至8 的倍数,同理,也可以改成16,32…的倍数。

1
(data + 8 - 1) & (8 - 1)

3. 取int的最值

1
2
3
4
(1<<31)-1;//int的最大值
(1<<31);//int的最小值
((long long)1<<63)-1;//long long的最大值
((long long)1<<63);//long long的最小值

4. 判断两个数符号是否相同

这个也很简单,二进制第一位表示符号,所以符号相同就为0(正数),符号不同就为1(负数)。

1
n^m>=0

5. 判断正负

1
n>>31

特殊用法

1. 交换两个数

1
2
3
a^=b;
b^=a;
a^=b;

2. 对这个数二进制的第m位进行处理(从低位到高位)

​ 首先为了得到第m位的值,肯定是要将这个数右移(m-1)位,然后为了将其他多余的数清零,我们再进行&1的操作,就可以将第m位提取出来了。如果是想改变第m位的值,那么就不能对这个数进行移动,因为这样会改变这个数的值。所以我们要对1向左移(m-1)位,然后再进行操作更改。如果要将第m位变成1,那么就n|(1<<(m-1)),这样就可以保证其余位不变改变第m位。如果要将第m位变为0,那么就n&~(1<<(m-1)),因为取反后就能得到除了第m位为0其余位都为1的一个数,这样再进行按位与计算就可以只改变第m位的值了。

1
2
3
(n>>(m-1))&1;//取n的二进制的第m位
n|(1<<(m-1));//将n的二进制的第m位改为1
n&~(1<<(m-1));//将n的二进制的第m位改为0

3. 统计1的个数

1.普通算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bitcount1(int n)
{
int cou=0;
int flag=1;
while(flag)
{
if(n&flag)
{
cou++;
}
flag=flag<<1;
}
return cou;
}
2. 快速算法
1
2
3
4
5
6
7
8
9
10
int bitcount2(int n)
{
int cou=0;
while(n)
{
n=n&(n-1);
cou++;
}
return cou;
}
  • © 2019-2022 guoben
  • PV: UV:

微信