位运算基础知识

正数和负数在二进制中的表达

正数的二进制状态转负数的二进制：

1. -1
2. 依次取反

例：
7的二进制为 0111 转为负数则为 0110 -> 1001

负数的二进制状态转正数的二进制，为逆过程：

1. 依次取反
2. +1

例：
-7的二进制为 1001 转为正数则为 0110 -> 0111

常见的位运算操作符

• | 或

  相同位次中只要出现1则返回1

  如 0010 | 0111 = 0111

• & 与

  相同位次中都出现1则返回1

  如 0010 & 0111 = 0010

• ~ 取反

  0变成1，1变成0

  如 ~0010 = 1101

• ^ 异或

  相同位次中都不同才返回1，否则返回0。可以看成无进位的相加

  如 0010 ^ 0111 = 0101

• >> 右移 和 << 左移

  将二进制整体向左/右移动k位，多出的位置用0补

  如 0010 >> 1 = 0100 0010 >> 1 = 0001

  对于非负整数而言 左移相当于扩大2的k次方倍，左移相当于缩小2的k次方倍

• >>> 右移

  和>>功能相同，但是多出的位置用符号位补

  如 1010 >>> 1 = 1101

一些技巧

取每个位次的数

对于32位的int类型数据，可以用如下方法依次取出每个位次的数

// 输入num
for (int i = 31; i >= 0; --i) {
	int tmp = (num >> i) & 1;
	std::cout << tmp << ' ';
}

向二进制状态填入1

对于0而言，可以用如下方法向指定位置填入1

ans |= 1 << i; // i为指定位置

异或运算的性质和Brain Kernighan算法

异或运算的性质：

1. a ^ 0 = 0、a ^ a = 0
2. 异或运算可以看成是无进位的相加
3. 异或运算满足交换律 即a ^ b = c -> c ^ b = a
4. 负数和正数的相互转化可以用a = ~a + 1，相当于a = -a

Brain Kernighan算法

目的：提取出二进制状态最右边的1

int pos = a & (-a);