位运算 | OI笔记

计算机数据存储方式

例：当(int)x = 10
注：int类型整数共计有32位，不足的位数在前面补0

原码

对于一个
表示原本的二进制数：x = 000…1010

反码

将二进制数的每一位进行取反运算：x = 111…0101

补码

对于x，除符号位不变之外进行~x + 1的操作：x = 111…0110

shudecunchu

---

进制转换

• 10进制转2进制： 短除法，逆序取余

• 2进制转10进制： 乘权求和

• 二进制转八进制： 取二进制的三位

• 八进制转二进制

同理，二进制与十六进制之间的转换也可以类比以上的方法，每四位转换为一个十六进制

一张模板走天下

注：在此62进制的数中
0 ~ 9 表示 0 ~ 9
A ~ Z 表示 11 ~ 35
a ~ z 表示 36 ~ 61
另外，此模板使用了高精度，可以适用于所有情况

此题可以简化为两个目标：

• $a$ 进制转十进制（秦九韶迭代）
• 十进制转 $b$ 进制

图解：

位运算

按位与 &

0 & 0 = 0， 1 & 0 = 0， 1 & 1 = 1

与运算的应用：

• 取出某一数的后某位

• 判断一个整数的奇偶性

x & 1 = 0 偶数， x & 1 = 1 奇数

• 返回n的最后一位1以及之后的0： lowbit(n)

lowbit 实现方式：

int lowbit(int x)
{
    return x & -x;
}

按位或 |

0 | 0 = 0, 1 | 0 = 1, 1 | 1 = 1

按位异或 ^

0 ^ 0 = 0, 1 ^ 0 = 1, 1 ^ 1 = 0

值得注意的是，按位异或满足交换律和结合律，因此：

洛谷1496-找筷子

一个非常巧妙的解法

int n;
cin >> n;
int ans = 0;
for (int i = 0; i < n; i ++)
{
    int tmp;
    cin >> tmp;
    ans = ans ^ tmp;
}
cout << ans << endl;

取反 ~

返回n的第k位数字： n >> k + 1

位运算内建函数

int __builtin_ffs(int x);

返回 $x$ 的二进制末尾最后一个 $1$ 的位置，位置的编号从 $1$ 开始（最低位编号为 $1$ ）。当 $x$ 为 $0$ 时返回 $0$

int __builtin_clz(unsigned int x);

返回 $x$ 的二进制的前导 $0$ 的个数。当 $x$ 为 $0$ 时，结果未定义 ($ub$)。

int __builtin_ctz(unsigned int x);

返回 $x$ 的二进制末尾连续 $0$ 的个数。当 $x$ 为 $0$ 时，结果未定义 ($ub$)。

int __builtin_clrsb(int x);

当 $x$ 的符号位为 $0$ 时返回 $x$ 的二进制的前导 $0$ 的个数减一，否则返回 $x$ 的二进制的前导 $1$ 的个数减一。

int __builtin_popcount(unsigned int x);

返回 $x$ 的二进制中 $1$ 的个数。