iOS开发之位运算

一、二进制

1、什么是二进制

二进制（binary），发现者莱布尼茨，是在数学和数字电路中以2为基数的记数系统，是以2为基数代表系统的二进位制。这一系统中，通常用两个不同的符号0（代表零）和1（代表一）来表示 [1] 。数字电子电路中，逻辑门的实现直接应用了二进制，现代的计算机和依赖计算机的设备里都使用二进制。每个数字称为一个比特（Bit，Binary digit的缩写）

2、计算机为什么采用二级制

首先，二进位计数制仅用两个数码。0和1，所以，任何具有二个不同稳定状态的元件都可用来表示数的某一位。而在实际上具有两种明显稳定状态的元件很多。例如，氖灯的“亮”和“熄” ；开关的“开” 和 “关”；电压的“高” 和“低”、“正”和 “负”；纸带上的“有孔”和“无孔”；电路中的“有信号” 和 “无信号”； 磁性材料的南极和北极等等，不胜枚举。 利用这些截然不同的状态来代表数字，是很容易实现的。不仅如此，更重要的是两种截然不同的状态不单有量上的差别，而且是有质上的不同。这样就能大大提高机器的抗干扰能力，提高可靠性。而要找出一个能表示多于二种状态而且简单可靠的器件，就困难得多了 [8] 。

其次，二进位计数制的四则运算规则十分简单。而且四则运算最后都可归结为加法运算和移位，这样，电子计算机中的运算器线路也变得十分简单了。不仅如此，线路简化了，速度也就可以提高。这也是十进位计数制所不能相比的 [8] 。

第三，在电子计算机中采用二进制表示数可以节省设备。可 以从理论上证明，用三进位制最省设备，其次就是二进位制。但由于二进位制有包括三进位制在内的其他进位制所没有的优点，所以大多数电子计算机还是采用二进制。此外，由于二进制中只用二个符号 “ 0” 和“1”，因而可用布尔代数来分析和综合机器中的逻辑线路。 这为设计电子计算机线路提供了一个很有用的工具[8] 。

由于计算机的硬件决定，任何存储于计算机中的数据，其本质都是以二进制码存储。

根据冯·诺依曼提出的经典计算机体系结构框架，一台计算机由运算器、控制器、存储器、输入和输出设备组成。其中运算器只有加法运算器，没有减法运算器（据说一开始是有的，后来由于减法运算器硬件开销太大，被废了）。

所以计算机中没办法直接做减法的，它的减法是通过加法实现的。现实世界中所有的减法也可以当成加法的，减去一个数可以看作加上这个数的相反数，但前提是要先有负数的概念，这就是为什么不得不引入一个符号位。符号位在内存中存放的最左边一位，如果该位位0，则说明该数为正；若为1，则说明该数为负。

而且从硬件的角度上看，只有正数加负数才算减法，正数与正数相加，负数与负数相加，其实都可以通过加法器直接相加。

原码、反码、补码的产生过程就是为了解决计算机做减法和引入符号位的问题。

二、原码、反码、补码

数值在计算机中是以补码的方式存储的，在探求为何计算机要使用补码之前， 让我们先了解原码， 反码和补码的概念。

对于一个数， 计算机要使用一定的编码方式进行存储。 原码， 反码， 补码是计算机存储一个具体数字的编码方式。

一个数在计算机中的二进制表示形式， 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号， 正数为0， 负数为1。比如，十进制中的数 +2 ，计算机字长为8位，转换成二进制就是[00000010]。如果是 -2 ，就是 [10000010] 。因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 [10000010]，其最高位1代表负，其真正数值是 -2 而不是形式值130（[10000010]转换成十进制等于130）。所以将带符号位的机器数对应的真正数值称为机器数的真值。

原码就是符号位加上真值的绝对值， 即用第一位表示符号， 其余位表示值。

反码的表示方法是:正数的反码是其本身；负数的反码是在其原码的基础上， 符号位不变，其余各个位取反。

补码的表示方法是:正数的补码就是其本身；负数的补码是在其原码的基础上， 符号位不变， 其余各位取反， 最后+1。 (即在反码的基础上+1)

2.1原码

原码：是最简单的机器数表示法，用最高位表示符号位，其他位存放该数的二进制的绝对值。

以带符号位的四位二进制数为例：1010，最高位为1表示这是一个负数，其它三位010，即02^2+12^1+0*20=2，所以1010表示十进制数-2。

	正数		负数
0	0000	-0	1000
1	0001	-1	1001
2	0010	-2	1010
3	0011	-3	1011
4	0100	-4	1100
5	0101	-5	1101
6	0110	-6	1110
7	0111	-7	1111

