企业官网建设流程全解析

看到 P14970 这道题第一眼，我是有点懵的。GTOI-2A 的第一题，名字叫“睡眠质量”，乍一看以为是模拟题或者贪心题，结果读了半天题面，发现核心就一句话：给你一个非负整数 (n)，求 (n \oplus (n+1)) 的二进制中 1 的个数。换句话说，这道题就是在考“相邻两个数异或之后长什么样”。如果你和我一样，第一反应是直接算一遍二进制、数 1，那当然也能做，但这题真正的价值在于那个非常经典的位运算结论：(n \oplus (n+1)) 的二进制一定是一串连续的 1。这篇题解我会从打表找规律开始，把推导过程、三种代码实现、边界坑和前缀和变形全部讲透，适合刚接触位运算的选手，也适合想巩固二进制敏感度的老手。

1. 题目速览与突破口：看到“相邻异或”先别急着写循环

1.1 一句话讲清这题在问什么

题面本身不复杂。假设第 (n) 天的“睡眠质量”定义为：

[ f(n)=\mathrm{popcount}(n \oplus (n+1)) ]

其中 (\oplus) 是按位异或，(\mathrm{popcount}) 是二进制中 1 的个数。题目会给一个 (n)，范围大概在 (0 \le n < 2^{30}) 左右，让你输出 (f(n))。

很多同学看到“睡眠质量”这个名字，会下意识往 DP 或者什么奇怪的状态转移上想。其实没有。出题人起这个名字多半只是为了让你放松警惕，真正的考点就是二进制观察力。我比赛的时候先花了三分钟确认题目意思，然后又花了两分钟在草稿纸上列了 (n=0) 到 (n=15) 的数据，最后发现规律极其明显，直接一个公式就过了。

1.2 为什么暴力能过却不应直接暴力

你可能觉得：(n) 最大才 (2^{30})，那 (n \oplus (n+1)) 最大也就 (2^{31}-1)，直接用一个循环数 1 不是也可以吗？

理论上可以，但这样做有两个问题。第一，如果题目改成多组询问，比如 (10^5) 组，每组都从最低位循环到最高位，虽然 31 次也不算多，可这已经偏离了出题人想考察的东西。第二，也是更重要的，这类题一旦你不会那个结论，就很容易在边界数据上踩坑。比如 (n = 2^{30}-1) 时，(n+1=2^{30})，两者异或结果是 (2^{31}-1)，有 31 个 1，这个还好；但如果你用int存 (n+1)，在某些语言里直接就溢出了。所以一个稳定的解题思路应该是：先把规律推出来，再用 O(1) 公式计算，既能避免溢出，又能适应更大的数据范围。

2. 核心结论：n⊕(n+1) 的二进制永远是一串连续的 1

2.1 打表找规律：从 n=0 到 n=15 的数据

不要怕麻烦，碰到位运算题，先打表永远是性价比最高的侦察手段。下面是 (n=0) 到 (n=15) 的二进制展开和异或结果：

这个表格一列出来，规律已经呼之欲出了：(n \oplus (n+1)) 的结果，永远是从最低位开始的连续若干个 1，没有 0 混在中间。具体有几个 1，取决于 n 的二进制末尾有多少个连续的 1。

2.2 用“低位连续 1”解释规律的本质

为什么会有这个规律？举个具体例子，设 (n=11)，二进制是1011。它从最低位往上看，有 2 个连续的 1（第 0 位和第 1 位都是 1），第 2 位是 0。那么 (n+1=12)，二进制是1100。加 1 的过程相当于把末尾连续的一串 1 全部进位变成 0，再进位到前面最近的 0 上，把这个 0 变成 1。

于是我们对比一下：

n = 1 0 1 1 n+1 = 1 1 0 0 xor = 0 1 1 1

异或结果里有 3 个 1，这个 3 恰好等于 n 末尾连续 1 的个数（2）再加 1。换句话说，(n+1) 的二进制最低位那个 1 所在的位置，决定了异或结果里连续 1 的长度。这个位置通常用lowbit(n+1)找，也就是 ((n+1) & (-(n+1)))，而它的幂指数就是答案减 1。

3. 完整推导与答案公式：v2(n+1)+1 是怎么来的

3.1 代数推导：把二进制写成同余形式

如果只停留在“看表得出规律”的阶段，比赛时勉强够用，但写题解还是要把背后的数学讲清楚。设 (n) 的二进制从低位开始连续的 1 的个数为 (k)，也就是说：

[ n \equiv 2^k - 1 \pmod{2^{k+1}} ]

这句话的意思是：二进制下 n 的最低 (k) 位全是 1，第 (k) 位是 0。这正好对应“末尾有 k 个连续 1”。

那么 (n+1) 就满足：

