Python中的数字系统

一、Python位运算操作符

二、计算机中的原码、反码、补码

1. 原码

   原码是二进制数字的一种简单表示。例如8位有符号整数中，最高位为符号位，因此可以表示-127 ~ -0, +0 ~ 127共256个数字。

2. 反码

   反码是根据原码得到的。

   特别的，正数的反码和原码一样；

   负数的反码是对原码按位取反，符号位保持不变

3. 补码

   补码是根据原码得到的。

   特别的，正数的补码和原码一样；

   负数的补码是反码+1，+1时产生进位则进位，跟正常的计算一样，但是符号位保持不变

三者的区别和联系

原码是为了方便人计算，补码是为了方便计算机计算，反码则是提供了原码到补码之间的转换

计算机里面只有加法没有减法，引入补码可以将减法转换为加法

也就是说，计算机存储的都是补码

因此，8位二进制在计算机中表示的范围是-128 ~ 127，原码中的-0其实是-128

三、Python位运算的一些trick

数字在计算机中是以补码形式保存的，因此编程语言的位运算也是作用在补码上的

首先我们要知道的一个点就是：bool(x) = False, if x == 0，bool(x) = True, if x != 0，也就是说只有0 和 0.0的布尔值是False，其他数字(整数/浮点数)都是True

1. 判断奇偶性

   # 在判断奇偶性的时候，可以使用 模2 判断余数是否为0的方法
   def isOdd(x):
       return True if x % 2 != 0 else False
       
   # 也可以将待判断的整数和1做位于运算，判断结果是否为1
   def isOdd(x):
       return True if x & 1 == 1 else False
   

2. 位移代替乘2/除2

   a *= 2
   a <<= 1
   b /= 2
   b >>= 1
   

3. 交换数值(实际上我没发现这个有多常用)

   # 法1
   a, b = b, a
       
   # 法2
   temp = a
   a = b
   b = temp
       
   # 法3
   a ^= b
   b ^= a
   a ^= b
       
   """
   首先a = a ^ b这个容易理解，
   然后b = b ^ a = b ^ a ^ b = a， 这里用到了x ^ x = 0，而 0 ^ y = y的原理，实现了b = a
   最后a = a ^ b = a ^ b ^ a = b， 道理跟上面一样
   """
   

4. 寻找只出现一次的数

   给定一个数组，共有2n + 1个数字，其中的n个数出现了2次，另一个数出现了1次，找出这个只出现一次的数

   def findUnique(arr):
       """
       由于x ^ x = 0，因此，出现偶数次的数字在异或过程中会被消除，最后异或剩下的结果就是只出现1次的数
       """
       res = 0
       for num in arr:
           res ^= num
       return res
   

   给定一个数组，共有2n+2个数字，其中n个数出现了2次，另外2个数出现了1次，找出这2个只出现一次的数

   def findUnique2(arr):
       flag = 0  # 记录只出现1次的这两个数字的异或值
       for num in arr:
           flag ^= num
           
       # flag中为1的位说明这两个数字在该位的数字不一样，
       # 例如flag的第x位为1，那么a和b的第x位就一定不一样，一个为1一个为0
       # 借助这个特点可以将原来的数组划分为2个子数组，分别包含a和b，以及对应的偶数个出现2次的数
       idx = 0
       while flag & 1 != 1:
           flag >>= 1
           idx += 1
               
       # 根据前面找到的idx，判断所有数字中第idx位是0还是1，划分为两个子数组，
       # 然后子数组内运行findUnique()的算法即可
       a = b = 0
       for num in arr:
           if num >> idx & 1:
               a ^= num
           else:
               b ^= num
       return a, b
   

5. 计算一个数值的二进制表示中1的个数

   def numOfOne_shift_fail(x):
       # 最简单的方法就是通过位移操作，判断最低位是否为1
       # 但是这种方法是可以引发死循环的，如果输入是负数，那么符号位为1，如果不对位数添加界限的话，
       # 循环将无法终止(这是因为Python不存在移位溢出)
       count = 0
       while x:
           count += x & 1
           x >>= 1
       return count
       
       
   def numOfOne_shift_success(x):
       # 最简单的方法就是通过位移操作，判断最低位是否为1
       # 但是这种方法是可以引发死循环的，如果输入是负数，那么符号位为1，如果不对位数添加界限的话，
       # 循环将无法终止(这是因为Python不存在移位溢出)
       count = 0
       x &= 0xffffffff  # 当然这里的界限可能不一定是32位，但只要对x添加了界限就不会引发死循环
       while x:
           count += x & 1
           x >>= 1
       return count
       
       
   def numOfOne_advanced(x):
       """
       将1个数字减1，那么其最低位的1会变为0，更低位的0会变为1，
       也就是说，将1个数字减1，可以将其最右边的1变为0
           
       但是这样做的话变为0的那个1的右边原本的0就变为了1，这并不是我们想要的，
       因此我们可以通过对x和x-1做按位与运算，保证原本为0的位保持不变，而最右边的1变为0.
           
       借助上面的算法，我们可以跳过二进制中很多个中间的0，每次将最右边的一个1置为0
       """
       count = 0
       x &= 0xffffffff  # 首先还是得添加一个位数限制，不然在Python中会引发死循环
       while x:
           count += 1
           x &= x - 1
       return count
   

6. 二进制和十进制转换

   def bin2Int(x, bits=32):
       # 如果是32位，或者64位，可以直接通过十六进制表示对x添加界限
       # 更通用的方法是通过位移后减1来获取对应位数个1，然后做按位与运算
       # bin()返回的是'0bxxxx'的形式，对我们来说有效的是xxxx这部分，所以需要先切片
       # str.zfill(bits)的作用是将str右对齐，然后左边补0，直到长度为bits，
       # 可以帮助我们将正数的位数补齐
       return bin(((1 << bits) - 1) & x)[2:].zfill(bits)  # 更通用的做法，适用任何位数
       return bin(x & 0xffffffff)[2:].zfill(bits)  # 已知位数为32的情况下可以这样
       
   def int2Bin(s, bits):
       return int(s[1:], 2) - int(s[0]) * 0x80000000  # 已知位数为32的情况下可以这样
       return int(s[1:], 2) - int(s[0]) * (1 << bits)  # 更通用的做法，适用任何位数