面试见闻，关于一个简单题目的算法和复杂度的讨论

[nulIptr]

题目是这个：
给定一个输入 n ，输出一个包含 n 个元素数组，数组中每个元素表示其索引的二进制形式中的数字 1 的个数，请给出对应算法并说明复杂度

依稀好像看过这个题，不确定到底有没有 o1 的数学解，我就说要是我的话肯定暴力数 0
面试官说给你提个醒能不能动态规划解这个题
我说没必要啊暴力数数也不慢，c 语言里面直接读内存，js 里可以位运算展开一下，最差情况也就是 32n 或者 64n 的复杂度。即使是 o1 的数学解也就是把 32n 降到 n ，讨论复杂度的时候本来就省略固定系数的

然后面试官就结束了提问环境，说我有啥问题要问的没然后结束了面试。

那么动态规划怎么更高效的解这个题呢？还是说我对 32n 的这个解释是有问题的？

[vacuitym]

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

[nulIptr]

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

[duality]

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

[kera0a]

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

[finalwave]

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

[sagaxu]

右移一位得到一个更小的数，这个数的 1 的个数已经算好了，加上当前最右位就是当前数字的 1 的个数

计算量是稍微小了一点点，但是空间从 O(1)变 O(n)了，如果是 10 亿个数呢，100 亿个呢

[Goooooos]

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

[Sawyerhou]

3 楼的递归是个好思路，说态度问题的也有道理，毕竟直接结束了面试

毕竟是算法题，暴力解不太合适吧

[MoYi123]

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

[misdake]

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

[misdake]

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

[codegenerator]

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

[main1234]

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

[main1234]

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

[main1234]

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

[zzblack]

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

[zhuxuanyu0720]

动态规划解法:


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)的时间复杂度。

[xiaozhaoz]

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

[xiaozhaoz]

@xiaozhaoz 错了，最后一种情况 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;
}

[Orlion]

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

[GrayXu]

算法题只是智力题

[majula]

去看了下 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;

不过既然题干都那么说了，还是别投机取巧了，老老实实动态规划吧