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

[nulIptr]

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

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

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

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

[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;

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