我很多次在刷题群里看到有人一看到“根据数字二进制下 1 的数目排序”这个题名就发怵，心想：数字排序我会，但二进制下的“1的数目”是个什么东西？其实把这句话拆开看，核心就三个词：二进制、1的数目、排序。这三件事单独拎出来都不难，放到一道题里考的就是你把这些基础能力组合起来解决实际问题的熟练度。
这个题目是 LeetCode 第 1356 题，难度是简单，但它非常典型：用到的知识点包括二进制位计数、多关键字排序、比较器写法，进阶一点还能牵扯出计数排序这类不需要比较的排序思路。不管你是准备面试的求职者，还是刚学完基础语法想找点题练手的新手，这道题都值得认真过一遍。我自己在实际工作中写数据处理脚本时，也经常遇到类似“先按某个隐含属性分组，再按另一维度排序”的需求，这道题的本质和那些真实场景是一致的。
1. 题目到底在问什么：题意拆解与核心考点
1.1 输入输出长什么样
先看最原始的题目格式。给你一个整数数组 arr，要求你把这个数组排序，排序规则是：先按每个数字的二进制表示中“1”的个数从少到多排序，如果两个数字二进制下 1 的个数相同，就按数字本身从小到大排序。
举个例子，输入 arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]：
- 0 的二进制是 0，1 的个数是 0；
- 1 的二进制是 1，1 的个数是 1；
- 2 的二进制是 10，1 的个数是 1；
- 3 的二进制是 11，1 的个数是 2；
- 4 的二进制是 100，1 的个数是 1；
- 5 的二进制是 101，1 的个数是 2；
- 6 的二进制是 110，1 的个数是 2；
- 7 的二进制是 111，1 的个数是 3；
- 8 的二进制是 1000，1 的个数是 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() 加字符串 count：
class Solution: def sortByBits(self, arr: List[int]) -> List[int]: return sorted(arr, key=lambda 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 的数目的函数，从封装程度上各有差异，我列个表格方便参考：
| 语言 | 提供方式 | 内部实现说明 |
|---|---|---|
| Java | Integer.bitCount(int) | 基于 SWAR 分治法，常数级运算 |
| Go | bits.OnesCount(uint) | 编译期可能被替换为 CPU 指令 |
| C++ | std::bitset::count 或手写 | bitset 内部实现依赖库，手写可控制 |
| Python | int.bit_count()（3.8+） | Python 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(key=lambda 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 的数组 ones，ones[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 数组，写了这样一段：
vector<int> 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++ 里负数的右移是算术右移，负数右移后高位补 1，n 永远不会变成 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(key=cmp_to_key(...))，那开销反而大得多。原因是 cmp_to_key 会把函数转成类对象，比较时调用这个类，性能远不如直接用 key 产生排序键后排序。我遇到很多同学因为习惯了其他语言的 comparator 写法，在 Python 里也用 cmp_to_key，其实没必要，Python 的 key 方式是官方推荐的高效写法。
6. 举一反三：位运算技巧还能用在哪里
6.1 判断一个数是不是 2 的整数次幂
这是 n & (n - 1) 最经典的应用。2 的幂的二进制表示只有一个 1，比如 8 是 1000，8 - 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 的数目的循环写出来，因为它是很多后续题目最小的积木，没有之一。
