位运算的规则

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

机器数:一个数在计算机中的二进制表示形式,叫做这个数的机器数。如: 00000011 和 10000011 就是机器数。

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

  • 原码 就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值, 比如如果是8位二进制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
  • 反码 的表示方法是:正数的反码是其本身,而负数的反码是在其原码的基础上,符号位不变,其余各个位取反。例如:
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
  • 一个反码表示的是负数,人脑无法直观的看出来它的数值,通常要将其转换成原码再计算。
    在应用中,因为补码 能保持加和减运算的统一,表示方法是:
  • 正数的补码就是其本身;
  • 负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1(即在反码的基础上+1)。
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

真值:因为机器数第一位是

符号位,所以机器数的形式值就不等于真正的数值。因此为了好区别,将带符号位的机器数对应的真正数值称为机器数的真值

1.1 为什么会有原码,反码和补码

如下:

  • [+1] = [00000001]原 = [00000001]反 = [00000001]补

但是对于负数:

  • [-1] = [10000001]原 = [11111110]反 = [11111111]补

可见原码, 反码和补码是完全不同的。既然原码才是被人脑直接识别并用于计算表示方式,为何还会有反码和补码呢?

反码的原因:

人脑可以知道第一位是符号位,在计算的时候我们会根据符号位选择对真值区域的加减。但是计算机要辨别"符号位"就必须获得全部的位的数据才可以,显然会让计算机的基础电路设计变得十分复杂!

例如:

1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2

很明显,这是错误的结果;如果用原码表示,让符号位也参与计算,显然对于减法来说,结果是不正确的,这也是为何计算机内部不使用原码表示一个数。

因此,引出了反码

1 - 1 = 1 + (-1) 
= [0000 0001]原 + [1000 0001]原
= [0000 0001]反 + [1111 1110]反 
= [1111 1111]反 = [1000 0000]原 
= -0

用反码计算减法结果的真值部分是正确的,但是"0"的表示有点奇怪,+0和-0是一样的,而且0带符号是没有任何意义,而且要浪费[0000 0000]原和[1000 0000]原两个编码来表示0。

补码的出现

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

例2: -3 + 5

5 的补码:          0000 0101
-3 的补码:         1111 1101
相加所得补码:1 0000 0010
左边 1 溢出范围,舍去:0000 0010

这样0用[0000 0000]表示, 而以前出现问题的-0则不存在了,而且可以用[1000 0000]表示-128:

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

2.位运算规则

位运算主要有:与、或、异或、取反、左移和右移,其中左移和右移统称移位运算,移位运算又分为算术移位和逻辑移位。

2.1 与、或、异或和取反

对于每个二进制为,有以下运算规则:

  • & : 当两个数对应的位都为 1 时,结果才为 1,否则结果为 0。
  • | : 当两个数对应的位都为 0 时,结果才为 0,否则结果为 1。
  • ^ : 对于每个二进制位,当两个数对应的位相同时,结果为 0,否则结果为 1。
  • ~ : 对一个数的每个二进制位进行取反操作,0 变成 1,1 变成 0。

46 的二进制表示是 00101110,51 的二进制表示是 00110011。考虑以下位运算的结果。

  • 46&51的结果是34,对应的二进制表示是 00100010。
  • 46|51 的结果是63,对应的二进制表示是 00111111。
  • 46⊕51 的结果是29,对应的二进制表示是 00011101。
  • ∼46 的结果是−47,对应的二进制表示是 11010001。
  • ∼51 的结果是 −52,对应的二进制表示是 11001100。

2.2 移位运算

移位运算按照移位方向分类可以分成左移和右移,按照是否带符号分类可以分成算术移位和逻辑移位。

原始:0000 0110 = 6

  • 右移一次:0000 0011 3 相当于除以2
  • 左移一次:0000 1100 12 相当于乘以2

