Python高性能编程（一）计算机中的信息表示
所谓编程，就是通过计算机语言，对存放在一定位置上的比特信息进行一系列移动和处理，最终得到某些结果的过程。而高性能的编程就是通过降低开销和改变操作方式来让这些操作的代价最小化。
要了解哪些开销是可以省去的，哪些操作是可以优化的，就不得不从更底层的角度看待计算机。
计算机中的信息表示
计算机中，信息都是以0与1两种状态组成的序列。要了解计算机中信息的含义，我们除了需要了解进制以外，还需要人为制定一些规则，帮助我们规范信息的含义，这些规则包括了数据宽度和原码补码反码的规则，在这些规则之上计算机才能够进行基本运算。
进制
可能因为人生来有十个手指的关系，人在计数的时候天然选择了十进制。而电子计算机的核心是由晶体管组成的，而晶体管只有通电和不通电两种状态。因此计算机天然就选择了二进制。所谓进制，无非就是指定如何用一套符号进行计数和运算的规则。我们用0和1两个符号计数，那么就是二进制；用0-9十个符号计数，就是十进制；再添上abcdef，就是十六进制了；
由于我们表示数字的符号系统（进制）不同，自然带来了运算的不同，然而其基本思想是相同的。
譬如二进制下的加法，2+3等于多少呢？我们可以用二进制计数符号来写下0-10的结果：
十进制对照： 0 1 2 3 4 5 6 7 8 9 10
二进制数字：00 01 10 11 100 101 110 111 1000 1001 1010
在十进制下，我们经过多年教育，自然掌握了2+3的结果，那就是5。我们不妨回想下我们是如何知道这件事的：在小学的时候我们就熟记十进制加法表了。
可以说，运算的本质，就是查表。怎么查？2+3，也就是从2开始，向后查3个数，对十进制来说，也就是5了。2*3又如何呢？乘法也就是找几个几的问题。我们从1开始（人类的自然计数都是从1开始的），向后查3次2个数，得到了6。而减法和除法又可以用加法与乘法进行表示，就不再赘述。
知道了这一点，我们也就可以采用同样的方式来在二进制乃至任意进制下进行运算了：2+3在二进制中，无非也就是从2的二进制表示10开始，向后找3个数，得到了101，也就是十进制的5。
数据宽度
大多数计算机中使用8位的块作为最小的可寻址的内存单位，也就是字节（byte）。通过这样的分割，计算机就可以将内存视为一个由字节组成的很大的数组，而数组中的每个字节都有其对应的唯一标识，称为它的地址。对于32位计算机来说，有个地址，也就是能够存储4GB左右个地址（这也是32位机器内存限制4GB的原因），而64位机器则有
个地址，大约为16EB（所以我们通常说64位机器支持无线扩展内存）。
这样，通过地址，计算机就可以定位到内存中的任意位置，进行数据的读出和写入。现在的问题在于，我们的一次读出和写入，需要读/写多少位呢？这就需要数据宽度来指定。
在静态编程语言中，我们通常能看到类型指定关键词，如int, double, char等，这些关键词就指明了数据在内存中定义的宽度。通过地址定位以及数据宽度，我们就可以从存储中进行正确的数据读写了（同时，也正是因为数据宽度，计算机对数字的保存从某种意义上来说是并不精确的，对于整数会产生溢出问题，对于浮点数会产生截断问题）。
但是我们提到了，一个字节由8位组成，其值域在二进制中也就是，这种表达太过冗长，而十进制的
与二进制之间转换非常麻烦。为了简化对位状态的描述，十六进制就应运而生了。一个十六进制数可以描述4个二进制位的状态，一个字节也就可以用两个十六进制数描述，其值域为
。这也是我们通常在底层查看位状态时看到的表示方法。
负数的表示 -- 原码补码和反码
规则定义
通过了对宽度的定义，我们可以从计算机存储中取得01序列并进行适当的“翻译”，得到它表示的整数（或者字符）。但是我们直到整数不止包括自然数，还包括负数，那么负数又应该如何表示呢？答案就在于原码补码和反码这套规则（在计算机体系中我们遇到的一切规则都是为了方便计算和其他操作人为定义的，毕竟自然界中并没有野生的计算机）。
原码补码和反码规则是用来表示负数的，因而它对于正负数的处理规则不同也是自然而然的：
- 对于正数和无符号数，原码补码和反码都是相同的；
- 对于负数，原码第一位为1，表示负数，剩余位和其正数相同；补码保持符号位不变，剩余位取反；反码在补码基础上+1
5的原码补码和反码（只考虑8位）
原码：0000 0101
反码：0000 0101
补码：0000 0101
--------------------
-5的原码补码和反码
原码：1000 0101
反码：1111 1010
补码：1111 1011
规则作用
为何需要这套规则呢？这是方便计算机将减法转化为加法，比如我们需要计算8-5，那么直接用补码相加就可以了：
用补码相加计算8-5：
8的补码: 0000 1000
-5的补码: 1111 1011
补码相加: 0000 0011 ===> 符号位为0，是正数；从而解析出结果为3
--------------------
用补码相加计算2-5：
2的补码: 0000 0010
-5的补码: 1111 1011
补码相加: 1111 1101 ===> 符号位为1，是负数；解析时需要向其原码转化
反码： 1111 1100
原码： 1000 0011 ===> 得到结果为-3
这样，我们用两个数的补码直接相加，就能得到其对应结果的补码，无论加数是正是负。
规则原理
从原码到补码的原理其实也不复杂，用一个词说明，就是同余。
我们先看一下mod的数学定义：
根据这个定义，我们不但可以应付正数的mod，还可以处理负数：
求-25 mod 12
-25 mod 12 = -25 - 12 * (-3) = 11
这里我们就看到一个很有意思的性质：11 mod 12 = 11，-25 mod 12 = 11，也就是说11和-25对于12是同余的。正如我们看到的闹钟，上面有12个代表小时的刻度，我们将一根时针向前拨动11个小时，和向后拨动25个小时，最后的位置是相同的。进一步地，所有的同余数对于我们的指针造成的影响都是相同的：向前拨动11小时，向前拨动23小时，向后拨动1小时，向后拨动25小时，最后指针停的位置都是相同的 。
下图演示了作用于闹钟时针上的同余数：
1-同余数.png
知道了同余数之后，我们就可以将减法和加法在一定进制和数据宽度下进行转化了。对上面的图，我们可以看做12进制下宽度为1的运算，此时1-1和1+11的结果是相同的。
我们计算机的原码和补码也是相同的道理，取一个字节作为例子，一个字节能表示的数范围是，也就可以看做是256进制下宽度为1的数。
考察-5的补码：
1111 1011 ===> 转化为10进制就是251
251 mod 256 = 251
-5 mod 256 = 251
根据上面描述过的原理，a-5和a+251在256进制下宽度为1时运算结果是等价的。这也就是补码的原理：找到原码描述的数字的同余数，从而帮助计算机将减法转化为加法。
位运算
基本的位运算有：与运算、或运算、异或运算、非运算，以及位移动。
其中与运算、或运算、异或运算都是双目运算符，我们可以简单的用开关和灯泡来形象化理解：
2-与或异或.png
其中两个开关分别代表参与运算的两个位a与b的状态，灯泡的状态则代表输出c。
对于与运算a&b=c，只有当a和b都是1时，c才是1。
对于或运算a|b=c，当a与b任一为1时，c为1。
对于异或a^b=c，当a与b状态不同时，c为1。
非是单目运算符，也就是对输入位状态进行取反：当输入为1（开关闭合时），输出为0（灯不亮）；当输入为0（开关打开时），输出为1（灯泡亮）。
3-非.png
而位移动就是对位状态的直接操作，分为<<左移和>>右移两种操作。
<<左移，相当于在宽度给定的数据范围内，对数据*2
例如：
在宽度为8的情况下，5的二进制表示为：
5: 0000 0101
5<<1: 0000 1010 ===> 也就是10
>>右移，相当于在宽度给定的数据范围内，对数据/2（小数部分直接舍去）
例如：
在宽度为8的情况下，9的二进制表示为：
9: 0000 1001
9>>1: 0000 0100 ===> 也就是4
基本计算的实现
通过位运算，我们就能够很方便的实现加减乘除这四种基本运算。在这四种基本运算中，最核心的是加法，之前我们已经展示了减法如何能用加法进行表示。而乘法也无非加法的扩展，除法则是乘法的一种变形。只要能够进行加法运算，那么一切就迎刃而解。
计算机是如何进行加法的呢？关键就在于异或和位移动两种位运算，异或也叫不进位加法，而通过位移动，则可以实现等同于进位的功效。我们可以先用语言描述以下计算机进行加法的操作过程，然后通过例子来理解。
假设我们需要计算a+b
- Step1: 首先通过异或，获得没有进位的加法结果
sum=a^b - Step2: 通过与运算判断哪一位会产生进位，
carry=a&b； - Step3: 通过左移实现进位
carry <<= 1 - Step4: 在结果上累加进位
newsum = sum^carry - Step5: 检查
sum与carry的累加是否会产生进位，如果sum&carry != 0，那么回到步骤1，此时a=newsum,b=carr<<1；如果不产生进位，则完成了加法
我们来看一个例子，用11+25为例：
* iter1: a = 11，b=25
0000 1011
0001 1001
+
-----------------
0001 0010 ---> Step1: 异或运算得到的sum
0000 1001 ---> Step2: 与运算得到carry
0001 0010 ---> Step3: carry左移一位
0000 0000 ---> Step4: newsum^=carry
0001 0010 ---> Step5: sum&carry不为0，需要进入下一次迭代
* iter2: a = 0，b=36
0000 0000
0010 0100
+
-----------------
0010 0100 ---> Step1: 异或运算得到的sum
0000 0000 ---> Step2: 与运算得到carry
0000 0000 ---> Step3: carry左移一位
0010 0100 ---> Step4: newsum^=carry
0000 0000 ---> Step5: sum&carry为0，不需要进入下一次迭代
最终结果即为0010 0100，也即是十进制的36