[ n+1 \equiv 2^k \pmod{2^{k+1}} ]

换句话说，加 1 之后，原来那 (k) 个 1 全部变成 0，第 (k) 位从 0 变成 1。更高位完全不变。所以两个数在第 0 位到第 (k) 位上完全不同，从第 (k+1) 位开始完全相同。

逐位异或之后，结果就是：

[ n \oplus (n+1) = 2^{k+1} - 1 ]

这个数的二进制自然是 (k+1) 个 1。因此答案就是 (k+1)。

3.2 三个等价视角：lowbit、ctz、连续 1

很多题解会把答案写成：

[ f(n)=\mathrm{ctz}(n+1)+1 ]

其中 (\mathrm{ctz}) 是count trailing zeros，也就是计算一个数二进制末尾有多少个 0。为什么是ctz(n+1)？因为 (n+1) 末尾的 0 恰好就是原来 n 末尾那段连续的 1 进位后留下的 0 的个数。

举三个常见等价表述：

1. 连续 1 视角：看 n 的二进制末尾有几个连续 1，答案就是那个数量加 1。
2. Ctz 视角：看 n+1 末尾有几个连续 0，答案就是那个数量加 1。
3. Lowbit 视角：令 (L = (n+1) & (-(n+1)))，那么答案解析 (L) 的幂次加 1，也就是 (\log_2 L + 1)。

这三个视角本质是同一个东西。做题时哪个方便用哪个。

3.3 为什么不直接用 popcount(n⊕(n+1))

当然，最朴素的写法就是先把 (n \oplus (n+1)) 算出来，再数 1。这个写法本身没错，而且只要用long long，对于 (n<2^{30}) 甚至 (n<2^{60}) 都能写。但从算法学习的角度，知道“异或结果是一串连续 1”能帮你省去很多无谓的计算，也更容易推广。

比如后面第 6 节要讲的前缀和问题，如果只会傻傻地每个数算 popcount，做不了大数据；但如果你知道 (f(n)=\mathrm{ctz}(n+1)+1)，求和就变成了一个简单的整除分块问题。所以这题真正的价值不在于“怎么数 1”，而在于帮你建立“异或 + 进位”的直觉。

4. 代码实现：三种写法的取舍与避坑

4.1 方案一：GCC 内建函数 __builtin_ctz

GCC 和 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)，那么 (n+1=2^{30})，还在int范围内；但如果题目数据稍微改大一点，比如 (n=2^{31}-1)，int的 (n+1) 就溢出变成负数，__builtin_ctz拿到负数时行为是未定义的。用unsigned int或者long long能彻底规避这个问题。

4.2 方案二：lowbit 循环，不依赖编译器扩展

有些 OJ 环境不保证支持__builtin_ctz，或者你想让自己的代码更“标准”，那可以用 lowbit 手写。lowbit 本身可以用位运算快速得到最低位的 1：

long long solve(long long n) { long long x = n + 1; int cnt = 0; while (x % 2 == 0) { x /= 2; cnt++; } return cnt + 1; }

这其实就是不断去掉末尾的 0，数出 (n+1) 末尾 0 的个数。效率也不差，因为最多循环 31 次或者 63 次，完全够用。如果你不想用除法，也可以写成while ((x & 1) == 0)，然后x >>= 1，语义完全一样，而且更贴近位运算的风格。

这个方案的优点是零扩展依赖，适合搬来搬去；缺点是写起来比内建函数啰嗦一点。不过比赛时我通常还是更喜欢__builtin_ctz，毕竟一行搞定。

4.3 方案三：Python 一行流，大整数也不怕

Python 写这类题几乎是最省心的。因为 Python 的整数是无限精度的，n+1不会溢出，而且bin可以直接把整数转成二进制字符串，然后count("1")数 1：

f = 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 复杂度对比与选型建议

说实话，单点查询时四种写法差距可以忽略不计。真正要花心思的不是代码，而是能不能一眼看出 (n \oplus (n+1)) 只包含连续 1。如果你能独立把第 2 节那个表推出来，代码怎么写都行。

5. 实战排错：这些坑我全踩过

5.1 错误一：n=0 时直接调用 __builtin_ctz(n)

有同学拿到公式后很兴奋，直接写：

int ans = __builtin_ctz(n) + 1; // 错！

这个写法错在哪？__builtin_ctz(0)是未定义行为，因为 0 的末尾有无数个 0。而我们真正需要的是__builtin_ctz(n + 1)，因为 (n+1 \ge 1)，永远有定义。

所以一个稳定的记忆点就是：答案不是看 n 末尾 0 的个数，而是看 n+1 末尾 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，这显然不是我们要的答案。我的经验是，碰到这种函数先在小数据上验证一下：n=0时答案必须是 1，n=1时答案必须是 2。如果这两个用例都过不了，说明函数用错了。

