第一次看到这道题时我内心是有点不以为然的——排序嘛谁不会呢。但真正动笔之后才发现**根据数字二进制下 1 的数目排序**这道题把位运算和自定义排序两个最常用的基础能力拧在一起稍不留神就会翻车。尤其是它要求先按每个数二进制里1的个数升序如果1的个数相同还要再按数值本身升序——这实际上是一个双关键字的排序问题比表面看起来的单维排序多了一层隐藏的门槛。今天这篇就聊聊我刷题时的完整思考过程以及从这道题里沉淀出来的一些通用优化思路。1. 题目拆解双key排序的考点不在排序而在键的计算1.1 先看清楚题目到底要排什么LeetCode 1356这道题的原意是给你一个非负整数数组arr要对数组中的元素按照二进制下 1 的数目升序排序如果两个数的二进制中1的数量相同再按照数本身的大小升序。比如arr [0,1,2,3,4,5,6,7,8]排序结果是0 - 二进制 01的个数 0 1 - 11的个数 1 2 - 101的个数 1 4 - 1001的个数 1 8 - 10001的个数 1 3 - 111的个数 2 5 - 1011的个数 2 6 - 1101的个数 2 7 - 1111的个数 3最后输出[0,1,2,4,8,3,5,6,7]。看到这个例子大部分人第一反应是写一个比较函数先算出每个数的1的个数然后比较这个数相同就比较原始值。思路没问题但这里有一个很容易忽略的点题目里的第二关键字数值本身也是排序规则的一部分。很多人写排序比较器的时候只写了如果 popcount 不同就返回 popcount 的大小关系那当 popcount 相同时比较器返回什么如果返回false对于严格弱排序来说这两个元素就被视为等价。虽然很多排序算法最后也会按原始顺序或稳定顺序排但 C 的std::sort不保证稳定性一旦数据顺序打乱结果就可能不符合题意。所以必须把a b的情况作为第二个条件补上。1.2 这道题真正的考察点如果只从排序算法本身看这道题完全没有考到快排、归并这些经典排序内部的实现细节它考的是两个基础能力的组合一是要知道一个整数二进制里1的个数怎么高效计算。这个能力对应位运算基本功也叫population count常写作popcount。二是要能熟练地把自定义规则翻译成对应语言里的排序比较器。这是日常工程里经常遇到的事——数据库ORDER BY可以写多列但用代码做内存排序时很多人会忘记多关键字的组合方式。所以这道题的难度虽然不高但覆盖面很广适合用来检验一个新手对位运算和排序接口的熟悉程度。我在面试候选人的时候也喜欢出类似的题考察点不在于能不能AC而在于能不能解释明白两个关键字的优先级关系和位计数方法的复杂度差异。2. 位1计数从逐位遍历到 Kernighan 再到查表2.1 方法A逐位检查——最朴素也最容易写错拿到一个整数想知道它二进制里有几个1最直接的方法是循环右移每次检查最低位是否为1int countOnes(int n) { int count 0; while (n) { count n 1; n 1; } return count; }这段代码的逻辑是n 1能取到二进制最低位如果是1就计数器加一然后把n右移一位相当于看下一位。对于非负整数这个写法完全正确。它的时间复杂度是O(bits)其中bits是整数的二进制位数对 int 来说通常是 32。但这段代码在工程里很容易被扩展成负数场景时踩坑C 中对有符号整数使用右移是算术右移负数右移会补符号位导致无限循环。虽然在本题里输入是非负整数不需要考虑但我还是建议在实际工作中养成习惯——要么先把整数转成unsigned int要么用无符号类型的位操作。这道题里arr[i]的范围是0 arr[i] 10^4所以用 int 完全没风险。逐位检查的优点是代码直观缺点是每个数的计算成本固定等于位数。如果数组很长这种写法整体就是O(n * 32)虽然数据量小时无所谓但作为算法题我们希望有更优雅的办法。2.2 方法BBrian Kernighan 算法——让循环次数只跟1的个数有关Kernighan 算法是位运算里非常经典的小技巧核心就一句话n n (n - 1)这个表达式的作用是把n二进制中最低位的那个1变成0。为什么因为n - 1会让最低位的1变成0同时让它右边的所有0变成1。相与之后只有n中比这个最低位更高的位保持不变最低位及其右边的位全部清空。举个例子n 12 1100 n-1 11 1011 n (n-1) 1000 8于是从12变成8最低位的那个1被消掉了。循环执行这个操作并计数直到n变成0循环次数恰好等于二进制中1的个数int countOnes(int n) { int count 0; while (n) { n n (n - 1); count; } return count; }对于n 12循环两次就结束比逐位检查的 4 次这里假设最高位在第四位更少。如果1的个数稀疏比如n 10000000那就只需要 1 次。这个算法的平均效率是O(ones)ones是1的个数最坏情况等于bits但实际使用中通常会比逐位检查更快。我个人非常推荐掌握这个写法因为它在没有内建函数的环境下是最优的通用实现而且代码简短、不容易错。2.3 方法C语言内建函数和预计算表——省心但要知道边界实际开发里没必要每次都自己写循环。C 的 GCC 和 Clang 都有内建函数__builtin_popcount(n)它能直接返回n的二进制表示中1的个数。注意它在底层可能映射到 CPU 指令比如 x86 上的POPCNT指令执行起来非常快。Java 里有现成的Integer.bitCount(n)Python 里最简洁bin(n).count(1)但这类内建函数不是没有坑。比如 C 的__builtin_popcount接收的参数类型是unsigned int如果你传一个有符号 int 的负数会发生隐式转换后统计补码里的1结果往往不是你以为的负数的绝对值有几个1。而 Java 的Integer.bitCount也是按补码处理的。在本题目范围内数组元素是非负整数所以问题不大但如果你想把这套逻辑拿到别的场景里就一定要确认自己需要的是补码的 1 的个数还是绝对值的 1 的个数。如果既不想依赖内建函数又想减少重复计算可以用一个预计算表。因为题目给的范围是0 arr[i] 10^4最大也就 10000完全可以开一个长度为 10001 的数组直接递推vectorint bitCount(10001, 0); for (int i 1; i 10000; i) { bitCount[i] bitCount[i 1] (i 1); }这个递推的原理是i 1是去掉最低位i 1是最低位本身所以i的1的个数等于去掉最低位之后的数字的1个数加上最低位是否为1。这个表可以在一开始就建好后面每个数直接查表是教科书里标准的动态规划打表思路。三种方法的对比如下方法时间复杂度单个数代码复杂度适用场景逐位检查O(bits)低新手理解、位数少Kernighan 循环O(ones)低通用、不依赖内建函数内建函数/预计算表O(1)中高频调用、性能敏感3. 用不同语言实现一次照着我踩过的坑调整3.1 Python一行 sorted 也能体现思路Python 里实现这道题最简单的方式是直接用sorted并且用key参数返回一个元组class Solution: def sortByBits(self, arr: List[int]) - List[int]: return sorted(arr, keylambda x: (bin(x).count(1), x))这里的key函数返回(count, x)Python 的sorted会先比较元组的第一项如果相等比较第二项正好对应题目要求的双关键字排序。这段代码看起来很短但包含了一个非常重要的工程思想排序键应该是一个计算一次然后存起来的独立值而不是在每次比较时动态去算。Python 的sorted内部会为每个元素调用一次key函数然后缓存结果因此多个元素的count(1)不会重复计算。如果不想用bin字符串也可以自己写一个popcount函数比如def popcount(x): cnt 0 while x: x x - 1 cnt 1 return cnt然后keylambda x: (popcount(x), x)。你会发现无论怎么写核心都是两件事算好键排序。3.2 Clambda 比较器与内建函数的细节C 的标准做法是用std::sort配合 lambdaclass Solution { public: vectorint sortByBits(vectorint arr) { sort(arr.begin(), arr.end(), [](int a, int b) { int ca __builtin_popcount(a); int cb __builtin_popcount(b); if (ca ! cb) return ca cb; return a b; }); return arr; } };这个写法有二个关键点要解释比较器必须满足严格弱序。当ca cb时我们不能返回true因为a b时也必须返回false。这里用a b作为第二关键字保证了任意两个不相等元素都能有一个确定的大小关系。__builtin_popcount在大多数编译环境下对非负整数是正确的。但如果你在 Windows 的 MSVC 环境下写它不认识这个函数你可能得改用std::bitset32(n).count()或者自己写 Kernighan。所以在提交给在线评测网站之前先确认一下你的编译器。另外如果你担心std::sort不稳定导致顺序不可控可以改用std::stable_sort。但对于这道题来说比较器里已经包含原始数值作为最后的 tie-breaker所以输出结果是确定且正确的std::sort就够了。3.3 Java 和 Go从不能直接传比较器说起Java 的Arrays.sort对基本类型数组int[]是不能传自定义比较器的因为它内部使用双轴快排不走对象比较。最常见的方式是把int[]转成Integer[]或者把每个数封装成包含count和value的对象。一个更省空间的做法是先把数组转成二维数组或者int[][2]然后排序class Solution { public int[] sortByBits(int[] arr) { int n arr.length; int[][] pairs new int[n][2]; for (int i 0; i n; i) { pairs[i][0] Integer.bitCount(arr[i]); pairs[i][1] arr[i]; } Arrays.sort(pairs, (a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]); int[] res new int[n]; for (int i 0; i n; i) { res[i] pairs[i][1]; } return res; } }注意在比较器里我用的是Integer.compare的更安全版本上面二元比较用了a[0] - b[0]因为a[0]最大也只有 1410000的二进制1的个数是 5不对10000 2^1416384最大 14位1的个数最大是14比如81912^13-1有13个1所以差值不会溢出不会溢出。但如果数值范围不明确我建议写成Integer.compare(a[0], b[0])养成好习惯。Go 语言通常用sort.Slice然后通过bits.OnesCount获取1的个数func sortByBits(arr []int) []int { sort.Slice(arr, func(i, j int) bool { ci, cj : bits.OnesCount(uint(arr[i])), bits.OnesCount(uint(arr[j])) if ci ! cj { return ci cj } return arr[i] arr[j] }) return arr }这里要注意 Go 的bits.OnesCount参数是uint所以要显式把int转成uint。如果数组里有负数这种转换会得到它的无符号整数表示bit count 也变成了补码的统计和前面提到的问题一样。4. 性能优化当数据规模放大我该怎么办4.1 避免在比较器里反复算 bit count虽然 LeetCode 这道题的arr.length最长只有 500完全不需要优化但工程思维就是要在小规模里看到大问题的影子。如果你在一个很大的数组上做同样的需求最忌讳的写法是sort(arr.begin(), arr.end(), [](int a, int b) { return __builtin_popcount(a) __builtin_popcount(b); });这种写法里每次比较两个元素都会重新计算一次 popcount而排序算法的比较次数通常远大于元素个数这会造成大量重复计算。更合理的思路是先计算出每个数的排序键然后一起带入排序过程也就是常说的 decorate-sort-undecorate装饰-排序-撤销模式Python 的key参数其实就是这个模式的语言级封装。具体到 C我们可以先构建一个由(count, value)组成的数组vectorpairint, int v; for (int x : arr) { v.push_back({__builtin_popcount(x), x}); } sort(v.begin(), v.end()); vectorint res; for (auto [c, val] : v) { res.push_back(val); }pair的默认比较规则就是先比较第一个元素再比较第二个元素刚好满足题目的双关键字要求。这样每个元素只算一次 popcount无论在排序过程中被比较多少次都不会重复计算键。我在实际项目中处理类似先按某个衍生指标排序再按原值排序的需求时都是优先采用这种pair思路因为它逻辑更清晰不容易漏掉 tie-breaker。4.2 桶排序思路让 bit count 成为分桶条件还有没有更强的优化对于0 ~ 10^4范围内的数字1的个数最多不超过 14 个。一想到 key 的取值范围很小就有另一个方向桶排序。我们可以遍历一遍数组按1的个数分到不同的桶里然后对每个桶内部按数值排序最后把所有桶按顺序拼起来。vectorvectorint buckets(15); for (int x : arr) { buckets[__builtin_popcount(x)].push_back(x); } vectorint res; for (auto b : buckets) { sort(b.begin(), b.end()); res.insert(res.end(), b.begin(), b.end()); } return res;这个做法的复杂度可以做到O(n k log k)这里的k是某个桶内元素的数量但每个桶里的数值范围有限甚至会非常快。从工程上看它把排序拆成了按key分组和组内排序两步实际上是利用了 key 的离散性这在很多大数据处理任务里是一种常见的分而治之策略。当然对这道题来说属于过度设计但当事件发生时能想到这个方案说明你已经开始关注数据特征对算法选择的影响了。4.3 复杂度分析与实测感受原题的标准解法只需要一次sort对于长度为n的数组时间复杂度是O(n log n)空间复杂度取决于实现方式。如果选择pair数组空间占用是O(n)如果直接在原数组上排序空间复杂度是O(1)。不管哪种这道题本身都不会造成任何性能压力。我在本地分别用比较器内重复计算 popcount和预提取 key 成 pair两种方式跑过 100 万个随机数后者耗时一般是前者的三分之一到一半左右。具体数字跟编译器优化程度有关但总体趋势稳定。**真正的工程经验是如果排序键是一个计算成本较高的衍生值务必提前算好并缓存而不是依赖比较器的惰性计算。**朴素的直觉认为比较器只会在排序时调用但快速排序的时间复杂度接近O(n log n)比较次数大概是n log n的常数倍当n很大时重复计算带来的成本会被显著放大。5. 这类位排序的思路在真实工程场景中的延伸5.1 汉明距离排序与相似度检索为什么需要统计二进制里1的个数最直接的应用是汉明距离Hamming distance。两个整数异或之后得到的二进制里1的个数就是它们之间的汉明距离。在图像感知哈希pHash、音频指纹识别等领域我们经常要计算一个待检测样本和库中所有样本的汉明距离然后按距离从小到大的顺序返回最相似的若干个结果。如果一次要处理成千上万个样本你很可能就会用到排序而排序的 key 就是异或结果中 1 的个数。这和本题的popcount是同一个操作。只不过真实场景里不会只对单个整数排序而是对样本 ID 距离这样的结构排序这时候就可以把我们在第 4 章说的pair预提键思路发挥出来先算好距离再排序而不是每次比较都xor一次。5.2 多关键字排序的通用解法DSU 模式根据二进制下 1 的数目排序数目相同再按原值排序这句话本质上是多关键字排序。数据库里写ORDER BY column1, column2非常简单但在内存数据结构里实现正确的解法是构造组合排序键。Python 的元组天然支持多关键字C 的pair/tuple也支持字典序Java 可以用Comparator链式调用Go 就只能手写比较器。如果你在做一些基础库或中间件需要支持任意多字段排序那么装饰-排序-撤销DSU是更通用的解法。流程是遍历原始数据为每个元素计算一个或多个排序键将原数据和键组合成一个新的结构或者放入元组用默认的字典序排序这个新结构从排序后的结构中取出原数据。这样做的好处是计算键和比较大小完全分离代码复用度高也方便后续对算法做性能优化。LeetCode 1356就是我常用来向新人演示这个模式的例子。5.3 稳定的链式排序等价双关键字实现还有一种更偏理论的做法如果语言只提供稳定排序可以先按第二关键字排序再按第一关键字排序。你要先按数值升序再按 popcount 升序做一次稳定排序就能得到题目要求的结果。稳定排序能保证第一关键字排序时不改变第二关键字的相对顺序从而合并出多关键字效果。这个技巧在经典算法教材里被称为 stable sort chaining。不过在现代语言里直接自定义比较器更直接链式排序更适合那些key 计算昂贵且无法预提的极端场景。但如果你在做一些不允许使用自定义比较器的环境比如某些数据库查询优化器内部这个思路仍然值得保留。最后再分享一点个人感受刷题不是背答案而是通过一道题把若干基础知识点串起来。这道题真正让我受益的不是那个 AC 的瞬间而是逼着我把位运算、排序键提取、多关键字比较、按桶分治这些知识在整个工程图景里重新放了一遍。下次你手头遇到按某个二进制特征排序的需求我建议你先别急着调sort停下来想一想这个 key 好算吗能不能提前算有没有更好的分桶方式想清楚这些比多刷十道类似的题更有用。