d********e
发帖数: 321 | 1 上周被问到一个计算 某正整数的比特位, 比如 3 有2个 比特位，我给秒了
然后被追问，如果输入是一个byte[] array，长度为n，问如何计算数组里全部的比特
位？我说挨个数，然后自然是 O(8n)，但是面试小哥说要更快的算法，也就是降低常数
项8，我想不出来了，请问有啥好办法？
我记得lc里有一个是数 1 ... n的连续整数的比特位，但是这题是给的byte[]数组 | h*******o
发帖数: 778 | 2 用空间换时间，用一个256数组存一下每个byte比特位数。 | z*********n
发帖数: 1451 | 3 n -= n & -n 可以消掉最低bit 位，用这个方法可以降低常数项到每个byte平均bit数*
n，
当然最坏还是8n。 | r*****s
发帖数: 1815 | 4 POPCNT
原理应该也是查表
: n -= n
【在 z*********n 的大作中提到】
: n -= n & -n 可以消掉最低bit 位，用这个方法可以降低常数项到每个byte平均bit数*
: n，
: 当然最坏还是8n。
| z*********n
发帖数: 1451 | 5 不查表的话，上个面试不会考的做法，O(lg8n) = O(3n)的：
int main()
{
vector arr = {1,2,3,4,5,6,7,8,9,255};
int sum = 0;
for (auto n : arr)
{
n = (n & 0x55555555U) + ((n >> 1) & 0x55555555U);
n = (n & 0x33333333U) + ((n >> 2) & 0x33333333U);
n = (n & 0x0f0f0f0fU) + ((n >> 4) & 0x0f0f0f0fU);
sum += n;
}
cout<
} | r*****s
发帖数: 1815 | 6 popcnt指令集里没有的时候_mm_popcnt_u32就退化成这个。。
: 不查表的话，上个面试不会考的做法，O(lg8n) = O(3n)的：
: int main()
: {
: vector arr = {1,2,3,4,5,6,7,8,9,255};
: int sum = 0;
: for (auto n : arr)
: {
: n = (n
【在 z*********n 的大作中提到】
: 不查表的话，上个面试不会考的做法，O(lg8n) = O(3n)的：
: int main()
: {
: vector arr = {1,2,3,4,5,6,7,8,9,255};
: int sum = 0;
: for (auto n : arr)
: {
: n = (n & 0x55555555U) + ((n >> 1) & 0x55555555U);
: n = (n & 0x33333333U) + ((n >> 2) & 0x33333333U);
: n = (n & 0x0f0f0f0fU) + ((n >> 4) & 0x0f0f0f0fU);
|
|
