位运算拓展
本节目标
在二进制与位运算基础之上，识别逐位统计、公共前缀、移位倍增与编码构造四类进阶模型。
本节只覆盖复试、面试与省赛中可能出现的四类位模型：逐位独立、公共二进制前缀、移位与倍增、编码构造。它不是任意位技巧的入口；遇到未能归入这些模型的问题，应先回到题意、数据范围和基础框架，而不是搜集零散公式。
何时进入拓展
完成二进制与位运算基础后，再学习本节。此前应已经能说明位宽、逐位读取、异或消去与移位各自表示什么；本节只在题目额外要求跨多个数比较、按位统计或构造特殊序列时，才引入新的模型。
题目若只需要清除一个最低位 1、判断单个数的形状或处理固定宽度的逐位读写，仍优先使用基础框架。不要因为题面出现二进制就直接套用拓展方法。
逐位独立
当每个二进制位对答案的贡献互不影响时，可以把一个整数问题拆成若干个“这一位有多少个 1”的问题。统计后再按题意取模或决定答案的该位；前提是进位、相邻位关系和位的位置都不会改变该位的结论。
这和异或消去不同：异或适合偶数次配对抵消，逐位统计适合出现次数遵循统一余数规律的场景。处理负数或题目规定固定宽度时，必须明确逐位遍历的位数和重建结果的补码语义，完整推导留在具体题解中。
公共二进制前缀
对一个连续整数区间做按位与时，只要某一位在区间内曾经从 0 变到 1，该位的结果就会变为 0。因此真正能保留下来的，是区间两端共享的高位二进制前缀；从低位开始变化的部分都不能保留。
常用做法是让两个端点同时右移，直到相等，再把共同前缀移回原来的位置。这里的关键是解释“为什么区间会覆盖变化的低位”，而不是机械记住右移次数。
移位与倍增
不能使用乘、除或模时，可以把除法理解为从大到小尝试减去若干个“除数的二进制倍数”。左移一次表示把一个非负数翻倍；每次选择不超过剩余值的最大倍数，就能像二进制展开一样累积商。
这类题必须先处理符号、绝对值范围和结果边界，再进行倍增。尤其在固定宽度整数中，最小负数的绝对值和最终结果溢出不能靠普通相反数操作想当然地处理；这些推导与语言细节放在题解页中。
编码构造
有些题不要求直接计算一个数，而要求构造相邻对象只改变一位的序列。此时应先验证构造规则是否同时满足“相邻仅一位不同”“覆盖所需数量”和题目要求的起点，再讨论实现。
格雷编码的常见表达 i ^ (i >> 1) 正是在索引的相邻变化中保留这种一位差异。这里关注的是构造不变量，而不是把公式当作可迁移到所有序列题的位技巧。
母题序列
按拓展顺序完成下列四题；每题只承载对应模型的完整证明、边界与代码实现：
- 只出现一次的数字 II（拓展）：逐位统计并按出现次数规律重建答案。
- 数字范围按位与（拓展）：通过共同前缀理解连续区间的按位与。
- 两数相除（拓展）：用移位和倍增模拟除法，并处理符号与边界。
- 格雷编码（拓展）：验证并实现相邻仅一位不同的编码构造。
迁移方向
迁移时先问：各位能否独立统计？连续范围是否只留下公共前缀？操作能否写成二进制倍数的组合？构造是否有可验证的不变量？只有答案明确落在其中一类时，才进入对应模型；否则仍从基础框架重新建模。