一个Fail的面经

上周被问到一个计算 某正整数的比特位, 比如 3 有2个 比特位，我给秒了

然后被追问，如果输入是一个byte[] array，长度为n，问如何计算数组里全部的比特
位？我说挨个数，然后自然是 O(8n)，但是面试小哥说要更快的算法，也就是降低常数
项8，我想不出来了，请问有啥好办法？

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

tica, sans-serif">        sum += n;
    }
    cout<<sum<<endl;
}

或许可以暴力＋记忆来稍微提速，比如算过3，求7可以提速

因为byte只有8个比特位, 也就是说只有0-255, 可不可以算出数组里面每个数的个数O(n), 然后再查表得到每个数的比特位个数 * 数的个数, 然后加起来. 因为只有256个数, 所以第二步是constant time. 最后时间复杂度就是就是1 * n

https://stackoverflow.com/a/25808559/3345261

楼上正解，其实可以把8位拆成4位+4位，然后四位bits一共16种可能性，构造一个长度为16的数组供查询即可。So basically, it's O(n)

楼上的意思是，每个0-255的数，都能通过查表得到它的比特位的数量，然后乘以对应的重复数量？