对于一个byte[] 数组，怎么计算比特位会比 O(8n)快？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

对于一个byte[] 数组，怎么计算比特位会比 O(8n)快？

对于一个byte[] 数组，怎么计算比特位会比 O(8n)快？# JobHunting - 待字闺中

d*e2017-08-28 07:08

1 楼

上周被问到一个计算某正整数的比特位, 比如 3 有2个比特位，我给秒了
然后被追问，如果输入是一个byte[] array，长度为n，问如何计算数组里全部的比特
位？我说挨个数，然后自然是 O(8n)，但是面试小哥说要更快的算法，也就是降低常数
项8，我想不出来了，请问有啥好办法？
我记得lc里有一个是数 1 ... n的连续整数的比特位，但是这题是给的byte[]数组

h*o2017-08-28 07:08

2 楼

用空间换时间，用一个256数组存一下每个byte比特位数。

z*n2017-08-28 07:08

3 楼

n -= n & -n 可以消掉最低bit 位，用这个方法可以降低常数项到每个byte平均bit数*
n，
当然最坏还是8n。

r*s2017-08-28 07:08

4 楼

POPCNT
原理应该也是查表

: n -= n

【在 z*********n 的大作中提到】

: n -= n & -n 可以消掉最低bit 位，用这个方法可以降低常数项到每个byte平均bit数*
: n，
: 当然最坏还是8n。

z*n2017-08-28 07:08

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*s2017-08-28 07:08

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