位运算

位运算操作符介绍，原码、反码、补码相关，位运算常用操作

操作符

• & 按位与：同1则1 其余0
• | 按位或：有1则1 都0则0
• ^ 按位异或：同0 异1
• ~ 按位取反：0变1 1变0
• << 左移：左移 n位 = \* 2^n
• >> 右移：右移 n位 = / 2^n （带符号右移 正数右移后高位补0 负数右移后高位补1）

原码、反码、补码

计算储存整型数时 符号位（最高位）0代表正数 1代表负数

int 型可以储存 [-2^32, 2^32-1]

原码：符号位 + 真值绝对值的二进制数

反码：

1. 正整数的反码是它本身
2. 负整数的反码是 符号位为 1 + 真值绝对值的二进制数各位取反

补码：

1. 正整数的补码是它本身
2. 负整数的补码是 符号位为 1 + 真值绝对值的二进制数各位取反再加一 （即在反码的基础上+1）

注：在计算机底层没有减法操作，因此计算机用补码的方式储存负数

例：设 x = 1 原码为 00000000000000000000000000000001

~x 为 11111111111111111111111111111110

-x = 0 - x

0的二进制数为 00000000000000000000000000000000

（在不存在的高一位 借1） -x = 100000000000000000000000000000000 - x = ~x + 1

常用的几个操作

1. 求n的二进制数最后一位

   n & 1

2. 求n的二进制数第k位是多少

   n >> k & 1
   /* n的第k位指从右往左由 0 开始计位 */

3. lowbit (x) 操作 返回x的最后一位1 （100100 则返回 100）

   x & -x
   /* x & (~x + 1) */

假设 x 为 1010…10000

~x = 0101…01111

~x + 1 = 0101…10000

x & ~x+1 后 为 0000…10000