位运算

2020-11-18 本文已影响0人 Su_yj

本人非科班出身，但由于想从事这一行业，希望进阶到更高的境界，可是面试了几次发现没有一些基础确实是有些难以支撑自己，所以在此记录一下自己学习的一些知识和想法，文章中如果有错误的希望各位能指正。

0. 数据在计算机中的表示方式

当代设计的计算机存储数据只能用0和1来表示，所以计算机中都是用二进制来表示各类的数据，也由此说明了一件事，计算机中存储数据的最小单位是比特（bit）。好比如：

0 -> 0000 0000  # 0用二进制表示
1 -> 0000 0001  # 1用二进制表示
2 -> 0000 0010  # 2用二进制表示（由于是二进制，所以缝2进位）

上面为什么0需要用到8个0来写呢？那是因为，Bit这个单位确实是太小了，存储起来不太方便，所以我们样规定，8个比特等于1个字节（8 Bit = 1 Byte），这里的Byte就是字节的意思，可以简写成B，因此存储容量的基本单位是字节。而每1024个字节又可以用KB来表示（具体原因请查看百度百科），所以他们的关系如下：

              8 bit（比特） = 1 Byte（字节，简写 B）
          1024 Byte（字节） = 1 KB（千字节）
         1024 KB （千字节） = 1 MB （兆字节，百万字节）
1024 MB （兆字节，百万字节） = 1 GB（吉字节，十亿字节）
                          ...

这里一个快速换算的网站：https://www.bejson.com/convert/filesize/

但是，现实生活中，我们除了计算正整数外，还会有负整数，那么，在表示一个二进制的整数时这样规定，这个数的第一个数字用来表示正号或负号，所以就有下面的表示：

 1 -> 0000 0001
-1 -> 1000 0001

可能说到这里有些人会产生疑惑，计算机的数据不是连着的吗？虽然这里的-1的第一位数是1，但是1再往前的数，它又怎样区分不是它的呢？
可能说得有点绕，这里画一个图来表示

image.png
像上面的图所说的，计算机不知道到底要从哪里开始取这个-1，所以一般下，在我们定义这个数的时候，我们先会告诉计算机，我们需要使用多少比特(bit)，然后计算机会帮我们在内存里开辟这么多的空间给我们存储数据（个人理解）。但具体计算机是怎样记录这块内存空间从哪里到哪里的，个人水平有限，如果以后知道另外再写文章介绍吧。
所以，大致流程如下

刚开始时，内存可能是长这个样子的

初始化

当我们向计算机申请一块内存使用，它可能是这样子记录的（红色框表示已使用的内存）

第一次申请内存

当我们再次申请内存，它可能又是长这个样子的（红色框表示已使用的内存）

image.png

我们程序中所说的int类型，一般都是指int32，也就是需要用32个bit来存我们这个数。所以，假如我们需要创建一个int32类型的数据，这时内存空间应该是这样子的

int32

所以到这里，我们顺便回答了一个问题，也就是int8，int16，int32，int64的取值范围

因为每个数有一位用于表示符号，所以范围取值是该数使用bit位数的数量减1，另外0由于没有正负之分，所以正整数的总数需要减一

int8  取值范围： -2^7 ~ 2^7-1
int16 取值范围：-2^15 ~ 2^15-1
int32 取值范围：-2^31 ~ 2^31-1
int64 取值范围：-2^63 ~ 2^63-1

1. 位运算概要

从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
下面举个例子说明一下：

35 + 47

计算两个数的和，因为在计算机中都是以二进制来进行运算，所以上面我们所给的int变量会在机器内部先转换为二进制在进行相加：

35:  0 0 1 0 0 0 1 1
47:  0 0 1 0 1 1 1 1
————————————————————
82:  0 1 0 1 0 0 1 0

所以，相比在代码中直接使用(+、-、*、/)运算符，合理的运用位运算更能显著提高代码在机器上的执行效率。

2. 位运算符

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
\|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

3. 按位与运算符（&）

定义：两个位都为1时，结果才为1，否则结果为0。
运算规则：

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

例如：

3 & 5 = 1

3:  0 0 0 0  0 0 1 1
5:  0 0 0 0  0 1 0 1
--------------------
1:  0 0 0 0  0 0 0 1

注意：负数按补码形式参加按位与运算。
与运算的用途：
1）清零
如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
如：1&0=0、100&0=0、127&0=0
2）取一个数的指定位（可以理解为求交集）
比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
3）判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。
PS：% 是求余符号

4. 按位或运算符（|）

