位运算实战：从OJ题“Secret Origins”解析二进制“下一个排列”算法

1. 从一道OJ题看位运算的“下一个排列”如果你刷过一些在线评测系统Online Judge, OJ的题目尤其是像LightOJ这样以算法竞赛题目闻名的平台可能会对“1042 - Secret Origins”这个题号有印象。乍一看标题“秘密起源”有点故弄玄虚但它的核心其实是一个经典的、在面试和实际工程中都可能遇到的位运算问题给定一个正整数找出其二进制表示中“1”的个数相同且比它大的下一个最小整数。这听起来是不是有点像在数字的二进制世界里寻找它的“下一个排列”没错这道题的精髓就在于此。它考察的不是复杂的算法设计而是对二进制数底层特性的深刻理解和巧妙的位操作技巧。很多人在第一次遇到时可能会选择最直观的暴力枚举法从给定数加1开始逐个判断其二进制中1的个数是否与原数相等。这个方法对于小数字没问题但当输入是一个接近32位整数上限比如2147483647的数时这种线性扫描的耗时将是灾难性的必然导致超时TLE。所以这道题逼着我们去寻找一个O(1)时间复杂度的优雅解法。这不仅仅是为了AC一道题更是理解计算机如何高效处理比特位的一个绝佳案例。在底层系统编程、压缩算法、位图Bitmap操作等场景中类似的位操作技巧无处不在。接下来我们就彻底拆解这个问题从暴力法开始一步步推导出那个高效且优美的位运算解法并深入探讨其背后的数学原理和实现细节。2. 问题定义与暴力法的局限性首先让我们把问题用更精确的语言描述一遍。输入一个正整数N(1 ≤ N ≤ 2^31 - 1)。输出一个正整数M满足以下三个条件M N。M的二进制表示中“1”的个数即popcount(M)与N的二进制表示中“1”的个数相等。在所有满足条件1和2的数中M的值是最小的。例如对于N 6(二进制110有2个1)下一个比6大且拥有2个1的数是9(二进制1001)。7(111)有3个18(1000)只有1个1都不符合。2.1 暴力枚举法及其复杂度最直接的思路就是写一个计算二进制中1的个数的函数popcount(x)然后从N1开始循环直到找到第一个popcount(i) popcount(N)的i。int popcount(int x) { int count 0; while (x) { count x 1; // 检查最低位是否为1 x 1; // 右移一位 } return count; } int nextSamePopcount_bruteforce(int N) { int target popcount(N); int M N 1; while (popcount(M) ! target) { M; } return M; }这个方法简单明了但问题出在时间复杂度上。考虑最坏情况N 2147483647(即0x7FFFFFFF二进制为31个1)。它的popcount是31。比它大的下一个拥有31个1的数是多少是0xBFFFFFFF(二进制10111111111111111111111111111111)。从N1到M中间间隔了大约0x40000000也就是十进制的1,073,741,824个数即使每次popcount计算是O(log N)的因为要遍历比特位整体复杂度也接近O(N log N)对于OJ的时限来说是完全不可接受的。注意这里popcount的复杂度通常被认为是O(log N)因为整数N的二进制位数约为log2(N)。但在现代CPU上通常有专门的指令如__builtin_popcount在O(1)时间内完成。暴力法的失败告诉我们必须利用二进制数的结构特性直接“计算”出下一个数而不是“搜索”。3. 寻找规律与关键观察要设计高效算法我们需要在二进制表示上发现规律。让我们用几个例子来手动推导例1:N 6(0b0110)目标找到下一个有2个1的数。从右向左扫描比特位位置(从右起0-based):bit11, bit21, bit30, bit40(即0110)。我们发现第一个“01”模式出现在 bit2和bit1值1和 bit3值0。更准确地说是从右向左找到第一个“1”并且这个“1”的左边一位是“0”。在0110中从右向左第一个“1”是 bit1它左边 bit2 是“1”不符合。继续找bit2 也是“1”它左边 bit3 是“0”符合我们找到了一个“01”序列bit30, bit21。操作交换这个“01”序列变成“10”。即把 bit3 设为1bit2 设为0。得到0100(0b0100 4)。但这比6小不符合M N。原因是仅仅交换这两位我们减少了1个1从 bit2 移到 bit31的个数没变等等这里错了。让我们重新思考。让我们换一种更系统的方法也是标准解法遵循的路径找到最右侧的、非拖尾的“1”。什么是“拖尾的1”就是右边全是0的1。例如在0b101100(44) 中拖尾的1是 bit2因为 bit1和bit0是0。我们要找的是这个拖尾1左边第一个“0”。实际上标准算法描述是c0: 从最右边开始数连续0的个数直到遇到第一个1。c1: 紧接着上述连续0的左边连续1的个数。找到p c0 c1这个位置就是最右边非拖尾的“1”的位置从右数0-based。将该位置的“1”置为“0”。在它的右边放入(c1 - 1)个“1”其余位全部置“0”。在更右边放入c0 1个“0”吗不需要重新组织。让我们用N44(0b101100) 来演练二进制:1 0 1 1 0 0从右向左遇到两个0 (c02)。然后遇到三个1 (c13)不对仔细看... 1 1 0 0在倒数第3位(bit2)是1倒数第4位(bit3)是1倒数第5位(bit4)是0。所以从右开始先是两个0 (c02)然后是两个1 (c12)然后遇到一个0。这个0的位置p c0 c1 2 2 4(bit4)。这个bit4就是我们要找的“最右侧非拖尾的1”吗bit4当前是0啊。哦我明白了这个算法找的是第一个“0”这个“0”的右边有c1个连续的1再右边有c0个连续的0。我们要做的是把这个“0”变成“1”。正确步骤根据《程序员面试金典》等经典描述 a. 找到最右边非拖尾的0。这个0的右边有c1个连续的1再右边有c0个连续的0。 b. 将该0置为1。此时1的个数增加了1。 c. 将刚才右边所有的c1个1全部移到最右边并确保它们左边有c0个0。 d. 但为了保持1的总数不变因为我们已经把一位0变成了1增加了1个1我们需要减少c1 - 1个1。所以在紧邻新设置的1的右边我们放c1 - 1个1其余位放0。对于N44(101100):c0 2(bit1,bit0 是0)c1 2(bit3,bit2 是1)p c0 c1 4(bit4当前是0)操作将 bit4 从0设为1。 -1 1 1 1 0 0? 不对先别动其他位。将 bit4 右边的所有位(bit3到bit0)清零。 -1 0 0 0 0 0(96)在低位bit0开始插入c1 - 1 1个1。因为c02我们需要留出位置。更准确地说在 bit4 被置1后我们需要在右边部分构造一个数这个数有c1-1个1并且这些1位于尽可能低位以保证新数最小。构造右边部分一个二进制数其最低的c1-1位是1其余是0。这个数就是(1 (c1-1)) - 1。这里c1-11所以这个数是1(0b000001)。但是我们还需要将这个构造出的数左移c01位吗不对。我们需要将它放到 bit4 的右边。bit4 的右边有c0c14个位。我们希望c1-1个1位于这些位的最右侧。所以我们将构造的数左移c01位让我们用公式。标准公式M N (1 c0) (1 (c1 - 1)) - 1推导一下N 101100 (44)c02, c121 c0 1 2 4 (0b000100)1 (c1-1) 1 1 2 (0b000010)(1 (c1-1)) - 1 2 - 1 1 (0b000001)M 44 4 1 49验证49 0b110001有3个1。等等44(101100) 也有3个1。符合而且110001确实比101100大并且是下一个最小的吗让我们手动找45(101101-3个1), 46(101110-4个1), 47(101111-5个1), 48(110000-2个1), 49(110001-3个1)。是的49是正确答案。这个公式很巧妙但直接记忆容易出错。我们接下来用更直观的位操作步骤来实现。4. 位运算的经典解法与逐步实现我们放弃公式采用一系列明确的位操作步骤这些步骤在任何语言中都容易实现且逻辑清晰。设输入为int n。4.1 步骤分解步骤1计算c0和c1c0: 尾部连续0的个数。c1: 尾部连续0之后连续1的个数。如何计算我们可以通过n与n1等技巧但更清晰的方法是直接扫描。int c n; int c0 0; int c1 0; // 计算 c0: 统计尾部连续的0 while (((c 1) 0) (c ! 0)) { c0; c 1; } // 计算 c1: 统计紧接着的连续1 while ((c 1) 1) { c1; c 1; }例如n44 (101100):初始c101100。c 1 0,c01,c10110。c 1 0,c02,c1011。现在c 1 1跳出第一个循环。c02。进入第二个循环c 1 1,c11,c101。c 1 1,c12,c10。c 1 0跳出循环。c12。步骤2检查错误情况如果n的二进制形式是111...1000...0即所有1都在左边所有0都在右边或者n 0那么不存在更大的、具有相同数量1的数。对于32位整数如果c0 c1 31因为最高位是符号位我们考虑31位则说明n是这种形式。但题目保证有解我们可以不处理但健壮的代码应该检查。步骤3找到位置p并翻转位位置p c0 c1。这是从右边数起第一个非拖尾的1的位置实际上是第一个“0”的位置这个“0”的右边是c1个1再右边是c0个0。在我们的例子中p 2 2 4(bit4)。将n的第p位设置为1。因为当前这位是0我们是通过找到c0和c1的方式定位到这个0的。n | (1 p); // 将第p位设为1操作后n从101100变成了111100(60)。注意我们一下子把 bit4 从0改成了1同时 bit3, bit2 原本就是1没变。但我们的目标是构造一个新数所以最好在一个新的变量上操作或者先记录这个操作。步骤4清除p位右边的所有位现在我们需要将位置p右边的所有位清零以便我们重新放置正确数量的1。// 创建一个掩码将第p位右边的所有位清零 // 掩码形式左边全是1直到第p位包含右边全是0。 // 我们可以用 (~0) (p1) 得到。 n ~((1 (p1)) - 1); // 清除p位含右边的所有位(~0) (p1)会得到一个高位全1低位从第0位到第p位全0的数。但更直观的是(1 (p1)) - 1会产生一个低p1位全1的数取反后就得到了一个低p1位全0高位全1的掩码。用n与这个掩码进行与操作就清除了低p1位。 在我们的例子中p4(1 5) - 1 0b11111取反后是0b...1111111111111111111111111100000低5位为0。与n(现在是60,111100) 相与得到1100000(96)? 等等我们之前n被改成了60 (111100)。清除低5位后n变成了1100000(96)。是的bit4现在是1bit3-bit0全是0。步骤5插入正确数量的1我们需要在低位放入c1 - 1个1。并且为了使得新数最小这些1应该放在最右边最低位。如何生成一个有c1-1个1的数(1 (c1-1)) - 1。int ones (1 (c1-1)) - 1; // 如果c1-1为0则ones0 n | ones; // 将这些1放到最低位在我们的例子中c12,c1-11,ones (11)-1 1。n目前是1100000(96)。n | 1得到1100001(97)。等等我们之前用公式算出是49。哪里出错了错误分析我们犯了一个顺序错误。在步骤4中我们清除了从第0位到第p位包括第p位的所有位吗我们的掩码~((1 (p1)) - 1)清除了低p1位。对于p4它清除了 bit4, bit3, bit2, bit1, bit0。但我们在步骤3中刚刚把 bit4 设为了1步骤4又把它清除了这不对。正确的顺序应该是先计算c0,c1,p。将第p位设为1。但此时第p位右边还有原来的c1个1和c0个0。将第p位右边的所有位清零。在清零后的区域的最右边放入c1-1个1。但步骤2和3可以合并我们不需要先设1再清零我们可以直接构造一个新数。更清晰的做法是修正后的步骤计算c0,c1,p。n (1 c0);// 这一步相当于将最右边的一个“1”向左移动了一位让我们验证。对于n44 (101100)c02。1 c0 4 (100)。n 4 48 (110000)。这步操作的效果是将最右边的一串“...100”变成了“...1000”即把拖尾的“1” (bit2) 变成了0并向其左边的位bit3进了1。同时它清除了尾部所有的0。现在n变成了110000。n | ((1 (c1-1)) - 1);// 在低位放入c1-1个1。c12,(1 1) - 1 1。n 48 | 1 49 (110001)。正确这个“加(1 c0)”的操作非常精妙它一次性完成了两件事a) 将最右边的非拖尾的0变成了1实际上是通过进位实现的b) 将原来该位置右边的所有位清零。4.2 完整代码实现#include stdio.h int nextSamePopcount(int n) { // 计算 c0 和 c1 int c n; int c0 0; int c1 0; // 统计尾部连续的0 while ((c 1) 0 c ! 0) { c0; c 1; } // 统计连续的1 while ((c 1) 1) { c1; c 1; } // 如果 n 是 ..111100..0 这种形式或者 n0理论上无解但题目保证有解 // 位置 p // int p c0 c1; // 在这个算法里我们不需要显式计算p // 核心操作 n (1 c0); // 步骤1: 将最右边的非拖尾的0变为1并清零右边所有位 n | (1 (c1 - 1)) - 1; // 步骤2: 在右边补上 (c1-1) 个1 return n; } int main() { int n 44; printf(Next number for %d (%b) is %d (%b)\n, n, n, nextSamePopcount(n), nextSamePopcount(n)); // 输出: Next number for 44 (101100) is 49 (110001) return 0; }注意代码中(1 (c1 - 1)) - 1在c10时会出现移位负数的情况需要特殊处理。但根据我们的定义c1是连续1的个数在找到非拖尾的0时c1至少为1。如果c1为0说明n本身就是0或者没有1这些边界情况题目可能不涉及但生产代码需要处理。例如可以加判断if (c1 0)。5. 边界条件、测试与算法正确性证明任何算法都不能忽视边界条件。对于这个问题我们需要考虑几种特殊情况n 0: 二进制全01的个数为0。比0大且1的个数为0的下一个数不存在因为正整数至少有一个1。题目范围N 1所以可以忽略。n的二进制形式为111...1000...0: 即所有1在左边所有0在右边。例如n 0b111000(56)。此时从右向左找到第一个“0”时这个“0”的右边没有连续的1c10或者这个“0”就是最高位实际上对于32位整数如果n是0b111000c03,c13,p6。n (1c0) 56 8 64 (0b1000000)。然后n | (1(c1-1))-1 64 | ((12)-1) 64 | 3 67 (0b1000011)。67的二进制有3个1且大于56。看起来算法仍然有效。但有一种极端情况n 0b111111...111(全1例如31个1)。此时不存在一个更大的、拥有相同数量1的32位正整数因为1的个数已经最大。算法中c00,c131p31n (10) n1会导致整数溢出如果n是0x7FFFFFFF。在实际解题中题目通常不会给出这种导致无解的输入但我们的代码应该能处理或给出提示。c11的情况: 例如n0b1001(9)。c00(因为最后一位是1)c11(只有最后一位是1它左边是0)。n (10) 10 (0b1010)。(1(c1-1))-1 (10)-1 0。结果n | 0还是10。10的二进制1010有2个1和9 (1001)一样。正确。为了验证算法的普遍正确性我们可以从组合数学的角度理解我们实际上是在所有具有k个1的二进制数中找到当前数n的“下一个”字典序排列。二进制串的字典序比较就是数值比较。算法步骤n (1 c0)相当于找到了下一个比n大的“拐点”这个操作将最右边的一个“01”变成了“10”并让后面的位变成全0。n | (1 (c1-1)) - 1则是将后面全0的部分重新设置成最小的、具有c1-1个1的数以保证总体的1的数量不变且新数尽可能小。6. 在LightOJ等OJ上的实战要点如果你要在LightOJ 1042上提交代码这里有一些实战建议输入输出格式: LightOJ题目通常是多组测试数据。需要循环读取直到文件结束。#include stdio.h int main() { int T, caseNo 1; scanf(%d, T); while (T--) { int n; scanf(%d, n); int ans nextSamePopcount(n); printf(Case %d: %d\n, caseNo, ans); } return 0; }使用内置函数许多现代编译器如GCC提供了内置函数__builtin_popcount用于快速计算1的个数以及__builtin_ctz用于计算尾部0的个数。这可以简化计算c0和c1的过程甚至直接实现算法。c0 __builtin_ctz(n);// 计算尾部0的个数然后int temp n (1 c0);c1 __builtin_popcount(n) - __builtin_popcount(temp);// 不是直接关系需要调整。更稳妥的还是用位操作。一个利用内置函数的优雅解法参考int nextSamePopcount_builtin(int n) { int c (n -n); // 得到最右边1的位置例如 n101100, c000100 int r n c; // 将最右边的连续1块向左移动一位例如 101100 000100 110000 // 现在r 在原来连续1块的位置上多了一个1右边全是0 // 我们需要将多出来的 (popcount(n) - popcount(r)) 个1放回最右边 // 实际上多出来的1的个数是原来连续1块的个数减1 // 可以通过以下方式计算 return (((r ^ n) 2) / c) | r; }这个解法更短但理解起来需要更多位运算知识。对于竞赛掌握我们上面逐步推导的方法更稳妥。注意整数范围题目说N 2^31 -1所以用int足够在C/C中通常是32位有符号。在加法n (1 c0)时确保不会溢出。对于最大数0x7FFFFFFFc0可能是0n1会变成0x80000000这是一个负数如果是有符号int。但题目应该不会给出导致无解或溢出的合法输入。为了安全可以使用unsigned int进行计算。测试用例自己多构造一些测试用例包括简单数字1, 2, 3, 4, 5, 6, 7, 8全1的边界0x7FFFFFFF(2147483647)有多个连续1块的0x0F0F0F0F,0x12345678结果接近2^31的。7. 举一反三相关位运算问题模式掌握了“下一个具有相同数量1的数”你可以轻松解决一系列变体问题上一个具有相同数量1的数找出比n小的最大数且1的个数相同。思路类似寻找最右边的“10”模式将其变为“01”并将其右边的所有位调整成最大的、具有特定数量1的模式即1全部靠左。判断一个数是否是2的幂(n (n-1)) 0。因为2的幂的二进制只有一个1。计算汉明距离两个整数二进制位不同的个数。xor后计算popcount。位计数Popcount的多种实现除了循环还有查表法、分治法n (n 0x55555555) ((n 1) 0x55555555)等。提取或设置特定位这是位运算的基础如设置第k位n | (1 k)清除第k位n ~(1 k)翻转第k位n ^ (1 k)。这道“Secret Origins”题就像一把钥匙帮你打开了一扇深入理解整数二进制表示和位操作的大门。它教会我们的不仅仅是那个巧妙的算法更是一种思维模式当暴力搜索行不通时去观察数据的固有结构在这里是二进制位的排列并利用位运算这种接近硬件底层的操作以O(1)的代价完成看似需要遍历的任务。在编写高性能代码、处理位图、设计压缩算法或进行加密运算时这种能力至关重要。下次当你需要操作比特位时不妨回想一下这个寻找“下一个排列”的过程它很可能就是解决问题的关键洞察。