从LightOJ 1042题解析位运算：高效寻找二进制1个数相同的下一个数

1. 从一道“简单”题看位运算的思维陷阱如果你刷过一些在线评测系统Online Judge, OJ的题目尤其是像 LightOJ 这样的平台可能会对“1042 - Secret Origins”这道题有印象。乍一看题目名字“秘密起源”有点神秘色彩但点进去一看描述却出奇地简单给定一个正整数 N要求你找出一个大于 N 的最小的正整数 M使得 M 的二进制表示中 1 的个数与 N 的二进制表示中 1 的个数相同。很多人的第一反应是“这还不简单从 N1 开始往上枚举数每个数的二进制中 1 的个数直到找到第一个‘1’的个数和 N 相同的数不就行了” 这个思路完全正确逻辑上也毫无问题。对于小范围的 N比如 N1, 2, 3...这个暴力枚举法瞬间就能得出答案。这也正是这道题被很多人标记为“简单”、“水题”的原因。然而当你真正在 OJ 上提交这个看似无懈可击的枚举代码时迎接你的很可能是一个冷冰冰的“Time Limit Exceeded”超时。为什么因为这道题的输入范围 N 最大可以达到 2^31 - 1约 21 亿。在最坏情况下比如 N 的二进制是011111...111一个 0 后面跟着一串 1那么下一个符合条件 M 的二进制可能是100000...000111...一个 1 后面跟着一串 0再跟一串 1这两个数之间的差值可能达到数亿甚至数十亿的量级。用线性的枚举法时间复杂度是 O(M-N)在极端情况下是不可接受的。这道题的精髓或者说它作为一道“思维题”的价值就在于逼迫你放弃直觉上的暴力解法去深入理解二进制数的结构并利用位运算来高效地、优雅地直接构造出答案 M。它考察的不是你会不会写循环而是你是否真正理解了比特bit层面的操作逻辑。2. 核心问题拆解我们到底在找什么在动手写任何代码之前我们必须把问题理解透彻。题目要求find the smallest integer greater than N, which has the same number of 1 bits in its binary representation.让我们用更直观的方式重新表述一下。假设 N 的二进制表示为b_k b_{k-1} ... b_2 b_1 b_0其中每个 b_i 是 0 或 1并且 b_k 是最高位的 1。设 N 中 1 的个数为popcount(N)population count即二进制中 1 的个数。我们要找的 M 必须满足三个条件M N。popcount(M) popcount(N)。在所有满足条件 1 和 2 的数中M 是最小的。条件 2 意味着我们不能随意增加或减少 1 的数量只能“重新排列”这些 1 的位置。条件 1 和 3 共同决定了这种“重新排列”必须遵循一个最小增量原则。换句话说我们要对 N 的二进制位进行最小的“扰动”在保持 1 的总数不变的前提下得到一个比 N 大的数。那么什么样的“扰动”是最小的呢在十进制里比一个数大的最小数通常是从最低位开始寻找可以“进位”并调整的位置。在二进制里这个逻辑同样适用但我们需要同时考虑 1 的个数守恒。让我们看一个具体的例子设 N 12其二进制为1100popcount 2。比 12 大且 1 的个数为 2 的数有哪些13 (1101, popcount3) 不行14 (1110, popcount3) 不行15 (1111, popcount4) 不行16 (10000, popcount1) 不行17 (10001, popcount2) 终于符合了。答案是 17。从1100到10001这个变化看起来跳跃很大。我们如何系统地找到它关键观察为了使 M N 且尽可能小我们应该尽可能保持 N 的高位不变只调整尽可能低的位。调整的规律是找到一个可以“让位”的 1把它向右移动并且把移动后空出的位以及它右边所有的 1 进行“最紧凑”的排列。更专业的说法是我们需要找到 N 的二进制表示中从右向左扫描第一个出现的“01”模式即一个 0 位紧跟着一个 1 位。然后我们将这个“01”交换成“10”。最后将交换位置右侧即原 1 的右边所有的 1 都“推”到最右边即最低位。为什么是“01”模式因为“01”中的 1 代表一个我们可以向右移动的“资源”一个 1-bit。把它和左边的 0 交换变成“10”我们就得到了一个比原数大的数因为更高位的一个 0 变成了 1。同时为了最小化这个数我们需要把交换后右侧所有的 1 都移到最右边这样保证右侧部分的值最小。3. 算法推导与逐步构造法理解了核心思想后我们可以将寻找 M 的过程分解为一个清晰的、可操作的算法。这个算法不依赖于枚举而是通过几次位运算直接计算出结果。下面我们一步步推导。步骤 1找到最右边的“01”串这里的“01”串指的是从最低位开始向高位扫描找到的第一个形如...01...的位模式。更具体地说是找到第一个为 1 的位设其位置为p并且它紧邻的高一位位置p1是 0。为什么找这个因为这个 1 是我们可以用来“填充”右边 0 位以创造更大数字的“种子”。它左边的 0 位位置p1将成为新的、更高的 1 位从而使数字变大。实际操作中我们可以这样找找到最右边连续的 1 的序列。设c1为这个连续 1 序列中 1 的个数。找到这个连续 1 序列左边紧邻的那个 0 位的位置。设这个 0 位的位置为p从 0 开始计数。 那么p位就是我们要找的“01”模式中的 0p位右边直到某个位置就是连续的 1。步骤 2翻转关键位找到位置p后我们进行以下操作将第p位从 0 设置为 1。这一步保证了新数 M 一定大于 N因为我们在一个更高的位置增加了 1。此时我们多设置了一个 1。为了保持 1 的总数不变我们必须减少一个 1。最直接的方法是将第p位右边原来所有的 1 都清零。设清零前p位右边总共有c1个 1。步骤 3重新安置剩余的 1上一步之后我们得到了一个数它比 N 大但是 1 的个数是popcount(N) 1 - c1。为了将 1 的个数恢复为popcount(N)我们需要在低位补回(c1 - 1)个 1。并且为了使得最终的 M 最小这些补回的 1 必须放在尽可能低的位置即最右边。总结算法流程c0 0。从最低位 (LSB) 开始向高位扫描统计连续的 0 的个数直到遇到第一个 1。记录此时连续的 0 的个数为c0不这里需要调整。更准确的做法是找到最右边连续的 1。找到最右边非拖尾的 0 位。实际上更好的描述是c1 从最低位开始连续 1 的个数。pc1的位置。即从右数第c1个 1 再左边一位的位置。例如 N 10011100156。最右边两位是00然后遇到1。连续 1 的个数c1 3位置 b2, b3, b4 是 1。p就是 b4 再左边一位即 b5。检查 b5在原始数中是 0。将第p位设为 1。将第p位右边的所有位清零。在清零区域的最右边即从第 0 位开始放入(c1 - 1)个 1。举例说明N 156(1001 1100)二进制:1 0 0 1 1 1 0 0(从高位b7到低位b0)从b0开始扫描: b00, b10, b21, b31, b41。所以最右边连续1的个数c1 3(b2, b3, b4)。这串连续1的左边一位是 b5。p 5。检查 b5原始是 0。完美。将 b5 设为 1。数变为1 0 1 1 1 1 0 0。这一步使数字变大了。将 b4, b3, b2, b1, b0 全部清零。数变为1 0 1 0 0 0 0 0(即 12832160)。此时 1 的个数是 2。我们需要总 1 个数和原来一样。原 N (10011100) 有 4 个 1。目前我们有 2 个 1。需要补回c1 - 1 2个 1。将这 2 个 1 放在最低位即 b1 和 b0 设为 1。最终 M 1 0 1 0 0 0 1 1 128 32 2 1 163。 验证163 156且10100011有 4 个 1符合条件。可以验证 157-162 之间的数都不满足条件。4. 位运算实现与代码解析理论清晰后用代码实现就变得直接了当。我们将上述算法步骤转化为高效的位操作。以下是用 C 实现的一种经典且清晰的写法我会逐行加上注释。#include bits/stdc.h using namespace std; int main() { int T, caseNo 1; scanf(%d, T); // 读取测试用例数量 while (T--) { unsigned int n; // 使用无符号整数方便位运算 scanf(%u, n); // 步骤 1: 找到最右边连续的1的序列 unsigned int c1 0; unsigned int temp n; // 这个循环计算拖尾的连续1的个数 (c1) while ((temp 1) 1) { // 检查最低位是否为1 c1; temp 1; // 右移一位检查下一位 } // 步骤 2: 找到第一个非拖尾的0的位置 (p) // 此时temp的最低位已经是0。我们需要找到这个0在原始n中的位置。 // 实际上在上面的循环结束后temp的最低位就是我们要找的0。 // 我们需要设置这个位为1。 // 更直接的方法是先构造一个掩码定位到那个0位。 unsigned int p c1; // 连续1的个数也代表了从低位算起第一个0位的位置偏移 // 现在我们要将n的第p位设为1。注意位次从0开始。 // 首先创建一个只有第p位是1的掩码。 unsigned int set_bit 1 p; // 将1左移p位 // 步骤 3: 设置p位为1并清除右边所有的位 unsigned int m n | set_bit; // 将n的第p位设为1 m ~(set_bit - 1); // 清除p位右边的所有位。set_bit-1 会产生p个低位1的掩码取反后与m相与将这些位清零。 // 例如p3, set_bit 0b1000, set_bit-1 0b0111, ~(set_bit-1)0b...11111000 // 步骤 4: 重新插入 (c1 - 1) 个1到最低位 // 我们需要在最低位放入 (c1 - 1) 个1。 // 可以通过 (1 (c1 - 1)) - 1 来得到这样一个掩码。 // 但需要注意 c1 可能为0此时c1-1为负数移位操作是未定义的。需要判断。 if (c1 0) { unsigned int ones_mask (1 (c1 - 1)) - 1; // 产生 (c1-1) 个低位1 m | ones_mask; // 将这些1放到m的最低位 } // 如果c10则意味着n的最低位就是0我们只是将第一个找到的0变成了1右边没有1需要重排m已经是最小答案。 printf(Case %d: %u\n, caseNo, m); } return 0; }代码关键点解析使用unsigned int位运算在无符号整数上进行是最安全、最符合定义的避免了有符号数右移时符号位扩展带来的潜在问题。计算c1while ((temp 1) 1)这个循环巧妙地统计了从最低位开始的连续 1 的个数。temp 1每次右移一位。定位并设置关键位set_bit 1 p创建了一个“灯塔”标识了我们需要翻转的 0 位的位置即第一个非拖尾 0。n | set_bit操作将其设为 1。清除低位~(set_bit - 1)是这段代码的精华之一。set_bit是0...010...01 在位置 p。set_bit - 1就变成了0...001...1从第 0 位到第 p-1 位全是 1。再取反~就得到了1...110...0第 0 位到第 p-1 位是 0其余位是 1。用这个掩码和m相与 ()就精准地将p位右边的所有位清零了。补回 1(1 (c1 - 1)) - 1是另一个经典技巧。1 k得到0...010...01 在位置 k再减 1就得到了0...001...1从第 0 位到第 k-1 位全是 1。这里k c1 - 1所以我们得到了c1 - 1个连续的 1。通过m | ones_mask将它们放到最低位。边界条件处理注意c1可能为 0即 n 的最低位就是 0。此时c1 - 1是 -1对负数进行移位是未定义行为。因此代码中加入了if (c1 0)的判断。当c1 0时算法退化为简单的“找到第一个 0 并置 1”这正是我们期望的例如 N2 (10)答案 M4 (100)。这个算法的时间复杂度是 O(log N)因为它只需要扫描 N 的二进制位若干次常数次与 N 的大小无关只与其二进制位数相关对于 32 位整数最多 32 步。空间复杂度是 O(1)。完美解决了大数据范围下的超时问题。5. 思维扩展与相关位运算技巧解决了 LightOJ 1042我们掌握的不仅仅是一道题的答案而是一类“二进制表示变换”问题的核心思路。这个“找到最右端‘01’模式并重组”的范式可以推广到许多其他场景。变体 1找出小于 N 的最大数且 1 的个数相同这是本题的镜像问题。思路完全对称找到最右边的“10”模式一个 1 后面跟着一个 0将它们交换成“01”然后将这个 1 右边所有的 1 都移动到紧挨着这个 0 的左侧以保证数字尽可能大但小于 N。算法步骤类似先找到最右边连续的 0然后找到其左侧的第一个 1进行翻转和重组。变体 2计算一个整数的二进制中 1 的个数Popcount本题中我们通过循环移位来数连续 1 的个数但更高效的计算总 popcount 的方法有很多内置函数__builtin_popcount(n)(GCC/Clang) 或bitset32(n).count()(C)。Brian Kernighan 算法while (n) { count; n (n-1); }。每次操作n (n-1)会清除 n 二进制表示中最右边的 1。这个算法在 1 的个数较少时非常高效。变体 3判断一个数是否是 2 的幂一个数是 2 的幂当且仅当其二进制表示中只有一位是 1。可以用n 0 (n (n-1)) 0来判断。n (n-1)这个操作在上面 Brian Kernighan 算法里出现过它能清除最右边的 1。如果清除后结果为 0说明原来只有一个 1。变体 4获取最低位的 1Lowest Set Bitlowbit n -n。在补码表示中-n等于~n 1。n -n的结果是一个只有 n 中最低位 1 被保留其余位全是 0 的数。这个技巧在树状数组Fenwick Tree等数据结构中至关重要。回到本题的教训为什么很多人一开始会想到枚举因为对于很多编程初学者或者对问题规模不敏感的解题者来说“枚举”是最直观、最符合第一思维的策略。计算机的速度给了我们“暴力解决”的错觉。但 LightOJ 1042 这道题就是一个很好的警示在算法问题中输入规模Constraints是神圣不可忽视的。它直接决定了哪些算法是可行的哪些是徒劳的。养成读题先看数据范围的习惯能帮你快速判断解法的方向。当看到 N 最大为 2^31 时O(N) 的线性枚举就必须被排除转而思考 O(log N) 或 O(1) 的数学/位运算解法。6. 实战中的调试与边界测试即使算法思路正确实现时也容易踩坑。以下是一些在实现和测试本题时需要注意的点和常见的调试用例边界测试用例 这些是检验你代码鲁棒性的试金石务必逐一测试。N 1(0001): 答案应该是 2 (0010)。检查你的代码是否能处理c11的情况找到p1设置清除低位补回 0 个 1。N 2(0010): 答案应该是 4 (0100)。这是c10的情况最低位是0。你的代码中if (c1 0)的判断是否生效避免了负位移N 3(0011): 答案应该是 5 (0101)。这里有连续的 1 (c12)需要重组。N 7(0111): 这是全 1 片段在尾部且左边是 0 的典型。答案应该是 11 (1011)。c13,p3。N 6(0110): 答案应该是 9 (1001)。注意它的连续 1 不是在最低位开始的。N 最大可表示数 (2^31 - 1)对于 32 位有符号整数这是0x7FFFFFFF二进制 31 个 1。这个数没有“01”模式除了符号位所有位都是1。它的下一个相同 1 的个数是什么实际上对于 32 位无符号整数这个数就是0xFFFFFFFF如果考虑 32 位全1但题目给定范围通常不包括全1。对于0x7FFFFFFF其下一个数需要更多位来表示第32位变为1但题目输入 N 在[1, 2^31-1]所以答案 M 也在 32 位无符号整数范围内且是0xBFFFFFFF吗让我们算一下0x7FFFFFFF(31个1) - 我们需要保持31个1但数字要变大。只能将最高位的0符号位我们视为数据位设为1但这样就有了32个1。所以无解不在32位表示内无法找到一个比0x7FFFFFFF大且只有31个1的数。但题目保证有解说明我们的理解或范围有误。实际上LightOJ 的原题描述中 N 是 32 位正整数但并未明确说明是int还是unsigned int。通常对于0x7FFFFFFF其下一个数是0x8FFFFFFF二进制1000 1111 ...但1的个数变了。这里是一个很好的陷阱。实际上对于二进制为011...111的数其下一个“相同1个数”的数是1011...111的形式即将最左边的1向左移动一位并将剩余的所有1放在最右边。例如0111(7) -1011(11)。对于0x7FFFFFFF答案是0xBFFFFFFF。这需要我们的算法能正确处理p等于最高有效位的情况。在我们的实现中p会等于c131set_bit 1 31在无符号 32 位整数中是合法的即0x80000000。后续操作也能正确进行。这是一个非常重要的测试。调试技巧打印二进制在调试时将关键的中间变量如n,temp,c1,set_bit,m等以二进制形式打印出来是理解算法每一步在做什么的最直观方法。你可以写一个简单的printBinary(unsigned int x)函数。单步跟踪对于复杂的位运算在 IDE 中使用调试器观察变量在每一步按位与、或、移位后的值确保它们符合你的预期。测试驱动不要只依赖样例输入。自己构造上面提到的边界用例以及一些随机数先手动计算答案再用程序验证。注意在 C/C 中对负数进行右移 () 操作是实现定义的可能是逻辑右移补0也可能是算术右移补符号位。这就是为什么在涉及位运算时强烈推荐使用unsigned int类型它的移位行为是明确且一致的逻辑移位。7. 从解题到精通位运算的思维模式LightOJ 1042 的价值远超过一道普通的编程题。它是一次很好的思维训练教会我们如何跳出“模拟过程”的惯性思维转而从“数据表示”这里是二进制表示的本质属性出发去寻找规律和高效算法。这种思维模式在解决许多计算机科学问题时都至关重要。当你面对一个看似需要遍历或模拟的问题时可以问自己以下几个问题数据的本质是什么在这个问题里数据的本质是二进制位串和其中 1 的个数。目标状态和当前状态的区别在哪里目标是找到一个更大的、但 1 的个数相同的位串。这意味着我们需要对位串进行一个“最小”的重新排列。这种“最小”的变化在结构上对应什么操作这引导我们发现了“找到最右边‘01’并重组”的规律。如何用计算机的基本操作位运算高效地实现这个结构变化这催生了我们上面那套c1,p,set_bit, 掩码清零低位补 1 的精妙操作。掌握这种思维你就能举一反三。例如在组合数学中求一个集合的下一个字典序排列或下一个具有相同元素个数的子集都有类似的“从右向左扫描找到第一个可增加的位置进行调整然后对右侧部分进行最小化重排”的算法例如 C STL 中的next_permutation和next_combination原理。位运算因其直接操作硬件的特性是执行这类算法最高效的工具。所以下次再遇到类似“寻找满足某特性的下一个数”的问题不妨先想想它的二进制或其他进制表示看看能否找到一种确定性的、无需遍历的构造方法。LightOJ 1042 就是一个完美的起点。