我不知道的按位运算

💻计算机为什么会加减乘除？笔者是一直都没了解过，认为加减乘除就是理所当然的事情，但计算机中的万物皆为0、1，笔者的认为是不可能那么简单的。

其实说直接点，就是计算机的原理是什么？

1. 二进制

二进制就是计算机使用的“语言”。简单举例来说就是：人类使用十进制来计数，它的运算规则是“逢十进一”。二进制就是“逢二进一”的运算规则。

为什么计算机使用二进制呢？这个可以归结于一个人有十根手指，所以人类普遍认知是使用十进制。计算机是由一大堆电子电路组成的，使用二进制正好对应电路里的高低电平（大部分电子器件只有两种状态），这就好比计算机只有“两根手指”。

1.1 原码

原码是二进制的一种表现形式。其为一个整数绝对值的二进制，加上符号位（0为正，1为负）。

整数	绝对值	绝对值的二进制	原码
+3	3	000 0011	0000 00011
+3	3	000 0011	1000 00011

• 原码是给人看的二进制，不是计算机保存的，不直接参与计算。

1.2 反码

针对负数做处理，在原码基础上，除了符号位，其它位取反。

整数	绝对值的二进制	原码	反码
+3	000 0011	0000 00011	0000 00011
+3	000 0011	1000 00011	1111 11100

• 反码是在计算机存储的二进制，但不是真正的二进制值，它不直接参与计算。

1.3 补码

补码是真正的二进制值，主要针对负数做处理，在反码的基础上加1。

整数	原码	反码	补码
+3	0000 00011	0000 00011	0000 00011
+3	1000 00011	1111 11100	1111 11101

1.4 理解补码

假如一个时钟现在显示的是10点钟，如何将它调到6点钟？

解：有两种方法，一是向后拨8个小时，二是向前拨4个小时

在这个例子中，8 和 4 互为补数，也就是说4的补码是8,8的补码是4，而这个时钟的模就是12

注意：可能有人会想，在往后调8个小时虽然也调到了6点，但是他实际上比原来日期多了12小时。是的，的确如此，但是你的时钟有地方存储了这多余的12个小时吗？答案是没有，所以在你调完后，你没有记录这12个小时，换句话说，你把这溢出的12个小时自动舍弃了。当第二个人来查看闹钟时间的时候，他看到的时间就是准的。

二进制补码表示负数是最方便的方式，它的便利体现在，所有的加法运算（加正数、加负数）可以使用同一种电路完成。

我们以-8作为例子。

假定有两种表示方法。一种是直觉表示法，即10001000；另一种是2的补码表示法，即11111000。请问哪一种表示法在加法运算中更方便？

随便写一个计算式，16 + (-8) = ?其中，16的二进制表示是 00010000，-8的二进制表示是 10001000

• 直觉表示法：

　０００１００００
＋１０００１０００
－－－－－－－－－
　１００１１０００

可以看到，如果按照正常的加法规则，就会得到10011000的结果，转成十进制就是-24。显然，这是错误的答案。也就是说，在这种情况下，正常的加法规则不适用于正数与负数的加法，因此必须制定两套运算规则，一套用于正数加正数，还有一套用于正数加负数。从电路上说，就是必须为加法运算做两种电路。

• 补码表示法：

　０００１００００
＋１１１１１０００
－－－－－－－－－
１００００１０００

可以看到，按照正常的加法规则，得到的结果是100001000。注意，这是一个9位的二进制数。我们已经假定这是一台8位机，因此最高的第9位是一个溢出位，会被自动舍去。所以，结果就变成了00001000，转成十进制正好是8，也就是16 + (-8) 的正确答案。这说明了，2的补码表示法可以将加法运算规则，扩展到整个整数集，从而用一套电路就可以实现全部整数的加法。

2. 按位运算

以Python为例，常用位运算符包括以下6中：

• 按位与 &
• 按位或 |
• 按位异或 ^
• 按位翻转 ~
• 左移运算 <<
• 右移运算 >>

2.1 按位与（&）

即按照对应位置的二进制进行 and运算，其中运算规则为 1 & 1 = 1，1 & 0 = 0，0 & 1 = 0，0 & 0 = 0。

下面的 5 & 3示意如下:

十进制     二进制
5 --> 0000 0101
  &        &&&&
3 --> 0000 0011
  =        ||||
1 <-- 0000 0001

• 位运算判断奇偶性

n&1 == 1 # 奇数返回1，偶数返回0

2.2 按位或（|）