左移运算的符号是 <<,左移运算时,将全部二进制位向左移动若干位,高位丢弃,低位补 0。对于左移运算,算术移位和逻辑移位是相同的。
右移运算的符号是 >>。右移运算时,将全部二进制位向右移动若干位,低位丢弃,高位的补位由算术移位或逻辑移位决定:

  • 算术右移时,高位补最高位;
  • 逻辑右移时,高位补 0。

左移示例:

  • 示例1:29 的二进制表示是 00011101。29左移 2 位的结果是 116,对应的二进制表示是 01110100;29 左移 3 位的结果是 −24,对应的二进制表示是 11101000。
  • 示例2:50的二进制表示是 00110010。50 右移 1 位的结果是 25,对应的二进制表示是 00011001;50 右移 2 位的结果是 12,对应的二进制表示是 00001100。对于 0和正数,算术右移和逻辑右移的结果是相同的。
  • 示例3:-50的二进制表示是 11001110(补码)。-50 算术右移 2 位的结果是 −13,对应的二进制表示是 11110011;−50 逻辑右移 2位的结果是 51,对应的二进制表示是 00110011。

右移运算中的算术移位和逻辑移位是不同的,计算机内部的右移运算采取的是哪一种呢?

  • 对于 C/C++ 而言,数据类型包含有符号类型和无符号类型,其中有符号类型使用关键字signed 声明,无符号类型使用关键字 unsigned 声明,两个关键字都不使用时,默认是有符号类型。对于有符号类型,右移运算为算术右移;对于无符号类型,右移运算为逻辑右移。
  • 对于 Java 而言,不存在无符号类型,所有的表示整数的类型都是有符号类型,因此需要区分算术右移和逻辑右移。在Java 中,算术右移的符号是 >>,逻辑右移的符号是 >>>,也就是所谓的无符号右移

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

由于计算机的底层的一切运算都是基于位运算实现的,因此使用移位运算实现乘除法的效率显著高于直接乘除法的。

2.3.1 乘法

移运算对应乘法运算。将一个数左移 k位,等价于将这个数乘以 2^k。

例如: 29 左移 2 位的结果是 116,等价于 29×4

当乘数不是 2 的整数次幂时,可以将乘数拆成若干项 2 的整数次幂之和

例如,a×6 等价于 (a<<2)+(a<<1)

对于任意整数,乘法运算都可以用左移运算实现,但是需要注意溢出的情况,例如在 8 位二进制表示下,29 左移 3 位就会出现溢出。

2.3.2 除法

算术右移运算对应除法运算,将一个数右移 k 位,相当于将这个数除以 2^k。

例如,50 右移 2 位的结果是 12,等价于 50/4,结果向下取整。

问: 将一个数(算术)右移 k 位,是否和将这个数除以 2^k等价?

答案是: 对于 0 和正数,上述说法是成立的,整数除法是向 0 取整,右移运算是向下取整,也是向 0 取整;但是对于负数,上述说法就不成立了,整数除法是向 0 取整,右移运算是向下取整,两者就不相同了。

例如:

(−50)>>2 的结果是 −13,而 (−50)/4 的结果是 −12,两者是不相等的。

不过,算法出题这早就考虑到了这一点,因此在大部分算法题都将测试数据限制在正数和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 & c) ∣ (b & c),(a⊕b) & c=(a & c)⊕(b & c);
  • 德摩根律:∼(a & b)=(∼a) ∣ (∼b),∼(a ∣ b)=(∼a) & (∼b);
  • 取反运算性质:−1=∼0,−a=∼(a−1);
  • 与运算性质:a & 0=0,a & (−1)=a,a & (∼a)=0;
  • 或运算性质:a ∣ 0=a;
  • 异或运算性质:a⊕0=a,a⊕a=0;

根据上面的性质,可以得到很多处理技巧,这里列举几个:

  • a & (a−1) 的结果为将 a 的二进制表示的最后一个 1 变成 0;
  • (补码)a & (−a)的结果为只保留 a 的二进制表示的最后一个 1,其余的 1 都变成 0。

下面的示例中,1s和0s分别表示与x等长的一串1和一串0:

image-20240304191910083

1.获取

接着堆这个值与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 |(1<<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); 
}