位运算

位运算

计算机采用的是二进制,二进制包括两个数码:0,1。在计算机的底层,一切运算都是基于位运算实现的。

位运算共有 6 种,分别是:与、或、异或、取反、左移和右移,其中左移和右移统称移位运算,移位运算又分为算术移位和逻辑移位。

上述位运算中,只有取反是一元运算,其余的都是二元运算。

参考:
位运算符的概念和性质

1、与、或、异或和取反

  • 与运算的符号是 $\And$ ,运算规则是:全 1 为 1,有 0 为 0
  • 或运算的符号是 $∣$ ,运算规则是:有 1 为 1,全 0 为 0
  • 异或运算的符号是 $\oplus$(在代码中用 $\wedge$ 表示异或),运算规则是:相同为 0 ,不同为 1
  • 取反运算的符号是 $\sim$,运算规则是:0 变 1, 1 变 0

2、移位运算

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

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

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

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

C++ 中:
对于有符号类型,右移运算为算术右移;对于无符号类型,右移运算为逻辑右移。
Java 中:
不存在无符号类型,所有的表示整数的类型都是有符号类型,因此需要区分算术右移和逻辑右移。
算术右移的符号是 $>>$,逻辑右移的符号是 $>>>$
Go 中:
只有算数移位

3、位运算与乘除法

使用移位运算实现乘除法的效率显著于直接乘除法的效率。

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

    • 例如,$29 << 2 = 116$,等价于 $ 29 \times 4 $

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

      例如,$a \times 6$ 等价于 $(a<<2)+(a<<1)$

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

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

    • 例如,$50 >> 2 = 12$ ,等价于 $50 / 4$,结果向下取整
    • 一个数(算术)右移 k 位,和将这个数除以 $2^k$ 是不等价的(只对0和正数成立)

同时,位运算也能用来替代取模运算判断奇偶:

  • 奇数:$整数&1==1$(二进制最低位是1,就是奇数
  • 偶数:$整数&1==0$(二进制最低位是0,就是偶数

4、位运算性质

此处列举位运算中的与、或、异或和取反的常见性质。假设以下出现的变量都是有符号整数。

  • 幂等律:$a \And a = a$ ,$a ∣ a=a$ (注意异或不满足幂等律)
  • 交换律:$a \And b = b \And a$,$a ∣ b = b ∣ a$,$a \oplus b = b \oplus a$
  • 结合律:$(a \And b) \And c = a \And (b \And c)$,$(a ∣ b) ∣ c = a ∣ (b ∣ c)$,$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
  • 分配律:$(a \And b) ∣ c = (a ∣ c) \And (b ∣ c)$,$(a ∣ b) \And c = (a \And c) ∣ (b \And c)$,$(a ⊕ b) \And c = (a \And c) ⊕ (b \And c)$
  • 德·摩根律:$\sim (a \And b) = ( \sim a) ∣ (\sim b)$ ,$\sim(a ∣ b) = (\sim a) \And (\sim b)$
  • 取反运算性质:$-1 = \sim 0,-a = \sim (a-1)$
  • 与运算性质:$a \And 0 = 0$,$a \And (-1) = a$,$a \And (\sim a) = 0$
  • 或运算性质:$a ∣ 0 = a$,$a ∣ (\sim a) = -1$
  • 异或运算性质:$a \oplus 0 = a$,$a \oplus a = 0$
  • 其他性质:
    • $a \And (a-1)$ 的结果:将 a 的二进制表示的最后一个 1 变成 0
    • $a \And (-a)$(与 $a \And (\sim (a-1))$ 等价)的结果:只保留 a 的二进制表示的最后一个 1,其余的 1 都变成 0
作者

SukiEva

发布于

2021-11-25

更新于

2021-12-22

许可协议

CC BY-NC-SA 4.0

评论


取次花丛懒回顾,半缘修道半缘君。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×