原码的表示法很简单，虽然出现了+0和-0，但是直观易懂。于是开始运算：

0001+0010=0011，1+2=3；
0000+1000=1000，+0+(-0)=-0；
0001+1001=1010，1+(-1)=-2。

于是可以看到其实正数之间的加法通常是不会出错的，因为它就是一个很简单的二进制加法，而正数与负数相加，或负数与负数相加，就要引起莫名其妙的结果，这都是符号位引起的。0分为+0和-0也是因它而起。

原码的特点：

1. 原码表示直观、易懂，与真值转换容易。

2. 原码中0有两种不同的表示形式，给使用带来了不便。

   通常0的原码用+0表示，若在计算过程中出现了-0，则需要用硬件将-0变成+0。

3. 原码表示加减运算复杂。

   利用原码进行两数相加运算时，首先要判别两数符号，若同号则做加法，若异号则做减法。在利用原码进行两数相减运算时，不仅要判别两数符号，使得同号相减，异号相加；还要判别两数绝对值的大小，用绝对值大的数减去绝对值小的数，取绝对值大的数的符号为结果的符号。可见，原码表示不便于实现加减运算。

2.2 反码

原码最大的问题就在于一个数加上它的相反数不等于0，于是反码的设计思想就是冲着解决这一点，既然一个负数是一个正数的相反数，那干脆用一个正数按位取反来表示负数。

反码：正数的反码还是等于原码；负数的反码就是它的原码除符号位外，按位取反。

以带符号位的四位二进制数为例：3是正数，反码与原码相同，则可以表示为0011；-3的原码是1011，符号位保持不变，低三位按位取反，所以-3的反码为1100。

image.png

再试着用反码的方式解决一下原码的问题：

0001+1110=1111，1+(-1)=-0；
1110+1100=1010，(-1)+(-3)=-2。

互为相反数相加等于0，虽然的到的结果是1111也就是-0。但是两个负数相加的出错了。

反码的特点：

1. 在反码表示中，用符号位表示数值的正负，形式与原码表示相同，即0为正；1为负。

2. 在反码表示中，数值0有两种表示方法。

3. 反码的表示范围与原码的表示范围相同。

反码表示在计算机中往往作为数码变换的中间环节。

2.2 补码

补码：正数的补码等于它的原码；负数的补码等于反码+1（这只是一种算补码的方式，多数书对于补码就是这句话）。

其实负数的补码等于反码+1只是补码的求法，而不是补码的定义，很多人以为求补码就要先求反码，其实并不是，那些计算机学家并不会心血来潮的把反码+1就定义为补码，只不过补码正好就等于反码+1而已。

如果有兴趣了解补码的严格说法，建议可以看一下《计算机组成原理》，它会用“模”和“同余”的概念，严谨地解释补码。

2.2.1补码的思想

补码的思想，第一次见可能会觉得很绕，但是如果肯停下来仔细想想，绝对会觉得非常美妙。

补码的思想其实就是来自于生活，只是我们没注意到而已，如时钟、经纬度、《易经》里的八卦等。补码的思想其实就类似于生活中的时钟。

如果说现在时针现在停在10点钟，那么什么时候会停在八点钟呢？

简单，过去隔两个小时的时候是八点钟，未来过十个小时的时候也是八点钟。
也就是说时间倒拨2小时，或正拨10小时都是八点钟。
也就是10-2=8，而且10+10=8。
这个时候满12，说明时针在走第二圈，又走了8小时，所以时针正好又停在八点钟。

所以12在时钟运算中，称之为模，超过了12就会重新从1开始算了。

也就是说，10-2和10+10从另一个角度来看是等效的，它都使时针指向了八点钟。

既然是等效的，那么在时钟运算中，减去一个数，其实就相当于加上另外一个数（这个数与减数相加正好等于12，也称为同余数），这就是补码所谓运算思想的生活例子。

在这里，再次强调原码、反码、补码的引入是为了解决做减法的问题。在原码、反码表示法中，我们把减法化为加法的思维是减去一个数等于加上这个数的相反数，结果发现引入符号位，却因为符号位造成了各种意想不到的问题。

但是从上面的例子中，可以看到其实减去一个数，对于数值有限制、有溢出的运算（模运算）来说，其实也相当于加上这个数的同余数。

也就是说，不引入负数的概念，就可以把减法当成加法来算。

2.2.2补码的实例

接下来就做一做四位二进制数的减法（先不引入符号位）。

0110-0010，6-2=4，但是由于计算机中没有减法器，没法算。

这时候，想想时钟运算中，减去一个数，是可以等同于加上另外一个正数（同余数），这个数与减数相加正好等于模。

