本文共 3759 字，大约阅读时间需要 12 分钟。

以前也多多少少接触过一点位运算，课本上，LeetCode上，但是就是没有动手实操过，因为没遇到那个场景。。

我一度不知道位运算干嘛用，昨天在《编程珠玑》上看到一个位运算解决大数排序的问题，突然我就对这个技术有了兴趣。

位运算 VS 普通运算

其实我个人觉得没有什么可比性，这两种运算，要说它们属于不同领域也是可以的，位运算是位运算，普通运算是普通运算。

不过吧，位运算快一点，程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。 但是吧，数据量小的时候也看不出什么区别来，不过数据量大的话，嘿嘿，我也没试过。

多学点总是好的，技多不压身嘛。

位运算运算符

按位与 &

相同位的两个数字都为1，则为1；若有一个不为1，则为0。

示例：6&11

0 1 1 0	1 0 1 1&-----------	0 0 1 0 = 2

and运算通常用于二进制的取位操作。

小技巧：一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。

更多技巧慢慢看，在后面。

按位或 |

相同位只要一个为1即为1。

示例：6 | 11

0 1 1 0	1 0 1 1| ----------- 	1 1 1 1 = 15

or运算通常用于二进制特定位上的无条件赋值。

小技巧：一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。

更多技巧慢慢看，在后面。

按位异或 ^

两个位相同为0，相异为1

示例：6 ^ 11

0 1 1 0	1 0 1 1^ -----------	1 1 0 1 = 13

^运算通常用于翻转指定位。

小技巧：将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

更多技巧慢慢看，在后面。

按位取反

not运算的定义是把内存中的0和1全部取反。

示例：~ 6

使用按位取反运算符，要知道几点：

1、内存中，一个int，4个字节，1字节8位。 2、有符号整数的按位取反情况略有偏差。

00000000 00000000 00000000 00000110~ --------------------------	11111111 11111111 11111111 11111001

小技巧：可以用~使每个数的最低位为0，方法：a & ~1

别问我上面为什么不用这么长，我也不知道。我猜，是我不想写这么长哈哈哈。

左移位运算符 <<

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

示例：6 << 2

0 1 1 0<<2 ------------	0 1 1 0 0 0 = 24

小技巧：若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

右移位运算符 >>

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

示例： 6 >> 2

0 1 1 0>>2 -------------		0 0 0 1 = 1

小技巧：操作数每右移一位，相当于该数除以2。

负数的二进制表示

既然都讲到这里了，那自然要了解一下负数的表示形式了。

==用字节的最高位表bai示:“1"表示"正”,“0"表示"负” ==

1、把补码“取反”（把二进制数的各位“1”换“0”，“0”换“1”。比如“101010”取反后为“010101”）

2、把取反后的二进制数“加1”

示例：-17 转码

再转回来

-17转码：

17：	00000000 00000000 00000000 00010001反码：	11111111 11111111 11111111 11101110转码：	11111111 11111111 11111111 11101111

转回来自己动手。

所以C++中int的取值范围为：-2^31~2^31-1。

---

投机

异或的几条性质

1、交换律2、结合律（即(a^b)^c == a^(b^c)）3、对于任何数x，都有x^x=0，x^0=x4、自反性:  a^b^b=a^0=a;

位运算实现乘除

上面有

位运算实现swap

//普通操作void swap(int &a, int &b) {
     a = a + b;  b = a - b;  a = a - b;}//位与操作void swap(int &a, int &b) {
     a ^= b;  b ^= a;  a ^= b;}

呐，我来试试分析：

a ^= b  -->  a = a^bb ^= a  -->  b = b^a^b = aa ^= b  -->  a = a^b^a = b

挺秀的啊，不过有的人说这样会出问题，比方说 a = b 的时候。

那我再来分析一下：

a ^= b  -->  a = a^b = 0b ^= a  -->  b = b^a^b = a = 0a ^= b  -->  a = a^b^a = b = 0

哦，确实，他是对的。

都说是投机了，大家看着用吧，下面的其他投机技巧也说不定会是地雷哦。

位操作判断奇偶数

只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。

if(0 == (a & 1)) {
    //偶数}

位操作交换符号交换符号

将正数变成负数，负数变成正数

int reversal(int a) {
   	return ~a + 1;}

整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数5. 位操作求绝对值整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

int abs(int a) {
   	int i = a >> 31;	return i == 0 ? a : (~a + 1);}

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

int abs2(int a) {
       int i = a >> 31;    return ((a^i) - i);}

位操作统计二进制中 1 的个数

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：

第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000

我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：count = 0

while(a){
         a = a & (a - 1);      count++;  }

用 O(1) 时间检测整数 n 是否是 2 的幂次

N如果是2的幂次，则N满足两个条件。

1.N >02.N的二进制表示中只有一个1

因为N的二进制表示中只有一个1,所以使用N & (N - 1)将N唯一的一个1消去，应该返回0。

数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数

因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。（异或自反性）

但当涉猎

1a&a=aa^a=02a&0=0a|0=aa^0=a3a|(a&b)=aa&(a|b)=a4、交换值a^=b;b^=a;a^=b;5、判断奇偶(取出最后一位)a &1等价于a%2(结果等于,位运算效率高)6、比较两值是否相等a^b==07、i+1位置1a |=1<

以上，为最常见的用法，不带循环，全部O(1)。

这个要常回来看看啊。

一个大数去重的栗子

---

初次见面，先打基础，待我这两天去LeetCode上包装一下。

待我包装完，试试看用位运算进行排序能不能写出来。

位图

不急。。

过两天就写，估计也会是粉丝可见咯

转载地址：https://lion-wu.blog.csdn.net/article/details/107244177 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！