位运算(bitwise)

2020-06-21  本文已影响0人  侧耳倾听y

计算机底层是使用二进制形式存储数据的,每一位是1或者0,因此当我们在某些场景使用位运算的时候,效率会更高一些。

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
含义 运算符 示例
左移 << 0011 => 0110
右移 >> 0110 => 0011
~0 = 1
比较常用的位运算
\color{rgb(0, 100, 0)}{异或} 解释
\color{rgb(0, 100, 0)}{1} x ^ 0 = x 任何数与0异或,结果都是它本身
\color{rgb(0, 100, 0)}{2} x ^ x = 0 任何数与它本身异或,结果都是0
\color{rgb(0, 100, 0)}{3} x ^ 1s = ~x (1s为全1) 一个数和全1异或,相当于取反
\color{rgb(0, 100, 0)}{4} x ^ (~x) = 1s 一个数和它取反后的结果异或,结果为全1
\color{rgb(0, 100, 0)}{5} c = a ^ b => a ^ c = b, b ^ c = a 交换两个数
\color{rgb(0, 100, 0)}{6} a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c 加法(异或)结合律

示例
\color{rgb(0, 100, 0)}{1} 1100 ^ 0000 = 1100
\color{rgb(0, 100, 0)}{2} 1100 ^ 1100 = 0000
\color{rgb(0, 100, 0)}{3} 1100 ^ 1111 = 0011 (~1100 = 0011)
\color{rgb(0, 100, 0)}{4} 1100 ^ 0011 = 1111

\color{rgb(0, 100, 0)}{指定位置的位运算} 解释
\color{rgb(0, 100, 0)}{1} x & (~0<<n) 将x最右边的n位清零
\color{rgb(0, 100, 0)}{2} (x>>n) & 1 获取x的第n位值(0或者1)
\color{rgb(0, 100, 0)}{3} x & (1<<n) 获取x的第n位的幂值
\color{rgb(0, 100, 0)}{4} x 丨 (1<<n) 仅将第n位置为1
\color{rgb(0, 100, 0)}{5} x & ((1<<n) - 1) 将x最高位至第n位(包含)清零
\color{rgb(0, 100, 0)}{6} x & (~(1 << n)) 仅将第n位置为0

示例(都只用四位) , 假设n = 2, x = 1101
\color{rgb(0, 100, 0)}{1} ~0 = 1111,1111 << 2 = 1100, 1101& 1100 = 1100
\color{rgb(0, 100, 0)}{2} 即将x的第n位移到最低位,和1做与运算:1101 >> 2 = 0011,0011 & 0001 = 1
\color{rgb(0, 100, 0)}{3} 即将1移到n的位置,和x做与运算:1 << 2 = 0100, 1101 & 0100 = 0100
\color{rgb(0, 100, 0)}{4} 即将1移到n的位置,和x做或运算:1 << 2 = 0100,1101 | 0100 = 1101
\color{rgb(0, 100, 0)}{5} 即将x与n之后为全1的数做与运算:1 << 2 = 0100,0100 - 1 = 0011,1101 & 0011 = 0001
\color{rgb(0, 100, 0)}{6} 即将x与一个除了第n位之外全是1的数做与运算:1 << 2 = 0100,~0100 = 1011,1101 & 1011 = 1001

\color{rgb(0, 100, 0)}{用的较多的位运算} 解释
x % 2 == 1 ----> (x & 1) == 1 奇数判断
x % 2 == 0 ----> (x & 1) == 0 偶数判断
x >> 1---->x / 2 一个数右移1位,相当于对2取模
x = x & (x - 1) 清零最低位的1
x & -x 得到最低位的1
x & ~x => 0 一个数和它的取反结果做与运算,结果为0
一些练习题
\color{rgb(0, 100, 0)}{题目} 用到的位运算
位1的个数 x = x & (x - 1)
2的幂 x = x & (x - 1)
颠倒二进制位 移位操作
上一篇下一篇

猜你喜欢

热点阅读