5.3 错误三：用 int 存 n+1 导致溢出

题目给的是 (0 \le n < 2^{30})，乍一看int存 (n+1) 是没问题的，因为 (2^{30}) 远小于INT_MAX。但如果你遇到的是改编题，限制变成 (n \le 2^{31}-1)，那么 (n+1 = 2^{31}) 就爆了int。更隐蔽的是，某些比赛喜欢让 (n) 达到 (10^{18})，这时你必须用long long或unsigned long long。

我在本地测试时就吃过这个亏，写了一版int版本，样例全过，结果交上去 RE。后来把所有涉及n+1的变量全部改成unsigned long long，问题立刻消失。位运算题里的“+1”往往比你想的更危险，因为它会触发进位链。

5.4 边界测试用例清单

这里列一组可以拿来验证代码的数据，记得在提交前至少过一遍：

尤其是 (2^{30}-1) 这类边界，如果答案不是 31，说明你的进位链理解出了问题。这类数据既不复杂又能精准命中实现错误，强烈建议写进自己的模板里。

6. 延伸：如果题目改成求前缀和

6.1 从单点查询变成区间求和

很多比赛不会只考一个孤立的结论，而是会把结论嵌入到一个更大的问题里。比如题目改成：

[ S(n) = \sum_{i=1}^{n} \mathrm{popcount}(i \oplus (i+1)) ]

(n) 可以大到 (10^{18})。这时你再逐项调用bit_count()就彻底不行了，必须回到我们第 3 节的结论：

[ \mathrm{popcount}(i \oplus (i+1)) = \mathrm{ctz}(i+1) + 1 ]

所以：

[ S(n) = \sum_{i=1}^{n} \Big( \mathrm{ctz}(i+1) + 1 \Big) = n + \sum_{j=2}^{n+1} \mathrm{ctz}(j) ]

6.2 用按位贡献拆出 O(log n) 公式

怎么快速求 (\sum_{j=2}^{n+1} \mathrm{ctz}(j))？这里有一个常用技巧：按指数统计个数。

(\mathrm{ctz}(j) \ge k) 当且仅当 (j) 是 (2^k) 的倍数。于是：

[ \sum_{j=2}^{n+1} \mathrm{ctz}(j) = \sum_{k=1}^{\infty} \left\lfloor \frac{n+1}{2^k} \right\rfloor ]

这个式子的意思是：先统计 2 的倍数贡献 1 个指数，再统计 4 的倍数贡献 1 个指数，以此类推。因为一个数如果含有因子 (2^t)，它会在 (k=1, 2, ..., t) 这 (t) 层各被统计一次，正好等于 (\mathrm{ctz})。

于是前缀和公式变成：

[ S(n) = n + \sum_{k=1}^{\lfloor \log_2(n+1) \rfloor} \left\lfloor \frac{n+1}{2^k} \right\rfloor ]

这个式子可以 (O(\log n)) 计算，比单点 O(1) 还快不了多少，但思路完全不同。核心就是“把每个数的质因子 2 贡献拆开统计”，这是位运算求和题里最常见的套路之一。

6.3 类似的经典变形与刷题建议

这类“利用二进制结构快速求和”的题目其实非常多。比如：

1. 求 (\sum_{i=1}^{n} \mathrm{lowbit}(i))
2. 求 (\sum_{i=1}^{n} \mathrm{popcount}(i))
3. 求 1 到 n 里所有数的异或和

它们的共同点都是先打表找到模式，再按照位或者按照进制拆贡献。如果你能独立把第 2 节的表推出来并总结出 (n \oplus (n+1)) 的性质，那么上面这些变体基本上都是同样的套路。我自己刷题的习惯是：拿到位运算题，先花两分钟列 0 到 15 的二进制表，再写代码。这个习惯救过我很多次，比任何高级数据结构都管用。

最后再说几句

这道题本身是个典型的 Div2 A 题，谈不上难，但它把“相邻异或”这个非常常见的二进制模式考得很透彻。我自己在做这道题的时候，最大的收获不是记住 (f(n)=\mathrm{ctz}(n+1)+1) 这个公式，而是重新复习了一遍进位链的视觉想象：(n) 末尾 1 越多，加 1 的时候进位就越长，异或结果里连续 1 也就越长。下次你再看到任何“异或 + 加一”的式子，都应该立刻联想到这个画面。

另外，关于代码实现，我强烈建议你把自己常用的那个版本收进模板，无论是__builtin_ctz还是 lowbit 循环都行，但一定要记得在 (n=0)、(n=2^k-1) 这些边界上自测一遍。这些小细节才是真实比赛里拉开差距的地方，共勉。