二进制
二进制（\(Binary System\)）是一种以 \(2\) 为基数的数制，只使用两个数字符号：\(0\) 和 \(1\)， 每个数字称为一个比特（\(Bit\)，\(Binary digit\)的缩写），是最基本的数位系统之一，其发现者是莱布尼茨。
位（\(bit\)）：二进制的最小单位，取值只有 \(0\) 或 \(1\)。
二进制与十进制的转换
十进制转二进制
公式化表述为对给定 \(x\ge 0\)，构造比特 \(b_i\)：
\(b_i=\left\lfloor \frac{x}{2^i} \right\rfloor \bmod 2,\quad x=\sum_{i\ge 0}b_i 2^i\)
实现思路
- 使用短除法，不断除以 \(2\)，记录余数，倒序读出。
- 利用 \(STL\) 中的 \(bitset\)。
实现代码
// 方法1
string convert(int x)
{
string ans;
while (x)
{
ans.push_back('0' + (x & 1));
x >>= 1;
}
reverse(ans.begin(), ans.end());
return ans;
}
// 方法2
cout << bitset<32>(123456) << endl;注：代码中使用的为 \(int\)，可根据场景随时切换其他更大的变量或者无符号变量。
二进制转十进制
公式化表述为设基数 \(B = 2\)，任意长度为 \(m\) 的 \(01\) 串，表示的值为：
\((b_{m-1}\dots b_0)_2 =\sum_{i=0}^{m-1} b_i \cdot 2^i,\quad b_i\in\{0,1\}\)
实现思路
- 遍历二进制 \(01\) 串，累加每一位的位权。
- 利用 \(STL\) 中的 \(bitset\)。
实现代码
// 方法1.1
ull convert1(string s)
{
ull ans = 0;
for (char c : s)
ans = (ans << 1ull) + (c - '0');
return ans;
}
// 方法1.2
ull convert2(string s)
{
reverse(s.begin(), s.end());
ull ans = 0;
for (ull i = 0; i < s.size(); ++i)
if (s[i] - '0')
ans += 1ull << i;
return ans;
}
// 方法2
bitset<64> bit(s);
ull x = bit.to_ullong();注：代码中使用的为 \(usigned\) \(long\) \(long\) 类型，可根据场景随时切换其他整形变量；\(bitset\) 的类型转换方法只有无符号类型。
原码、反码、补码
为了便于运算，带符号的机器数可采用原码、反码、补码等不同的编码方法，机器上的这些编码方法称为码制。
原码：原码是最直观的表示方法，它直接用二进制数表示一个数，包括正负号。在原码中，最高位（最左边的位）是符号位，\(0\) 表示正数，\(1\) 表示负数。其余位表示数值本身。原码是人脑最容易理解和计算的表示方式。
反码：反码主要用于表示负数。对于正数，其反码与其原码相同。对于负数，其反码是将原码除符号位外的所有位取反（\(0\) 变 \(1\)，\(1\) 变 \(0\)）。
补码：补码是计算机中最常用的表示方法，用于进行二进制加法运算。对于正数，其补码与其原码相同。对于负数，其补码是其反码加 \(1\)。补码的一个重要特性是，任何数的补码加上该数本身，结果总是 \(0\)。补码的使用可以简化计算机中的算术运算，因为加法和减法可以统一为加法运算。当进行减法运算时，可以将减数的补码与被减数相加，从而得到结果。
位运算符与优先级
| 运算符 | 含义 | 优先级 |
|---|---|---|
~ | 按位取反 | \(1\) |
& | 按位与 | \(3\) |
^ | 按位异或 | \(4\) |
| | 按位或 | \(5\) |
<< | 左移 | \(2\) |
>> | 右移 | \(2\) |
上面的数字只是在这几个位运算符之间的相对顺序，仅用于这六个运算符之间的比较，与其他运算符的全局优先级无关。
按位取反
定义：对参与位运算的数值的二进制位进行”取反”运算。
运算规则：
以八位二进制举例。
~1 = 1111 1110
~0 = 1111 1111总结：将 \(0\) 变 \(1\)，\(1\) 变 \(0\)。
按位与
定义：对参与位运算的数值的二进制位进行”与”运算。
运算规则：
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1总结：只有两位同时为 \(1\) 时，结果才为 \(1\) ，否则结果为 \(0\)。
注意：负数按补码形式参与按位与运算。
按位或
定义：对参与位运算的数值的二进制位进行”与”运算。
运算规则：
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1总结：只要有一个为 \(1\)，其值为 \(1\)。
注意：负数按补码形式参与按位或运算。
按位异或
定义：对参与位运算的数值的二进制位进行”异或”运算。
异或也叫半加运算，其运算法则相当于不带进位的二进制加法：这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。
运算规则：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0总结：相同为 \(0\)，不同为 \(1\)。
性质：
- 交换律：\(a \oplus b = b \oplus a\)
- 结合律： \((a \oplus b) \oplus c == a \oplus (b \oplus c)\)
- 对于任何数 \(x\)，都有 \(x \oplus x = 0\)，\(x \oplus 0 = x\)
左移
定义：将一个运算对象的各二进制位全部左移若干位，高位丢弃，低位补 \(0\)。
右移
定义：将一个数的各二进制位全部右移若干位，高位补 \(0\) 或补符号位，右边丢弃。
关于右移：
- 无符号右移逻辑右移（高位补 \(0\)）。
- 有符号右移在 \(C++\) 中对负数实现相关（大多数编译器做算术右移，高位补符号位）。
建议：位运算尽量用无符号类型（\(unsigned\)）。
位运算常用技巧
判断奇偶
在数值的二进制表述中，最低位（第 \(0\) 位，既 \(bit0\)）位权为：\(2 ^ 0 = 1\)，其余位权都 \(> 1\)，由此可知 \(bit0\) 直接决定数值的奇偶性：当 \(bit0\) 为 \(0\) 时数值为偶数；为 \(1\) 时数值为奇数。
实现代码
if (x & 1u)
cout << "odd" << endl;
else
cout << "even" << endl;将指定位变为 \(0\)
只需构造 “保留位 \(= 1\)、清零位 \(= 0\)” 的掩码 \(mask\)，然后 \(x \mathrel{\&}= \mathrm{mask}\)。
实现代码
// 将第 k 位变为 0
x &= ~(1u << k);
// 将区间 [l, r] 变为 0
x &= ~(((1u << (r - l + 1u)) - 1u) << l);将指定位变为 \(1\)
只需将需要变为 \(1\) 的目标位的掩码或进去即可。
实现代码
// 将第 k 位变为 1
x |= (1u << k);
// 将区间 [l, r] 变为 1
x |= ((1u << (r - l + 1u)) - 1u) << l;翻转指定位
只需将需要翻转的目标位的掩码异或进去即可。
实现代码
x ^= (1u << k);判断指定位是否为 \(1\)
常见于状态压缩、标志位判断、筛选子集等。
构造一个只在第 \(k\) 位为 \(1\) 的掩码 \(M = (1u << k)\)。
- 若 \(x\) 的第 \(k\) 位是 \(1\)，那么 \(x \text{ & } M\) 的结果正好就是 \(M\)（非 \(0\)）。
- 若该位是 \(0\)，那么 \(x \text{ & } M\) 的结果为 \(0\)。
实现代码
if (x >> k & 1u)
cout << "YES" << endl;
else
cout << "NO" << endl;交换两个数字
主要利用异或的三个性质：
- 交换律：\(a \oplus b = b \oplus a\)
- 结合律： \((a \oplus b) \oplus c == a \oplus (b \oplus c)\)
- 对于任何数 \(x\)，都有 \(x \oplus x = 0\)，\(x \oplus 0 = x\)
实现代码
a = a ^ b;
b = a ^ b;
a = a ^ b;代数推导
设初值为 \((a, b)\)：
- \(a = a \oplus b\)
此时 \(a\) 里装的是 \((\)原\(a \oplus\) 原\(b\)\()\)，\(b\) 还等于 原\(b\)。 - \(b = b \oplus a\)
代入：\(b =\) 原\(b \oplus\) \((\)原\(a \oplus\) 原\(b\)\()\) \(=\) 原\(a\)（因为 \(x \oplus x = 0\)，剩下 原\(a\)）。 - \(a = a \oplus b\)
代入：\(a =\) \((\)原\(a \oplus\) 原\(b\)\()\) \(\oplus\) 原\(a =\) 原\(b\)。
交换完成，得到 \((a, b) =\) \((\)原\(b\), 原\(a)\)。
只有一个出现奇数次的数字
题目链接
题目描述
给定一个非空数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。需设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
思路
利用异或性质 \(a \oplus a=0\), \(a \oplus 0=a\) 。把所有数按位异或起来，偶数次的都会抵消掉，只剩那个奇数次的。
关键代码
class Solution
{
public:
int singleNumber(vector<int> &nums)
{
int ans = 0;
for (auto x : nums)
ans ^= x;
return ans;
}
};有两个出现奇数次的数字
题目链接
260. 只出现一次的数字 III – 力扣（LeetCode）
题目描述
给定一个非空数组，除了两个元素只出现一次以外，其余每个元素均出现两次。找出那两个出现了一次的元素。需设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
思路
数组里恰有两个数出现奇数次，记为 \(u\) 与 \(v\)，其余数都出现偶数次。
- 整体异或：\(X = u \oplus v\)。如果 \(u != v\)，那么 \(X != 0\)，它在某个比特位上为 \(1\)，说明 \(u\) 与 \(v\) 在那一位的取值不同。
- 用 \(lowbit\) 把两类分开，取 \(t = X \text{&} -X\)（最低位 \(1\) 的掩码）。这位在 \(u\) 和 \(v\) 中必然一个为 \(1\)、一个为 \(0\)。把所有数按 \(t\) 这一位是否为 \(1\) 分成两组，并各自异或：
- 组 \(B\)（与 \(t\) 按位与为 \(0\)）最终得到另一个奇数次元素。
- 两组里其他出现偶数次的数都会在各自组内抵消。
组 \(A\)（与 \(t\) 按位与不为 \(0\)）最终得到其中一个奇数次元素；
关键代码
class Solution
{
public:
vector<int> singleNumber(vector<int> &nums)
{
long long x = 0;
for (auto val : nums)
x ^= val;
long long cnt = x & -x;
long long y = 0;
for (auto val : nums)
if (val & cnt)
y ^= val;
return {int(x ^ y), int(y)};
}
};取最低位的 1（lowbit）
既仅保留最右侧的那一位 \(1\)：\(x \mathrel{\&} -x\)（补码语义），最常用在树状数组中。
实现代码
int lowbit(int x)
{
return x & -x;
}重要结论
关于 \(lowbit\) 有一个重要结论，既 \(lowbit(x)\) 必然是 \(x\) 的因子。
结论证明
设正整数 \(x\) 的二进制表示为：\(x = 2^{a₁} + 2^{a₂} + … + 2^{a_k}\)，其中 \(a₁ < a₂ < … < a_k\)。
要证明 \(2^{a₁}\) 是 \(x\) 的因子，只需证明 \(x\) 能被 \(2^{a₁}\) 整除，即 \(x / 2^{a₁}\) 为整数。
提取公因子，将 \(x\) 表示为：\(x = 2^{a₁} (1 + 2^{a₂-a₁} + 2^{a₃-a₁} + … + 2^{a_k-a₁})\)。
令 \(m = 1 + 2^{a₂-a₁} + … + 2^{a_k-a₁}\)，则 \(x = 2^{a₁}·m\)。
因此，\(x / 2^{a₁} = m\) 为整数，即 \(2^{a₁}\) 整除 \(x\)。
\(lowbit(x) = 2^{a₁}\) 是 \(x\) 的因子。
通过以上可引出另外一个重要结论。
令 \(2 ^ t = lowbit(x)\)，此时 \(x = 2 ^ t · m\)，记 \(L = lowbit(x) = 2^t\)。
做一步操作 \(x\leftarrow x+L\)：
\(x+L=(m+1)\cdot 2^t\)
因为 \(m\) 是奇数，\(m+1\) 至少含一个 \(2\)，所以二进制尾随 \(0\) 的个数 \(v_2\) 至少增加 \(1\)；换言之，每加一次 \(lowbit\)，\(x\) 至少“多一个 \(2\) 的因子”。
把这个过程投影到“奇数部分”上更直观：令
\(g(m)=\frac{m+1}{2^{v_2(m+1)}}\quad(\text{把 }m+1\text{ 中的 2 都除掉，得到下一个奇数}).\)
当你反复执行 \(x\leftarrow x+lowbit(x)\) 时，奇数部分就按
\(m\mapsto\ g(m)\ \mapsto\ g(g(m))\ \mapsto\ \cdots\)
演化。对所有奇数 \(m\ge 3\)，有 \(g(m)\le \frac{m+1}{2}<m\)，所以这条奇数序列严格下降，必然在有限步内下降到 \(1\)。
结论：不停做 \(x\leftarrow x+lowbit(x)\)，会在有限步内把 \(x\) 变成某个 \(2\) 的幂（因为奇数部分最终变成 \(1\)）。
例题
题目链接
https://codeforces.com/gym/105977/problem/J
题目描述
给定 \(n\) \((\le 10^{12})\)。你可以在不超过 \(100\) 次的操作内，把它变成一个完全平方数。每次操作：选一个当前 \(n\) 的正因子 \(x\)（且所有选过的 \(x\) 彼此不同），令 \(n\gets n+x\)。整个过程 \(n\) 不得超过 \(10^{18}\)。
思路
- 若 \(n\) 已是完全平方数，直接输出 \(0\)。
- 否则循环做：\(x += lowbit(x)\)，当 \(n\) 变成 \(2\) 的幂时停下来。
- 此时 \(n=2^k\)。若 \(k\) 是偶数，\(n\) 已是完全平方数；若 \(k\) 是奇数，再进行一次操作。此时指数为偶数，得到 \(n=2^{2t}\) 是完全平方数。
关键代码
ull lowbit(ull x)
{
return x & -x;
}
void miyan()
{
ull x;
cin >> x;
if (ull(sqrtl(x)) * ull(sqrtl(x)) == x)
{
cout << 0 << endl;
return;
}
vector<ull> ans;
while (lowbit(x) != x)
{
ans.push_back(lowbit(x));
x += lowbit(x);
}
int cnt = log2(x);
if (cnt & 1u)
{
ans.push_back(x);
x *= 2;
}
cout << ans.size() << endl;
for (auto x : ans)
cout << x << ' ';
cout << endl;
}是否为 \(2\) 的幂
用于判断是否只有一个 \(1\)，常见于分块、对齐、位集优化。
例题
https://leetcode.cn/problems/power-of-two
实现代码
// 方法 1
if (x > 0 && lowbit(x) == x)
cout << "YES" << endl;
// 方法 2
if (x > 0 && (x & (x - 1)) == 0)
cout << "YES" << endl;注意：\(x \leq 0\) 要排除。
\(1\) 的个数
在状压 \(DP\)/组合计数里很常见。
常用解法
- 使用 \((x \text{>>} k \text{&} 1)\) 逐位判断。
- 使用 \(lowbit\) 判断，不断减最低 \(1\)。
- 使用内置函数 \(\text{__builtin_popcount(x)} / \text{__builtin_popcountll(x)}\)。
实现代码
// 方法 1
{
ll ans = 0;
for (int i = 0; i <= 62; ++i)
{
if (x >> i & 1u)
++ans;
}
cout << ans << endl;
}
// 方法 2
{
ll ans = 0;
while (x)
{
++ans;
x -= lowbit(x);
}
cout << ans << endl;
}
// 方法 3
cout << __builtin_popcountll(x) << endl;前缀异或与区间异或
定义
构造前缀异或 \(p[0]=0\)，\(p[i]=a_1\oplus a_2\oplus\cdots\oplus a_i\)。
区间公式
和前缀和一模一样的用法，但减法换成异或：\( a_l\oplus a_{l+1}\oplus\cdots\oplus a_r \;=\;p[r]\ \oplus\ p[l-1]\)。
为什么成立？
异或满足交换律、结合律，且自反：\(x\oplus x=0、x\oplus 0=x\)。把 \(p[r]\) 展开，与 \(p[l−1]\) 逐项配对，区间外的项两两抵消成 \(0\)，剩下正好是 \([l, r]\)。
例题
题目链接
https://www.51nod.com/Html/Challenge/Problem.html#problemId=2128
题目描述
给定长度为 \(n\) 的数组和 \(m\) 次询问，每次给 \((l,r)\)，输出子数组 \([l,r]\) 的异或值。
思路
用上面的前缀异或。
- 预处理：一次扫描得到 \(p[i]=p[i-1]\oplus a[i] (i=1..n)\)。
- 回答查询：每个 \((l,r)\) 输出 \(p[r]\oplus p[l-1]\)。
关键代码
void miyan()
{
int n, m;
cin >> n;
vector<int> a(n + 1), p(n + 1, 0);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
p[i] = p[i - 1] ^ a[i];
}
cin >> m;
while (m--)
{
int l, r;
cin >> l >> r;
cout << (p[r] ^ p[l - 1]) << endl;
}
}1 ~ n 的异或值
\( f(n)=0\oplus1\oplus\cdots\oplus n\,\mbox{只取决于 }n\bmod 4\,\mbox{，并且恰好是：} \)$$
f(n)=\left\{
\begin{array}{ll}
n, & n\bmod 4=0,\\
1, & n\bmod 4=1,\\
n+1, & n\bmod 4=2,\\
0, & n\bmod 4=3.
\end{array}
\right.
$$
例题
题目链接
https://www.luogu.com.cn/problem/U601307
题目描述
计算区间 [l, r] 元素不进位加法的值，数据范围：\(1≤T≤2×10^5， 1≤l≤r≤10^{18}，r−l≤10^{18}\)。
思路
因为异或就是不进位加法，问题可转换为区间 \([l, r]\) 所有元素的异或值，通过上述结论可通过容斥原理快速求得，既由异或的逆运算就是异或可知：\(xor(l, r) = xor(1, r) \oplus xor(1, l – 1)\)。
关键代码
void miyan()
{
ll l, r;
cin >> l >> r;
auto get = [&](ll x) -> ll
{
ll val = x % 4;
if (!val)
return x;
else if (val == 1)
return 1;
else if (val == 2)
return x + 1;
return 0;
};
cout << (get(r) ^ get(l - 1)) << endl;
}题目推荐
1. https://leetcode.cn/problems/power-of-three
2.https://leetcode.cn/problems/bitwise-and-of-numbers-range
3.https://leetcode.cn/problems/reverse-bits
4.https://leetcode.cn/problems/hamming-distance