即按照对应位置的二进制进行 or运算，其中的运算规则为 1 | 1 = 1，1 | 0 = 1，0 | 1 = 1，0 | 0 = 0

下面的 5 | 3示意如下:

十进制     二进制
5 --> 0000 0101
  |        ||||
3 --> 0000 0011
  =        ||||
7 <-- 0000 0111

• 向上取奇数

map(lambda x:x|1, range(6)) # 结果为[1, 1, 3, 3, 5, 5]

2.3 按位异或（^）

即按照对应位置的二进制进行 xor运算，其中的运算规则为 1 ^ 1 = 0，1 ^ 0 = 1，0 ^ 1 = 1，0 ^ 0 = 0

下面的 5 ^ 3示意如下:

十进制     二进制
5 --> 0000 0101
  ^        ^^^^
3 --> 0000 0011
  =        ||||
6 <-- 0000 0110

• 只出现一次的数字

reduce(lambda x,y: x^y, [1,1,3,2,4,3,4]) # 累积进行异或运算，找出只出现一次的数字为2，出现两次的数字就抵消掉了

2.4 按位翻转（~）

即1变成0，0变成1。

十进制     二进制
5 --> 0000 0101
  ~   ~~~~ ~~~~
-6<-- 1111 1010

翻转相当于跟 -1做异或运算，即~n = n ^ (-1)

十进制     二进制
5 --> 0000 0101
  ^        ^^^^
-1--> 1111 1111
  =        ||||
6 <-- 1111 1010

2.5 左移运算（<<）

左移运算是将二进制数值整体向左边移动n个位置，空出来的位置补0。

下面的 5 << 2示意如下:

十进制     二进制
5 --> 0000 0101
  <<    << 2
20<-- 0001 0100

• 用于乘法计算

  5 * 7
= (101 * 111)_2
= (101 * (100 + 10 + 1))_2
= (101 * 100 + 101 * 10 + 101 * 1)_2
= 5 << 2 + 5 << 1 + 5 << 0
= (10100 + 01010 + 00101)_2
= 20 + 10 + 5
= 35

2.6 右移运算（>>）

左移运算是将二进制数值整体向右边移动n个位置，空出来的位置补上符号位的数值。即正数补0，负数补1。

下面的 5 >> 2、-5 >> 2示意如下:

十进制     二进制
5 --> 0000 0101
  >>    >> 2
1 <-- 0000 0001

十进制     二进制
-5--> 1111 1011
  >>    >> 2
-1<-- 1111 1110

• 用于除法

  5 / 3
= 5 >> 2
= (101 / 100)_2
= (001)_2
= 1

2.7 位运算实现加减乘除

def add(num1, num2):
    while num2 != 0:
        temp = num1 ^ num2
        num2 = (num1 & num2) << 1
        num1 = temp
    return min(max(-2147483648, num1), 2147483647)

def sub(num1, num2):
    return add(num1, add(~num2, 1))

def mul(num1, num2):
    sign = (num1 > 0) is (num2 > 0)

    if num1 < 0:
        num1 = add(~num1, 1)
    if num2 < 0:
        num2 = add(~num2, 1)

    result = 0
    while num2:
        if num2 & 1:
            result = add(result, num1)
        num1 = num1 << 1
        num2 = num2 >> 1

    if not sign:
        result = - result
    return result

def div(num1, num2):
    sign = (num1 > 0) is (num2 > 0)

    if num1 < 0:
        num1 = add(~num1, 1)
    if num2 < 0:
        num2 = add(~num2, 1)

    result = 0
    while (num1 >= num2):
        tmp, i = num2, 1
        n = 4
        while(num1 >= tmp):
            num1 -= tmp
            result += i

            tmp = tmp<<n
            i = i << n
        n = n >> 2

    if not sign:
        result = -result

    return min(max(-2147483648, result), 2147483647)

在早期版本中，如Python2.7，整数的有int和long两个类型。int类型是一个固定位数的数；long则是一个理论上可以存储无限大数的数据类型。当数大到可能溢出时，为了避免溢出，Python会把int转化为long。

而Python3.x之后整数只有一个可以放任意大数的int了。可是无论哪种，都是采用了特殊的方法实现了不会溢出的大整数。

在进行负数的按位加法时，有可能发生在最高位还要向前进一位的情形，正常来说，这种进位因为超出了一个int可以表示的最大位数，应该舍去才能得到正确的结果。但在Python中因为上述原因会产生一个不会溢出的大整数，所以在进行负数的按位加法时，结果会不断变大。

这个问题在 Java、C、C++ 中不会存在，这也是Python效率低的一个原因。