题目是这个：给定一个输入 n ，输出一个包含 n 个元素数组，数组中每个元素表示其索引的二进制形式中的数字 1 的个数，请给出对应算法并说明复杂度依稀好像看过这个题，不确定到底有没有 o1 的数学解，我就说要是我的话肯定暴力数 0面试官说给你提个醒能不能动态规划解这个题我说没必要啊暴力数数也不慢，c 语言里面直接读内存，js 里可以位运算展开一下，最差情况也就是 32n 或者 64n 的复杂度。即使是 o1 的数学解也就是把 32n 降到 n ，讨论复杂度的时候本来就省略固定系数的然后面试官就结束了提问环境，说我有啥问题要问的没然后结束了面试。那么动态规划怎么更高效的解这个题呢？还是说我对 32n 的这个解释是有问题的？

面试官要动态规划你就回答动态规划，除非你不会

就这个题来说我还真没想出来怎么动态规划…

从 0 开始处理，设 A[0] = 0For (i = 1 ... n) 设 i 的最高非零位为 d 位 A[i] = A[i - (1<<(d-1))] + 1

有没有可能都不是算法的问题，面试官只是觉得你不好沟通了。会觉得等到要给你需求时你也来一句"没必要啊"怎么办现在牛马太多了，一点点不合意就直接下一位了

DP[ i ] = DP[ floor(i / 2) ] + (i & 1)

右移一位得到一个更小的数，这个数的 1 的个数已经算好了，加上当前最右位就是当前数字的 1 的个数计算量是稍微小了一点点，但是空间从 O(1)变 O(n)了，如果是 10 亿个数呢，100 亿个呢

这道题目是返回数组，所以这个结果的空间可以忽略

3 楼的递归是个好思路，说态度问题的也有道理，毕竟直接结束了面试毕竟是算法题，暴力解不太合适吧

2 种可能性,1. 你题目理解错了2. 面试官 sb

这个题挺有意思，再往底层走还可以问多线程和 cpu 缓存相关的内容，如何优化到极致

如果把统计 1 的数量改成统计所有质因数之和，会更有意思一点

这题你理解错了，就是个位运算的题目但是如果你是面前端，那就是面试官的问题

这里不就是奇数和偶数判断一下么，如果元素为 i ，i 如果是奇数则 i 的二进制 1 为 i-1 的二进制 1 个数+1 ，如果是偶数则是 i/2 的二进制数

leetcode.cn/problems/counting-bits/description/?envType=study-plan-v2&envId=leetcode-75

对于奇数，二进制表示中奇数一定比前面的偶数多一个 1 ，多的就是最低位的 1如 0 = 0 ，1 = 1 ，2=10 ，3=11对于偶数，二进制表示中偶数一定和除以 2 之后的那个数一样多，因为最低位是 0 ，除以 2 就是右移一位2 = 10 ，4=100 ，8=1000

这个“没必要啊”属实绷不住了，面试官是想通过这个题考查你的算法能力，你直接暴力了，那他面试评价咋写？面试是一个候选人展示自己的过程，面试官的题目难度其实是决定了你能展示出来的能力的上限。你这句没必要啊。。是我面你我也直接结束了

动态规划解法:def countBits(n): result = [0] (n+1) offset = 1 for i in range(1, n+1): if offset 2 == i: offset *= 2 result[i] = result[i - offset] + 1 return result[:n]offset 代表的是该区间内最小数字(即起始数字)的二进制位数。offset 变量代表当前位置所属的那个长度为 offset 的区间的起始点。举例来说,当 offset=1 时,表示区间[0,1];当 offset=2 时,表示区间[2,3];当 offset=4 时,表示区间[4,7].有一个数学规律对于任意一个数字 x,如果 x 和 x+1 的二进制位数相同,那么 x 和 x+1 对应的 1 的个数,最多只相差 1 ，这个特性就被用来推导 result 数组中相邻两个数字对应的 1 的个数所以通过区间分治的方式,算法可以高效地确定每一个区间的起点,并利用相邻区间的结果推导出当前区间每个数字对应的 1 的个数,从而达到 O(n)的时间复杂度。

根据前一个数 的三种情况：- 最后一位 0 ，1 的个数 + 1- 前一个数全 1 ，1 的个数回到 1 ，实现方法：记住前一个数二进制长度，“~前一个数 & （ 0x1<<位数）- 1” == 0- 其他情况，1 的个数不变

错了，最后一种情况 1 的个数会变。看到过一个算法，可以算一个 32bits 的 1 个数。int count(unsigned x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; x = x + (x >> 8); x = x + (x >> 16); return x & 0x0000003F; }

leetcode 338 原题，动态规划的转移方程：bits[i] = bits[i >> 1] + (i & 1)。

算法题只是智力题

去看了下 leetcode 338 ，果然是不让用 popcnt intrinsic 的，不然就是一个非常 trivial 的 O(n)其实就算不让用 intrinsic ，popcnt 也有 branchless 且 lut-less 的 trivial 实现。参考 Bit Twiddling Hacks：v = v - ((v >> 1) & 0x55555555);v = (v & 0x33333333) + ((v >> 2) & 0x33333333);c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;不过既然题干都那么说了，还是别投机取巧了，老老实实动态规划吧