为何总是一串连续1？)
看到 P14970 这道题第一眼我是有点懵的。GTOI-2A 的第一题名字叫“睡眠质量”乍一看以为是模拟题或者贪心题结果读了半天题面发现核心就一句话给你一个非负整数 (n)求 (n \oplus (n1)) 的二进制中 1 的个数。换句话说这道题就是在考“相邻两个数异或之后长什么样”。如果你和我一样第一反应是直接算一遍二进制、数 1那当然也能做但这题真正的价值在于那个非常经典的位运算结论(n \oplus (n1)) 的二进制一定是一串连续的 1。这篇题解我会从打表找规律开始把推导过程、三种代码实现、边界坑和前缀和变形全部讲透适合刚接触位运算的选手也适合想巩固二进制敏感度的老手。1. 题目速览与突破口看到“相邻异或”先别急着写循环1.1 一句话讲清这题在问什么题面本身不复杂。假设第 (n) 天的“睡眠质量”定义为[ f(n)\mathrm{popcount}(n \oplus (n1)) ]其中 (\oplus) 是按位异或(\mathrm{popcount}) 是二进制中 1 的个数。题目会给一个 (n)范围大概在 (0 \le n 2^{30}) 左右让你输出 (f(n))。很多同学看到“睡眠质量”这个名字会下意识往 DP 或者什么奇怪的状态转移上想。其实没有。出题人起这个名字多半只是为了让你放松警惕真正的考点就是二进制观察力。我比赛的时候先花了三分钟确认题目意思然后又花了两分钟在草稿纸上列了 (n0) 到 (n15) 的数据最后发现规律极其明显直接一个公式就过了。1.2 为什么暴力能过却不应直接暴力你可能觉得(n) 最大才 (2^{30})那 (n \oplus (n1)) 最大也就 (2^{31}-1)直接用一个循环数 1 不是也可以吗理论上可以但这样做有两个问题。第一如果题目改成多组询问比如 (10^5) 组每组都从最低位循环到最高位虽然 31 次也不算多可这已经偏离了出题人想考察的东西。第二也是更重要的这类题一旦你不会那个结论就很容易在边界数据上踩坑。比如 (n 2^{30}-1) 时(n12^{30})两者异或结果是 (2^{31}-1)有 31 个 1这个还好但如果你用int存 (n1)在某些语言里直接就溢出了。所以一个稳定的解题思路应该是先把规律推出来再用 O(1) 公式计算既能避免溢出又能适应更大的数据范围。2. 核心结论n⊕(n1) 的二进制永远是一串连续的 12.1 打表找规律从 n0 到 n15 的数据不要怕麻烦碰到位运算题先打表永远是性价比最高的侦察手段。下面是 (n0) 到 (n15) 的二进制展开和异或结果nn 的二进制(n1) 的二进制n⊕(n1)popcount00111111011221011113111001113410010111510111011261101111171111000111148100010011191001101011210101010111111101111001113121100110111131101111011214111011111115111110000111115这个表格一列出来规律已经呼之欲出了(n \oplus (n1)) 的结果永远是从最低位开始的连续若干个 1没有 0 混在中间。具体有几个 1取决于 n 的二进制末尾有多少个连续的 1。2.2 用“低位连续 1”解释规律的本质为什么会有这个规律举个具体例子设 (n11)二进制是1011。它从最低位往上看有 2 个连续的 1第 0 位和第 1 位都是 1第 2 位是 0。那么 (n112)二进制是1100。加 1 的过程相当于把末尾连续的一串 1 全部进位变成 0再进位到前面最近的 0 上把这个 0 变成 1。于是我们对比一下n 1 0 1 1 n1 1 1 0 0 xor 0 1 1 1异或结果里有 3 个 1这个 3 恰好等于 n 末尾连续 1 的个数2再加 1。换句话说(n1) 的二进制最低位那个 1 所在的位置决定了异或结果里连续 1 的长度。这个位置通常用lowbit(n1)找也就是 ((n1) (-(n1)))而它的幂指数就是答案减 1。3. 完整推导与答案公式v2(n1)1 是怎么来的3.1 代数推导把二进制写成同余形式如果只停留在“看表得出规律”的阶段比赛时勉强够用但写题解还是要把背后的数学讲清楚。设 (n) 的二进制从低位开始连续的 1 的个数为 (k)也就是说[ n \equiv 2^k - 1 \pmod{2^{k1}} ]这句话的意思是二进制下 n 的最低 (k) 位全是 1第 (k) 位是 0。这正好对应“末尾有 k 个连续 1”。那么 (n1) 就满足[ n1 \equiv 2^k \pmod{2^{k1}} ]换句话说加 1 之后原来那 (k) 个 1 全部变成 0第 (k) 位从 0 变成 1。更高位完全不变。所以两个数在第 0 位到第 (k) 位上完全不同从第 (k1) 位开始完全相同。逐位异或之后结果就是[ n \oplus (n1) 2^{k1} - 1 ]这个数的二进制自然是 (k1) 个 1。因此答案就是 (k1)。3.2 三个等价视角lowbit、ctz、连续 1很多题解会把答案写成[ f(n)\mathrm{ctz}(n1)1 ]其中 (\mathrm{ctz}) 是count trailing zeros也就是计算一个数二进制末尾有多少个 0。为什么是ctz(n1)因为 (n1) 末尾的 0 恰好就是原来 n 末尾那段连续的 1 进位后留下的 0 的个数。举三个常见等价表述连续 1 视角看 n 的二进制末尾有几个连续 1答案就是那个数量加 1。Ctz 视角看 n1 末尾有几个连续 0答案就是那个数量加 1。Lowbit 视角令 (L (n1) (-(n1)))那么答案解析 (L) 的幂次加 1也就是 (\log_2 L 1)。这三个视角本质是同一个东西。做题时哪个方便用哪个。3.3 为什么不直接用 popcount(n⊕(n1))当然最朴素的写法就是先把 (n \oplus (n1)) 算出来再数 1。这个写法本身没错而且只要用long long对于 (n2^{30}) 甚至 (n2^{60}) 都能写。但从算法学习的角度知道“异或结果是一串连续 1”能帮你省去很多无谓的计算也更容易推广。比如后面第 6 节要讲的前缀和问题如果只会傻傻地每个数算 popcount做不了大数据但如果你知道 (f(n)\mathrm{ctz}(n1)1)求和就变成了一个简单的整除分块问题。所以这题真正的价值不在于“怎么数 1”而在于帮你建立“异或 进位”的直觉。4. 代码实现三种写法的取舍与避坑4.1 方案一GCC 内建函数 __builtin_ctzGCC 和 Clang 都提供了__builtin_ctz作用是返回一个数二进制末尾 0 的个数。对于非负整数它可以直接帮我们算出答案#include bits/stdc.h using namespace std; int solve(unsigned int n) { return __builtin_ctz(n 1) 1; } int main() { int T; cin T; while (T--) { unsigned int n; cin n; cout solve(n) \n; } return 0; }注意这里我用的是unsigned int而不是int。原因很简单如果测试数据里有 (n 2^{30}-1)那么 (n12^{30})还在int范围内但如果题目数据稍微改大一点比如 (n2^{31}-1)int的 (n1) 就溢出变成负数__builtin_ctz拿到负数时行为是未定义的。用unsigned int或者long long能彻底规避这个问题。4.2 方案二lowbit 循环不依赖编译器扩展有些 OJ 环境不保证支持__builtin_ctz或者你想让自己的代码更“标准”那可以用 lowbit 手写。lowbit 本身可以用位运算快速得到最低位的 1long long solve(long long n) { long long x n 1; int cnt 0; while (x % 2 0) { x / 2; cnt; } return cnt 1; }这其实就是不断去掉末尾的 0数出 (n1) 末尾 0 的个数。效率也不差因为最多循环 31 次或者 63 次完全够用。如果你不想用除法也可以写成while ((x 1) 0)然后x 1语义完全一样而且更贴近位运算的风格。这个方案的优点是零扩展依赖适合搬来搬去缺点是写起来比内建函数啰嗦一点。不过比赛时我通常还是更喜欢__builtin_ctz毕竟一行搞定。4.3 方案三Python 一行流大整数也不怕Python 写这类题几乎是最省心的。因为 Python 的整数是无限精度的n1不会溢出而且bin可以直接把整数转成二进制字符串然后count(1)数 1f lambda n: bin(n ^ (n 1)).count(1) # 测试 for n in range(16): print(n, f(n))更优雅一点也可以利用 Python 的int.bit_count()方法f lambda n: (n ^ (n 1)).bit_count()bit_count()是 Python 3.8实际上 3.10 正式加入里提供的方法直接返回一个整数的二进制 1 的个数和 C 的__builtin_popcount对应。如果你在 OJ 上遇到 Python 版本比较新直接用这个方法最简洁。不过要注意bit_count()和__builtin_popcount一样都是 O(位数) 的如果你在做大数据范围的前缀和问题还是要回到公式推导。4.4 复杂度对比与选型建议实现方式代码量时间复杂度依赖适用场景__builtin_ctz1 行O(1)GCC/Clang多数 OJ 首选lowbit 循环3-5 行O(位数)纯 C要求可移植时Pythonbit_count1 行O(位数)Python 3.10快速验证结论Pythonbin().count1 行O(位数)任意 Python通用、最保险说实话单点查询时四种写法差距可以忽略不计。真正要花心思的不是代码而是能不能一眼看出 (n \oplus (n1)) 只包含连续 1。如果你能独立把第 2 节那个表推出来代码怎么写都行。5. 实战排错这些坑我全踩过5.1 错误一n0 时直接调用 __builtin_ctz(n)有同学拿到公式后很兴奋直接写int ans __builtin_ctz(n) 1; // 错这个写法错在哪__builtin_ctz(0)是未定义行为因为 0 的末尾有无数个 0。而我们真正需要的是__builtin_ctz(n 1)因为 (n1 \ge 1)永远有定义。所以一个稳定的记忆点就是答案不是看 n 末尾 0 的个数而是看 n1 末尾 0 的个数。如果你非要从 n 本身出发那就要先找到 n 末尾连续 1 的个数而不是末尾连续 0 的个数。5.2 错误二把 ctz 写成 clz答案直接翻车__builtin_clz是count leading zeros统计前导 0 的个数。有些同学做题做到后面把ctz和clz记混写着写着就成了int ans __builtin_clz(n 1) 1; // 错clz通常和整数位数强相关比如 32 位整数下__builtin_clz(1) 31这显然不是我们要的答案。我的经验是碰到这种函数先在小数据上验证一下n0时答案必须是 1n1时答案必须是 2。如果这两个用例都过不了说明函数用错了。5.3 错误三用 int 存 n1 导致溢出题目给的是 (0 \le n 2^{30})乍一看int存 (n1) 是没问题的因为 (2^{30}) 远小于INT_MAX。但如果你遇到的是改编题限制变成 (n \le 2^{31}-1)那么 (n1 2^{31}) 就爆了int。更隐蔽的是某些比赛喜欢让 (n) 达到 (10^{18})这时你必须用long long或unsigned long long。我在本地测试时就吃过这个亏写了一版int版本样例全过结果交上去 RE。后来把所有涉及n1的变量全部改成unsigned long long问题立刻消失。位运算题里的“1”往往比你想的更危险因为它会触发进位链。5.4 边界测试用例清单这里列一组可以拿来验证代码的数据记得在提交前至少过一遍输入 n预期输出原因01(0 \oplus 1 1)12(1 \oplus 2 3)21(2 \oplus 3 1)33(3 \oplus 4 7)74(7 \oplus 8 15)81(8 \oplus 9 1)155(15 \oplus 16 31)161(16 \oplus 17 1)(2^{30}-1)31二进制全 1 加 1 后进位到底尤其是 (2^{30}-1) 这类边界如果答案不是 31说明你的进位链理解出了问题。这类数据既不复杂又能精准命中实现错误强烈建议写进自己的模板里。6. 延伸如果题目改成求前缀和6.1 从单点查询变成区间求和很多比赛不会只考一个孤立的结论而是会把结论嵌入到一个更大的问题里。比如题目改成[ S(n) \sum_{i1}^{n} \mathrm{popcount}(i \oplus (i1)) ](n) 可以大到 (10^{18})。这时你再逐项调用bit_count()就彻底不行了必须回到我们第 3 节的结论[ \mathrm{popcount}(i \oplus (i1)) \mathrm{ctz}(i1) 1 ]所以[ S(n) \sum_{i1}^{n} \Big( \mathrm{ctz}(i1) 1 \Big) n \sum_{j2}^{n1} \mathrm{ctz}(j) ]6.2 用按位贡献拆出 O(log n) 公式怎么快速求 (\sum_{j2}^{n1} \mathrm{ctz}(j))这里有一个常用技巧按指数统计个数。(\mathrm{ctz}(j) \ge k) 当且仅当 (j) 是 (2^k) 的倍数。于是[ \sum_{j2}^{n1} \mathrm{ctz}(j) \sum_{k1}^{\infty} \left\lfloor \frac{n1}{2^k} \right\rfloor ]这个式子的意思是先统计 2 的倍数贡献 1 个指数再统计 4 的倍数贡献 1 个指数以此类推。因为一个数如果含有因子 (2^t)它会在 (k1, 2, ..., t) 这 (t) 层各被统计一次正好等于 (\mathrm{ctz})。于是前缀和公式变成[ S(n) n \sum_{k1}^{\lfloor \log_2(n1) \rfloor} \left\lfloor \frac{n1}{2^k} \right\rfloor ]这个式子可以 (O(\log n)) 计算比单点 O(1) 还快不了多少但思路完全不同。核心就是“把每个数的质因子 2 贡献拆开统计”这是位运算求和题里最常见的套路之一。6.3 类似的经典变形与刷题建议这类“利用二进制结构快速求和”的题目其实非常多。比如求 (\sum_{i1}^{n} \mathrm{lowbit}(i))求 (\sum_{i1}^{n} \mathrm{popcount}(i))求 1 到 n 里所有数的异或和它们的共同点都是先打表找到模式再按照位或者按照进制拆贡献。如果你能独立把第 2 节的表推出来并总结出 (n \oplus (n1)) 的性质那么上面这些变体基本上都是同样的套路。我自己刷题的习惯是拿到位运算题先花两分钟列 0 到 15 的二进制表再写代码。这个习惯救过我很多次比任何高级数据结构都管用。最后再说几句这道题本身是个典型的 Div2 A 题谈不上难但它把“相邻异或”这个非常常见的二进制模式考得很透彻。我自己在做这道题的时候最大的收获不是记住 (f(n)\mathrm{ctz}(n1)1) 这个公式而是重新复习了一遍进位链的视觉想象(n) 末尾 1 越多加 1 的时候进位就越长异或结果里连续 1 也就越长。下次你再看到任何“异或 加一”的式子都应该立刻联想到这个画面。另外关于代码实现我强烈建议你把自己常用的那个版本收进模板无论是__builtin_ctz还是 lowbit 循环都行但一定要记得在 (n0)、(n2^k-1) 这些边界上自测一遍。这些小细节才是真实比赛里拉开差距的地方共勉。