定义：两个位都为0时，结果才为0，否则结果为1。
运算规则：

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

例如：

3 | 5 = 1

3:  0 0 0 0  0 0 1 1
5:  0 0 0 0  0 1 0 1
--------------------
7:  0 0 0 0  0 1 1 1

注意：负数按补码形式参加按位或运算。
或运算的用途：
1）常用来对一个数据的某些位设置为1（可以理解为求并集）
比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。

5. 异或运算符（^）

定义：两个对象的对应位置上的数相同为0，不同为1.
运算规则：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

例如：

3 ^ 5 = 6

3:  0 0 0 0  0 0 1 1
5:  0 0 0 0  0 1 0 1
--------------------
6:  0 0 0 0  0 1 1 0

异或的几条性质：
1、交换律
2、结合律 (a ^ b) ^ c == a ^ (b ^ c)
3、对于任何数x，都有 x ^ x = 0，x ^ 0 = x
4、自反性: a ^ b ^ b = a ^ 0 = a
异或运算的用途：
1）翻转指定位（有点类似求差集）
比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。
2）与0相异或值不变
例如：1010 1110 ^ 0000 0000 = 1010 1110
3）交换两个数

void Swap(int &a, int &b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

6. 取反运算符（~）

定义：对数据的每个二进制位取反,即把1变为0,把0变为1。
运算规则：

~1 = -2
~0 = -1

例如：

 5:  0 0 0 0  0 1 0 1
---------------------
-6:  1 1 1 1  1 0 1 0

到这里可能有些人会有疑惑，为什么1111 1010表示的是-6呢？
其实，取反后，还需要进行取原码的操作就可以得到-6了，上面是反码的表示方式，反码取原码的具体步骤如下：

首位不变，取反码，末尾加1。

1. 首位不变，取反码

1 1 1 1  1 0 1 0
----------------
1 0 0 0  0 1 0 1

2. 末尾加1

1 0 0 0  0 1 0 1
0 0 0 0  0 0 0 1
----------------
1 0 0 0  0 1 1 0

所以经过上面计算后，最终的结果就是-6，具体可以查看位运算按位取反是怎么算出来的这篇文章中的介绍

异或运算的用途：
1）使一个数的最低位为零
使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

7. 左移运算符（<<）

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

5 << 1 = 10
5 << 2 = 20
5 << 3 = 40

例如：

5 << 2 = 20

 5: 0 0 0 0  0 1 0 1
--------------------  向左移两位后
20: 0 0 0 1  0 1 0 0

左移运算符的用途：
1）快速计算某个数乘以2的几次方
其实从上面的结论可以看出，5的机器码左移1位，相当于5✖2的操作（2^1），左移2位，相当于5×4的操作（2^2），所以可以通过这样的方法快速算出某个数乘以2的几次方，这样的计算是相当的快的。

8. 右移运算符（>>）

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

运算规则：

  8 >> 2 = 2
  6 >> 2 = 1
-10 >> 2 = -3

例如：

8 >> 2 = 2

8: 0 0 0 0  1 0 0 0
--------------------  向又移两位后
2: 0 0 0 0  0 0 1 0


6 >> 2 = 1

6: 0 0 0 0  0 1 1 0
--------------------  向又移两位后
1: 0 0 0 0  0 0 0 1

然而，负数的右移位运算比较特别，需要先对原码的补码，在右移，然后保留符号位，按位取反，然后加1，即为所求数的原码，具体步骤如下：

-10 >> 2 = -3

1. 求原码的补码（保证符号位不变，其余位置取反加1）
-10的原码：1 0 0 0  1 0 1 0
-10的补码：1 1 1 1  0 1 1 0

2. 右移2位
1 1 1 1  0 1 1 0
----------------
1 1 1 1  1 1 0 1

3. 保留符号位，按位取反
1 1 1 1  1 1 0 1
----------------
1 0 0 0  0 0 1 0

4. 加1求原码
1 0 0 0  0 0 1 0
----------------
1 0 0 0  0 0 1 1

右移运算符的用途：
1）在没有溢出的情况下，可以看成是求某个数除以2的n次方

9. 注意：

1）上面的计算都是基于整数而言，小数不在此考察范围内
2）对于左移运算和右移运算，在没有位溢出的情况下，都可以看成是某个数成或除以2的n次方

参考：
https://www.cnblogs.com/yrjns/p/11246163.html
https://blog.51cto.com/sunnybay/1625309
https://blog.csdn.net/king_msky/article/details/17221973

位运算