0x01 位运算
0x 代表 16 进制。
0x00~0xFF 是以最高位二进制位为正负符号位的“补码”形式表示的 8 位二进制数。
8 位二进制数对应 char 类型，范围为 -128~127。
其中 0xFF 代表 -1，0x7F 代表最大值 127。
| 与 | 或 | 非 | 异或 |
|---|---|---|---|
| and,& | or,| | not,~ | xor,^,$\oplus$ |
在 $m$ 位二进制数中，通常称最低位为第 0 位，从右到左依此类推，最高位为 $m - 1$ 位。
补码
32 位无符号整数 unsigned int：
直接把这 32 位编码 $C$ 看作 32 位二进制数 $N$。
32 位有符号整数 int：
以最高位为符号位，$0$ 表示非负数，$1$ 表示负数。
对于最高位为 $0$ 的每种编码 $C$，直接看作 32 位二进制数 $S$。
同时，定义该编码按位取反后得到的编码 $\sim C$ 表示的数值为 $-1-S$。
\[C + \sim C=11111111\ 11111111\ 11111111\ 11111111 = 0x7F = -1\]在补码下每个数值都有唯一的表示方式，并且任意两个数值做加减法运算，都等价于在 32 为补码下做最高位不进位的二进制加减法运算。
正数：原码 = 反码 = 补码
负数：反码 = 原码除符号位取反；补码 = 反码 + 1
个人理解：负数补码的符号位相当于 $- 2147483648(2^{31})$，其余位与正数表示数值相同。
0x3F 3F 3F 3F
满足以下两个条件的最大整数。
- 整数的两倍不超过 0x7F FF FF FF，即int能表示的最大正整数。
- 整数的每8位（每个字节）都是相同的。
memset
memset(a, val, sizeof(a));
把数值 $val$(0x00~0xFF) 填充到数组a的每个字节上。
1 个 int 占用 4 个字节，所以只能赋值出 “每 8 位都相同” 的 int。
综上所述，0x7F 7F 7F 7F 是能初始化出的最大数值。
把数值初始化成正无穷时，为避免加法算数上溢或繁琐的判断，
用 memset(a, 0x3f, sizeof(a)) 来代替。
移位运算
左移
在二进制表示下把数字同时向左移动，
低位以 0 填充，高位越界后舍弃。
\[1 << n = 2^n, n << 1 = 2n\]算数右移
在二进制补码表示下把数字同时向右移动，
高位以符号位填充，低位越界后舍弃。
\[n >> 1 = \lfloor {n \over 2.0} \rfloor\]-
算数右移等于除以 2 向下取整。
\((-3) >> 2 = -2，3 >> 1 = 1\) -
“整数/2”在C++中实现为“除以2向零取整”。
\((-3) / 2 = -1，3 / 2 = 1\)
逻辑右移
在二进制位补码表示下把数字同时向右移动，
高位以 $0$ 填充，低位越界后舍弃。
- 一般编译器均使用算数右移。
- 默认右移操作采用算数右移。
【例题】a^b
相关题目：Raising Module Numbers
【例题】 64位整数乘法
二进制状态压缩
将一个长度为 $m$ 的 bool 数组用一个 $m$ 位二进制整数表示并存储。
| 操作 | 运算 |
|---|---|
| 取出整数 $n$ 在二进制表示下的第 $k$ 位 | (n >> k) & 1 |
| 取出整数 $n$ 在二进制表示下的第 $0 \sim k - 1$ 位（后 $k$ 位） | n & ((1 << k) - 1) |
| 把整数 $n$ 在二进制表示下的第 $k$ 位取反 | n ^ (1 << k) |
| 对整数 $n$ 在二进制表示下的第 $k$ 位赋值 $1$ | n | (1 << k) |
| 对整数 $n$ 在二进制表示下的第 $k$ 位赋值 $0$ | n & (~(1 << k)) |
【例题】最短Hamilton路径
【例题】起床困难综合症
成对转换
通过计算可以发现，对于非负整数 $n$：
- 当 $n$ 为偶数时，$n\oplus 1=n+1$。
- 当 $n$ 为奇数时，$n\oplus 1=n-1$。
因此，“0 与 1” “2 与 3” “4 与 5” $\cdots$ 关于 $\oplus 1$ 运算构成 “成对转换”。
在具有无向边（双向边）当图中把一对正反方向的边分别存储在邻接表数组的第 $n$ 与 $n+1$ 位置（其中 $n$ 为偶数），就可以通过 $\oplus 1$ 的运算获取与当前边 $(x,y)$ 反向当边 $(y,x)$ 的存储位置。
lowbit 运算
$lowbit(n)$ 定义为非负整数 $n$ 在二进制表示下“最低位的 $1$ 及其后边所有的 $0$”构成的数值。
设 $n > 0$，$n$ 的第 $k$ 位是 $1$，第 $0 \sim k - 1$ 位都是 $0$。
为了实现 $lowbit$ 运算，先把 $n$ 取反，此时第 $k$ 位变为 $0$，第 $0 \sim k - 1$ 位都是 $1$。再令 $n = n + 1$，此时因为进位，第 $k$ 位变为 $1$，第 $0 \sim k - 1$ 位都是 $0$。
在上面的取反加 $1$ 操作后，$n$ 的第 $k + 1$ 到最高位恰好与原来相反，所以 $n \& (\sim n+1)$ 仅有第 $k$ 位为 $1$，其余为都是 $0$。
而在补码表示下，$～n=-1-n$，因此：
\[lowbit(n) = n \& (\sim n + 1) = n \& (- n)\]