也就是四位二进制数最大容量是多少？其实就是2^4=16（10000）。

那么-2的同余数，就等于10000-0010=1110，16-2=14。

既然如此，0110-0010=0110+1110=10100，6-2=6+14=20。

按照这种算法得出的结果是10100，但是对于四位二进制数最大只能存放4位，如果低四位正好是0100，正好是想要的结果，至于最高位的1，计算机会把它放入psw寄存器进位位中，8位机会放在cy中，x86会放在cf中，这里不做讨论。

这个时候，再想想在四位二进制数中，减去2就相当于加上它的同余数（至于它们为什么同余，还是建议看《计算机组成原理》）。

但是减去2，从另一个角度来说，也是加上-2，即加上-2和加上14得到的二进制结果除了进位位，结果是一样的。如果我们把1110的最高位看作符号位后就是-2的补码，这可能也是为什么负数的符号位是1，而不是0。

image.png

到这里，原码、反码的问题，补码基本解决了。

在补码中也不存在-0了，因为1000表示-8。

补码的特点：

1. 在补码表示中，用符号位表示数值的正负，形式与原码的表示相同，即0为正，1为负。但补码的符号可以看做是数值的一部分参加运算。

正数的补码表示就是其本身，负数的补码表示的实质是把负数映像到正值区域，因此加上一个负数或减去一个正数可以用加上另一个数（负数或减数对应的补码）来代替。
从补码表示的符号看，补码中符号位的值代表了数的正确符号，0表示正数，1表示负数；而从映像值来看，符号位的值是映像值的一个数位，因此在补码运算中，符号位可以与数值位一起参加运算。

2. 在补码表示中，数值0只有一种表示方法。

3. 负数补码的表示范围比负数原码的表示范围略宽。纯小数的补码可以表示到-1，纯整数的补码可以表示到-2^n。

   由于补码表示中的符号位可以与数值位一起参加运算，并且可以将减法转换为加法进行运算，简化了运算过程，因此计算机中均采用补码进行加减运算。

2.2.3为什么负数的补码的求法是反码+1

因为负数的反码加上这个负数的绝对值正好等于1111，再加1，就是10000，也就是四位二进数的模，而负数的补码是它的绝对值的同余数，可以通过模减去负数的绝对值得到它的补码，所以负数的补码就是它的反码+1。

总结：

1. 计算机在进行减法时，都是在做加法运算。

2. 正数原码、反码、补码是一样。

3. 负数的反码，在原码的基础上，符号位不变，其余的各个位取反（1变0，0变1）。

4. 负数的补码，就是反码+1.

三、位运算

1、按位与运算符（&）

参加运算的两个数据，按二进制位进行“与”运算。

运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;

即：两位同时为“1”，结果才为“1”，否则为0

例如：3&5 即 0000 0011& 0000 0101 = 00000001 因此，3&5的值得1。

另，负数按补码形式参加按位与运算。

“与运算”的特殊用途：

（1）清零。如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

（2）取一个数中指定位

方法：找一个数，对应X要取的位，该数的对应位为1，其余位为零，此数与X进行“与运算”可以得到X中的指定位。

例：设X=10101110，

取X的低4位，用 X & 0000 1111 = 00001110 即可得到；

还可用来取X的2、4、6位。

2、按位或运算符（|）

参加运算的两个对象，按二进制位进行“或”运算。

运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；

即 ：参加运算的两个对象只要有一个为1，其值为1。

例如:3|5　即 00000011 | 0000 0101 = 00000111 因此，3|5的值得7。

另，负数按补码形式参加按位或运算。

“或运算”特殊作用：

（1）常用来对一个数据的某些位置1。

方法：找到一个数，对应X要置1的位，该数的对应位为1，其余位为零。此数与X相或可使X中的某些位置1。

例：将X=10100000的低4位置1 ，用X | 0000 1111 = 1010 1111即可得到。

3、异或运算符（^）

参加运算的两个数据，按二进制位进行“异或”运算。

运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；

即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

“异或运算”的特殊作用：

（1）使特定位翻转找一个数，对应X要翻转的各位，该数的对应位为1，其余位为零，此数与X对应位异或即可。

例：X=10101110，使X低4位翻转，用X ^0000 1111 = 1010 0001即可得到。

（2）与0相异或，保留原值 ，X ^ 00000000 = 1010 1110。

从上面的例题可以清楚的看到这一点。

4、取反运算符（~）

参加运算的一个数据，按二进制位进行“取反”运算。

运算规则：~1=0； ~0=1；

即：对一个二进制数按位取反，即将0变1，1变0。

使一个数的最低位为零，可以表示为：a&~1。

_{1的值为1111111111111110，再按“与”运算，最低位一定为0。因为“}”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

