算法通关村十一关 | 位运算的规则

1.数字在计算机中的表示

1. 机器数：一个数在计算机中的二进制表示形式，叫做这个数的机器数。机器数是自带符号的，在计算机用一个数的最高位存放符号，整数为0，负数为1。比如，十进制中的数+3，计算机字长8位，转换成二进制就是00000011.如果是-3.就是10000011。两者都是机器数。

2. 真值：因为机器数的第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数10000011，其实最高位1代表负，其真正数值是-3，而不是形式数值131（10000011转换成10进制等于131）。所以将带符号位的机器数对应的的真正数值称为机器数的真值。（0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = -000 0001 = -1）。

   计算机对机器数的表示进一步细化：原码，反码，补码。

3. 原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值，比如如果是8位二进制：

   [+1]原 = 0000 0001

   [-1]原 = 1000 0001

   第一位是符号位所以8进制的取值范围是

   [1111 1111, 0111 1111] 即[-127 , 127]

4. 反码的表示方法是：正数的反码是其本身，负数的反码在原码的基础上，符号位不变，其它位取反。

   [+1] = [0000 0001]原 = [0000 0001]反

   [-1] = [1000 0001]原 = [1111 1110]反

   可以发现一个反码表示的是负数，人脑无法直观的看出来它的数值，通常要将其转换成原码再计算。

   因为补码能保持加和减运算的统一，因此应用更广，其表示方法是：

   • 正数的补码就是其本身

   • 负数的补码是在反码的基础上加1

   对于负数，补码也需要转换成原码在计算其数值

   拓展为何会有原码、反码和补码？

   [+1] = [0000 0001]原 = [0000 0001]反 = [0000 0001]补

   [-1] = [1000 0001]原 = [1111 1110]反 = [1111 1111]补

   我们都知道计算机中只有加法，我们看个例子，计算十进制的表达式：1-1=0，看原码表示：

   1- 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [1000 0010]原 = -2

   结果不正确

   用反码计算：

   1- 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原

   = [0000 0001]反 + [1111 1110]反

   =[1111 1111]反 = [1000 0000] 原 =-0

   有点奇怪，0带符号没有意义

   用补码计算：

   1- 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原

   = [0000 0001]补 + [1111 1111]补

   =[0000 0000] 补+[0000 0000]原 = 0

   负0就不存在了，可以用[1000 0000] 表示-128。补码的表示范围就是[-128 - 127]

2.位运算规则

2.1与、或、异或和取反

1. 与运算 & ，规则：对于每个二进制位，两个数都为1，结果才为1，否则结果为0.

   0 & 0 = 0

   0 & 1 = 0

   1 & 0 = 0

   1 & 1 = 1

2. 或运算 | ，规则：对于每个二进制位，两个数都为0时，结果才为0，否则结果为1.

   0 | 0 = 0

   0 | 1 = 1

   1 | 0 = 1

   1 | 1 = 1

3. 异或运算的符号价⊕（在代码中用^表示），相同为0，不同为1

   0 ⊕ 0 = 0

   0 ⊕ 1 = 1

   1 ⊕ 0 = 1

   1 ⊕ 1 = 0

4. 取反运算符号 ~,运算规则，0变1，1变0，

2.2 移位运算

1. 移位运算分为左移和右移，按照是否带符号可以分成算术运算和逻辑移位。

   原始：0000 0110 6

   右移一次：0000 0011 3 相当于除以2

   左移一次：0000 1100 12 相当于乘于2

1. 左移运算的符号是<< ,左移运算时，将全部运算时，将全部二进制位向左移动若干位，高位丢弃，低位补0。对于左移运算，算术移位和逻辑移位是相同的。

2. 右移运算的符号是>>,右移运算时，将全部的二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定：

   • 算术移位时，高位补最高位，（负数最高位补1，正数补0）

   • 逻辑右移时，高位补0

   在计算机中，对于0和正数，算术移位和逻辑移位结果是相同的。负数的结果时不同的。

   对于C++，数据类型包含有符号和无符号类型。有符号类型右移为算术右移，无符号类型右移运算为逻辑右移。

   对于Java，不存在无符号类型，算术右移是>>,逻辑右移是>>>

2.3 移位运算与乘除法的关系

1. 左移运算对应乘法关系。低位补0，将一个数左移k位，相当于这个数乘于2^k.

2. 右移运算对应除法关系，将一个数右移k位，相当于这个数除以2^k.

   需要注意的是：

   • 左移无需考虑太多只需低位补0即可。

   • 对于负数和正数的右移对应的结果是不一致的，分为算术右移和逻辑右移。算法在出题的时候考虑到这一点，大部分会将数据限制在正数和0的情况 ，因此可以放心的左移或右移。

2.4 位运算技巧

位运算的性质有很多，有一些运算公式，

• 幂等律：a&a=a, a | a = a （注意异或运算不满足幂等率）

• 交换律：a & b = b & a, a| b = b | a, a ⊕ b = b ⊕ a

• 结合律：( a & b) & c = a& ( b& c) ,(a | b) | c = a | ( b | c),(a ⊕ b) & c = a ⊕( b ⊕ c)

• 分配律：(a & b) | c = ( a & c) & ( b & c) ,(a | b) & c = (a & b) | ( b& c) ,异或同理

• 德摩根律：~（a & b）= ( ~a) | (~ b), ~(a | b) = (~a) & (~b)

• 取反运算性质：-1 = ~0, -a = ~( a - 1)

• 与运算性质：a & 0 = a, a& (~1) = a,a & (~a) = 0;

• 或运算性质： a | 0 = a, a | ( ~ a) = -1 ;

• 异或运算性质: a⊕0 = a, a⊕a = 0;

根据上面的性质可以得到很多的处理技巧，

• a & (a - 1) 的结果位将a的二进制表示的最后一个1变为0；

• （补码）a&(-a) 的结果为只保留a的二进制表示的最后一个，其余的1都变成0.

如何获取、设置、和更新某个位的数据，也有固定的套路。

1. 获取

   该方法是将1左移i位，得到形如00010000的值，接着对这个值与num执行“位与”操作，从而将i位之外的所有位清零，最后检查该结果是否为零。不为零i位为1，否则i位位0。代码如下：

   boolean getBit(int num, int i) {

   return ((num & (1 << i))) != 0;

   }

2. 设置（将某一位置设置为1）

   setBit先将1右移i位，得到形如00010000的值，接着对这个值和num执行“位或”操作，这样只会改变i位的数据。除i位外的位均为零，故不会影响num的其余位。代码如下：

   int setBIt(int num, int i) {

   return num | (i << i);

   }

3. 清零（将某一位置设置为0）

   该方法与setBit方法相反，首先将1左移i位获得形如00010000的值，对这个值取反的到类似11101111的值，接着对该值和num执行“位与”，古不会影响到num的其余位，只会清零i位。代码如下：

   int clearBit(int num, int i) {

   int mask = ~(1 << i); return num & mask;

   }

4. 更新

   这个方法是将setBit和clearBit合二为一，首先用11101111的值num的第i位清零，接着将待写入的值v左移i位，得到一个i位为v但其余为都为0的数。最后对之前的结果执行“位或”操作，v为1则num的i位更新为1，否则为0.代码如下：

   int updateBit(int num, int i, int v) {

   int mask = ~(1 << i); return (num & mask) | (v << i);

   }