我很多次在刷题群里看到有人一看到“根据数字二进制下 1 的数目排序”这个题名就发怵心想数字排序我会但二进制下的“1的数目”是个什么东西其实把这句话拆开看核心就三个词二进制、1的数目、排序。这三件事单独拎出来都不难放到一道题里考的就是你把这些基础能力组合起来解决实际问题的熟练度。这个题目是 LeetCode 第 1356 题难度是简单但它非常典型用到的知识点包括二进制位计数、多关键字排序、比较器写法进阶一点还能牵扯出计数排序这类不需要比较的排序思路。不管你是准备面试的求职者还是刚学完基础语法想找点题练手的新手这道题都值得认真过一遍。我自己在实际工作中写数据处理脚本时也经常遇到类似“先按某个隐含属性分组再按另一维度排序”的需求这道题的本质和那些真实场景是一致的。1. 题目到底在问什么题意拆解与核心考点1.1 输入输出长什么样先看最原始的题目格式。给你一个整数数组 arr要求你把这个数组排序排序规则是先按每个数字的二进制表示中“1”的个数从少到多排序如果两个数字二进制下 1 的个数相同就按数字本身从小到大排序。举个例子输入 arr [0, 1, 2, 3, 4, 5, 6, 7, 8]0 的二进制是 01 的个数是 01 的二进制是 11 的个数是 12 的二进制是 101 的个数是 13 的二进制是 111 的个数是 24 的二进制是 1001 的个数是 15 的二进制是 1011 的个数是 26 的二进制是 1101 的个数是 27 的二进制是 1111 的个数是 38 的二进制是 10001 的个数是 1。所以先按 1 的个数分组0 个 1 的是 [0]1 个 1 的有 [1, 2, 4, 8]2 个 1 的有 [3, 5, 6]3 个 1 的有 [7]。组内按数值升序排好后就是 [0, 1, 2, 4, 8, 3, 5, 6, 7]。这道题在原题里的数据范围是 0 arr[i] 10^4而且数组长度最大是 500。这个范围意味着你不需要用任何花哨的优化也能通过但它不限制你往更高效的方向想。1.2 这道题真正考的是什么表面上看这道题考的是“你会不会统计二进制中 1 的个数”但往深一层看它考的是三件事。第一位运算基本功。统计二进制中 1 的个数有很多种办法你可以转字符串数 1可以循环移位判断最低位也可以用 n (n - 1) 这种经典技巧。不同方案的性能差很多面试时你选哪种、能不能说清原理体现的就是底层基本功。第二多关键字排序的理解。系统自带的排序函数默认是拿一个值去比较但这里每个数字有两个比较维度第一个维度是“1 的数目”第二个维度是“数字本身”。你能不能把这种规则翻译成比较器里的返回值是很多人在实际开发中都会遇到的场景。第三对算法复杂度的敏感度。常规思路是先统计每个数字的 1 的数目再调用系统的快排整体时间复杂度是 O(n log n)这个答案已经很好了。但如果你知道“1 的数目”的取值范围非常小比如 32 位整数最多只有 0 到 31 个 1就能想到用桶排序做到 O(n)思路一下子就上了一个档次。2. 先跑通最直觉的三种写法2.1 用内置函数一行搞定如果只是为了 AC最简单的方式是直接利用各语言内置的二进制转换函数。Python 里就是 bin() 加字符串 countclass Solution: def sortByBits(self, arr: List[int]) - List[int]: return sorted(arr, keylambda x: (bin(x).count(1), x))这里的关键点是sorted 的 key 参数传的是一个元组Python 会先比较元组第一个元素相同再比较第二个元素。所以 (bin(x).count(1), x) 天然实现了“先按 1 的数目再按数值”的排序规则。如果用 Java可以写成class Solution { public int[] sortByBits(int[] arr) { return Arrays.stream(arr) .boxed() .sorted(Comparator.comparingInt(Integer::bitCount) .thenComparingInt(Integer::intValue)) .mapToInt(Integer::intValue) .toArray(); } }Java 的 Integer.bitCount 就是专门统计 int 二进制中 1 的个数的这个比较器写法也很清晰。这段代码跑起来没有任何问题但它隐藏了一个细节bin() 先把整数转成字符串再从头到尾扫一遍数 1时间复杂度是 O(k)k 是二进制的位数。数据量小的时候无所谓但如果你在嵌入式环境或者追求性能的场景里这么写多少有点浪费。2.2 循环移位逐位判断如果你不想依赖字符串最简单的位运算思路是每次看最低位是不是 1然后右移一位重复直到数字变成 0。def count_ones(n: int) - int: cnt 0 while n: cnt n 1 n 1 return cnt这里 n 1 的作用是取出最低位最低位为 1 就计数加一为 0 就不加。右移一位相当于把第二位移到最低位。这个写法比较容易理解但它的循环次数等于 n 的二进制位数对于 32 位整数最多循环 32 次性能也算 OK。C 里写这个逻辑要注意 n 1 是对有符号数还是无符号数操作。如果是 int右移可能是算术右移高位补符号位但因为我们只统计正数问题不大。如果处理的可能是负数建议用无符号类型或者用逻辑右移。2.3 用 n (n - 1) 提升效率比逐位判断更经典的是 n (n - 1) 这个操作它每次能直接消掉二进制表示中最低位的那个 1。原理回头细说这里先记住用法def count_ones(n: int) - int: cnt 0 while n: n n - 1 cnt 1 return cnt这个循环的次数等于 n 中 1 的个数而不是二进制总位数。比如 n 8二进制是 1000只有 1 个 1循环只需要跑一次但逐位判断要跑 4 次。数字里 1 越少这个方案的优势越明显。不过话说回来在 10^4 这个数据范围内两种写法差别也就几十纳秒级别完全不影响 AC。真正有价值的不是谁更快而是你能不能在面试时把 n (n - 1) 的原理讲明白以及知道什么时候该选它。3. 核心原理二进制中 1 的数目到底怎么算得优雅3.1 为什么 n (n - 1) 能消掉最低位的 1很多人背下了这个公式但被问“为什么”时卡住。我尽量用最直观的方式讲清楚。你随便写一个二进制数比如 n 12二进制是 1100。n - 1 等于 11二进制是 1011。我们把两个数对齐看1100 1011 ------ 1000结果等于 8也就是 1000。原本 1100 最低位的那个 1 是在第三位从低往高数做完按位与之后这一位变成了 0而它右边的所有位本来都是 0相与之后还是 0。关键规律是n - 1 会把 n 最低位的 1 变成 0同时把这一位右边的所有 0 变成 1。这两部分再跟原来的 n 做与运算正好把最低位的 1 以及它右边的位全部清零而高位不变。脑子里可以想象成二进制里最右边的那个 1 像一个“分界线”n - 1 的作用是让这条分界线右边的位全部反转分界线本身从 1 变 0。和原数相与之后分界线及右侧全部归零。所以每执行一次 n n - 1就少一个 1。这个技巧在无数位运算题里都会用到比如判断一个数是不是 2 的幂可以用 n 0 and (n (n - 1)) 0因为 2 的幂的二进制表示里只有一个 1。3.2 动态规划查表一次算完全部数字还有一类写法是提前把 0 到某个范围内的所有数字的“1 的个数”都算出来存到数组里后面直接查表。LeetCode 第 338 题“比特位计数”就是这个思想的典型代表。递推公式很简单对于一个数字 i它的二进制等于 i 1 的二进制左移一位再加上最低位 i 1。所以ones[i] ones[i 1] (i 1)写成代码就是def count_ones_up_to(n: int) - List[int]: ones [0] * (n 1) for i in range(1, n 1): ones[i] ones[i 1] (i 1) return ones在这道题里可以用一个 10001 长度的数组把所有数对应的 1 的个数预处理好排序的时候直接取连 bin() 都省了。这个方案的思路不是为单个数字算得快而是为“大量连续数字”的场景准备的。你要是把数组最大值 max_val 拿到只预处理到 max_val比固定 10001 更省。3.3 不同语言里统计 1 的数目的基础设施很多语言的标准库已经提供了统计二进制中 1 的数目的函数从封装程度上各有差异我列个表格方便参考语言提供方式内部实现说明JavaInteger.bitCount(int)基于 SWAR 分治法常数级运算Gobits.OnesCount(uint)编译期可能被替换为 CPU 指令Cstd::bitset::count 或手写bitset 内部实现依赖库手写可控制Pythonint.bit_count()3.8Python 3.8 开始内置底层为 C 实现性能优秀JS手写或用 toString(2) 转字符串没有专门 API通常手写位运算这里提醒一下Python 在 3.8 之后有 int.bit_count()可以直接统计二进制中 1 的个数写法是 x.bit_count()。如果你刷题时用的是新版 Python这一行比 bin(x).count(1) 更高效。针对这道题key 函数可以直接写成 lambda x: (x.bit_count(), x)。Go 的 bits.OnesCount 是我在实际工程里用得比较多的它底层会尝试调用 CPU 的 POPCNT 指令统计速度极快这种“能用硬件指令就不用软件循环”的思路在做性能敏感的基础库时特别重要。3.4 这道题和二进制补码的关系有同学可能会问如果数组里有负数怎么办这就要提到二进制补码。在原题里 arr[i] 0所以不涉及负数。但在更广的位运算场景中比如 C 里统计一个负数二进制下 1 的数目你要注意负数在计算机里是用补码表示的-1 的 32 位二进制是全 1也就是 32 个 1。此时你如果直接把 n 右移C 的算术右移会在高位补符号位 1可能导致循环永远结束不了。所以处理负数时要么转成无符号整数要么固定循环 32 次。延伸一下二进制转十进制的时候很多人用 8421 码来记位权也就是从高位到低位依次对应 8、4、2、1这本质上就是 2^3、2^2、2^1、2^0。理解了这个位权结构再看二进制和补码就没那么神秘了。4. 进阶优化不用快排用计数排序把复杂度降到 O(n)4.1 观察数据特征前面几版方案虽然写法不同但排序部分都调用了系统的排序函数复杂度 O(n log n)。但如果我们仔细观察“1 的数目”这个排序键的取值是有限且很小的32 位整数最多只有 0 到 31 个 1。这才是这道题真正的突破口。既然排序键取值范围只有 32 种可能我们完全可以维护 32 个桶遍历数组时根据每个数字的 1 的个数放入对应的桶最后按桶编号从 0 到 31把每个桶里的数字排好序拼起来。每个桶内部的数字本身还要按数值升序但这里有个细节如果我们从原数组从左往右放入桶再对每个桶单独排序总复杂度是 O(n 32 * k log k)如果桶内直接再 sort整体还是 O(n log n)。问题来了能不能避免桶内快排能。因为我们可以先把这个数通过 sort 来完成但更彻底的办法是桶的数量已经足够多直接把每个数字同时作为桶内排序依据。实际上有个更简单的等价做法对原数组按数值升序排序之后再按 1 的个数做稳定排序。4.2 稳定排序思路排序算法有一个性质叫稳定性如果两个元素排序键相同稳定排序会保持它们在原数组里的相对顺序。利用这个性质我们可以分两步先按数值大小对数组升序排序再按“1 的数目”对数组做一次稳定排序。因为数值相同的元素已经排好了而“1 的数目”相同的元素在第一次数值排序中的相对顺序就是要的升序关系。稳定排序会保留这个相对顺序所以二次排序完成后天然满足题目的要求。用 Python 的 sorted 是最直接的体现arr.sort() arr.sort(keylambda x: x.bit_count())这里第一次 sort 是纯数值升序第二次 sort 指定了 key 为 bit_count而 Python 的 sort 是稳定的所以相同 1 的数目的元素仍然保持数值升序。这个两段式写法的复杂度仍然是 O(n log n)因为第一次 sort 是 O(n log n)。但如果换成手动实现稳定版本的基数排序就能把整体做到 O(n)。4.3 手动桶排序实现我们用一个长度为 32 的列表做桶但每个桶里先不排序而是只记录“有哪些数字”。为了达到 O(n)最靠谱的做法是先对整个数组按数值升序排序这是最耗时的部分再基于这个有序序列做稳定分桶。这样每个桶内天然有序拼接即可。其实还可以直接用前缀和做计数排序彻底不用在桶内排序。这里我给出一个比较实操的 Python 版本class Solution: def sortByBits(self, arr: List[int]) - List[int]: arr.sort() # 先按数值升序保证稳定性下桶内有序 buckets [[] for _ in range(32)] for num in arr: buckets[num.bit_count()].append(num) res [] for b in buckets: res.extend(b) return res第一次 arr.sort() 是 O(n log n)仍然是瓶颈。但这版代码比直接对每个数算 key 再 sort 更快的原因在于排序过程中比较器的计算量更小而且省去了反复调用 lambda 的开销。不过严格从复杂度的角度讲还是没有达到 O(n)。完整做到 O(n) 的方法是既然 arr[i] 的范围是 0 到 10^4我们可以先构建一个长度为 10001 的数组 onesones[x] 表示数字 x 的 1 的个数然后对这个 0 到 10000 的“数字”按 (ones[x], x) 做基数排序。但说实话工程上没必要绕这么大的弯子因为 n 最大 500快排耗时完全可以忽略。面试时你只要提一句“考虑到位数固定为 32 位可以用桶把复杂度优化到接近 O(n)”已经能体现水平了。4.4 复杂度对比速查方案时间复杂度空间复杂度推荐场景bin(x).count(1) 排序O(n log n * k)O(n)数据量小、追求代码简洁n (n - 1) 排序O(n log n * m)O(1)单个数能算代码可控位运算查表 DP 排序O(n R)O(R)数组范围已知且规整可预计算先数值排序再稳定分桶O(n log n)O(n)逻辑清晰面试易讲计数排序 / 基数排序O(n R)O(R)对性能有执念或想展示算法深度这里的 R 表示数据取值范围相关的常数比如 0 到 10000 就可以认为 R 10001。5. 实战中的坑我写这道题踩过的那些雷5.1 比较器返回值写反我第一次用 C 写这道题时lambda 里的比较逻辑写成了sort(arr.begin(), arr.end(), [](int a, int b) { int ca __builtin_popcount(a); int cb __builtin_popcount(b); return ca cb; // 忘了考虑数值相等的情况 });这样写当 ca ! cb 时是没问题的但当 ca cb 时这个比较器会返回 false在 C 的 sort 看来 a 和 b 就是“等价的”排序结果里它们可能会被打乱导致同样 1 的数目的数字没有按数值升序排列直接判错。正确写法应该是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; });C 的严格弱排序要求比较器必须有明确的优先级你把两个维度分开判断一行一行写清楚既避免出错也方便阅读。5.2 C lambda 的捕获列表坑有同学为了直接用预计算好的 ones 数组写了这样一段vectorint ones(10001); for (int i 1; i 10000; i) ones[i] ones[i 1] (i 1); sort(arr.begin(), arr.end(), [](int a, int b) { if (ones[a] ! ones[b]) return ones[a] ones[b]; return a b; });但 C lambda 默认不能访问外部局部变量编译时直接报错。需要在方括号里捕获它sort(arr.begin(), arr.end(), [](int a, int b) { ... });这个问题非常隐蔽因为编译器报错信息看起来像是类型不匹配新手容易在这里卡很久。我的习惯是只要 lambda 里用到外部变量直接写 [] 捕获所有引用简单粗暴除非是生产环境有性能洁癖再改成按需捕获。5.3 负数补码导致的死循环风险如果数组扩展到包含负数你再用 while(n) n 1 的方式统计 1 的个数就出问题了。C 里负数的右移是算术右移负数右移后高位补 1n 永远不会变成 0循环变成死循环。我实测过 -1 在 32 位下右移 100 次仍然是 -1。处理方式有两种一是转成 unsigned int让右移变成逻辑右移二是固定循环 32 次每次判断 n 1。Java 和 Python 因为语言设计不同没有这个问题但 C/C 和 JS 里都要小心。5.4 Python 里过度使用内置 lambda 的性能问题Python 的 sorted 在每次比较时都会调用 key 函数如果你写成 lambda x: (bin(x).count(1), x)那每个元素会被调用一次而不是比较一次调一次所以总开销其实不大。但如果你图省事用 list.sort(keycmp_to_key(...))那开销反而大得多。原因是 cmp_to_key 会把函数转成类对象比较时调用这个类性能远不如直接用 key 产生排序键后排序。我遇到很多同学因为习惯了其他语言的 comparator 写法在 Python 里也用 cmp_to_key其实没必要Python 的 key 方式是官方推荐的高效写法。6. 举一反三位运算技巧还能用在哪里6.1 判断一个数是不是 2 的整数次幂这是 n (n - 1) 最经典的应用。2 的幂的二进制表示只有一个 1比如 8 是 10008 - 1 是 0111相与之后是 0所以if n 0 and (n (n - 1)) 0: # n 是 2 的幂这个判断在分治算法、内存对齐、哈希表扩容等场景中很常见。我自己在写缓存容量对齐逻辑时经常用这个技巧检查一个数是不是友好的容量值。6.2 汉明距离和位运算加速LeetCode 第 461 题“汉明距离”就是求两个整数的二进制有多少位不同解法是先做异或再统计异或结果里 1 的个数def hammingDistance(x: int, y: int) - int: return (x ^ y).bit_count()这道题几乎可以看作是本题目一个延伸你学会了统计一个数的 1 的个数就等于学会了汉明距离的一半。我面试候选人的时候如果他能从“二进制下 1 的数目”自然地引申到异或和位计数说明他对位运算有一个体系化的理解而不是背了几道题。6.3 工程里的位图压缩实际工程中位运算最常见的应用是位图Bitmap和布隆过滤器。比如用 32 位整数存储 32 个布尔状态需要统计有多少个状态为真时就要计算这个整数的 1 的个数。我在做服务端埋点统计时用过一个 64 位整数表示 64 个功能开关每天统计开启数量时就靠 bits.OnesCount64一整个服务几百万次调用下来性能依然稳。回到这个题目本身它虽然简单却是一条很清晰的链路入口从算术思维到位运算思维从调用系统排序到理解排序原理从识别数据范围到设计计数排序。把这些东西吃透了再遇到别的“简单题”你就不会只满足于 AC 那一下的快感而是会去想它背后到底藏着什么可以复用的能力。如果非要分享一个我的个人习惯拿到这类题我会先写最直白、最容易读懂的版本保证正确性然后立刻在注释里写一版用位运算常量级优化的替代方案。刷题不是炫技而是用最合适的粒度解决问题。这道题你至少应该做到闭着眼睛把位运算统计 1 的数目的循环写出来因为它是很多后续题目最小的积木没有之一。