5、左移运算符（<<）

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

例：a = a<< 2将a的二进制位左移2位，右补0，

左移1位后a = a *2;

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

6、右移运算符（>>）

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

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

例如：a = a>> 2 将a的二进制位右移2位，

左补0 or 补1得看被移数是正还是负。

">>" 运算符把expression1 的所有位向右移 expression2指定的位数。expression1的符号位被用来填充右移后左边空出来的位。向右移出的位被丢弃。

例如，下面的代码被求值后，temp 的值是 -4：

-14 （即二进制的 11110010）右移两位等于 -4（即二进制的 11111100）。

var temp = -14 >> 2

7、无符号右移运算符（>>>）（Objective-C不支持）

">>>"运算符把 expression1 的各个位向右移expression2 指定的位数。右移后左边空出的位用零来填充。移出右边的位被丢弃。

例如：var temp = -14 >>>2

变量 temp的值为 -14 （即二进制的 11111111 11111111 1111111111110010），向右移两位后等于 1073741820 （即二进制的 00111111 11111111 1111111111111100）。

8、复合赋值运算符

位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：

&= 例：a &=b 相当于a=a& b

|= 例：a |=b 相当于a=a |b

">>=" 例：a >>=b 相当于a=a>> b

"<<=" 例：a<<=b 相当于a=a<< b

"^=" 例：a ^= b 相当于a=a^ b

运算规则：和前面讲的复合赋值运算符的运算规则相似。

不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时，系统会将二者按右端对齐，然后进行位运算。

以“与”运算为例说明如下：我们知道在C语言中long型占4个字节，int型占2个字节，如果一个long型数据与一个int型数据进行“与”运算，右端对齐后，左边不足的位依下面三种情况补足，

（1）如果整型数据为正数，左边补16个0。

（2）如果整型数据为负数，左边补16个1。

（3）如果整形数据为无符号数，左边也补16个0。

如：long a=123;int b=1;计算a& b。

如：long a=123;int b=-1;计算a& b。

如：long a=123;unsigned intb=1;计算a & b。

9、总结

含义	运算符
按位与	&
按位或	l
按位异域	……
按位取反	~
左移	<<
右移	>>
无符号右移	>>>

10、位运算详细示例：

      int d = 3 & 4;
      //0000 0000 0000 0000 0000 0000 0000 0011   //3的原码
      //0000 0000 0000 0000 0000 0000 0000 0100   //4的原码
      //0000 0000 0000 0000 0000 0000 0000 0000   //按位与后为0
      int e = 3 | 4;
      //0000 0000 0000 0000 0000 0000 0000 0011   //3的原码
      //0000 0000 0000 0000 0000 0000 0000 0100   //4的原码
      //0000 0000 0000 0000 0000 0000 0000 0111   //按位或后为7
      int x = 3 ^ 4;
      //0000 0000 0000 0000 0000 0000 0000 0011   //3的原码
      //0000 0000 0000 0000 0000 0000 0000 0100   //4的原码
      //0000 0000 0000 0000 0000 0000 0000 0111   //按位异域后为7
      int y = ~3;
      //0000 0000 0000 0000 0000 0000 0000 0011   //3的原码
      //1111 1111 1111 1111 1111 1111 1111 1100   //取反后为-4（负数的计算是先减一从补码获取反码，再从反码获取原码，获取的正数值再加上负号）
      NSLog(@"d:%d,e:%d，x:%d,y:%d",d,e,x,y);
      int f = -15;
      //0000 0000 0000 0000 0000 0000 0000 1111   //15的原码
      //1111 1111 1111 1111 1111 1111 1111 0000   //15的反码
      //1111 1111 1111 1111 1111 1111 1111 0001   //在补码(+1)，就是-15的原码
      int h = f >> 2;//-4
      //1111 1111 1111 1111 1111 1111 1111 1100   //右移两位，因为是负数，左边补充的全是1
      //1111 1111 1111 1111 1111 1111 1111 1011   //减一,从补码转成反码
      //0000 0000 0000 0000 0000 0000 0000 0100   //从反码转成原码，因为是负数，所以获取值为-4
      int g = f << 2;//-60
      //1111 1111 1111 1111 1111 1111 1100 0100   //左移两位，右边补充2位0，最左边两位直接舍去
      //1111 1111 1111 1111 1111 1111 1100 0011   //减一，从补码转成反码
      //0000 0000 0000 0000 0000 0000 0011 1100   //从反码转成原码，因为是负数，所以获取值为-60
      NSLog(@"h:%d;g:%d",h,g);</pre>

借鉴原文：https://www.jianshu.com/p/1b3b8e853f83