数组10000有16位元素,找到位设置(无限RAM) - 谷歌访谈

Question

最近在我的谷歌采访中提到了这一点,我提供了一个涉及位移的答案,并且是O(n),但她说这不是最快的方式.我不明白,有没有办法计算位集而不必迭代提供的整个位？

Answer 1

蛮力:10000*16*4 = 640,000 ops.(每个16位字的移位,比较,递增和迭代)

更快的方式:

我们可以构建表00-FF - >设置的位数.256*8*4 = 8096 ops

即我们构建一个表,我们计算每个字节设置的位数.

然后对于每个16位int,我们将它分成上下

for (n in array)
   byte lo = n & 0xFF; // lower 8-bits
   byte hi = n >> 8;   // higher 8-bits
   // simply add number of bits in the upper and lower parts 
   // of each 16-bits number
   // using the pre-calculated table
   k += table[lo] + table[hi];
}

迭代中共有60000个操作.即总共68096个操作.它虽然是O(n),但是不那么恒定(减少~9倍).

换句话说,我们计算每8位数的位数,然后将每个16位数分成两个8位,以便计算使用预建表设置的位.

Answer 2

(几乎)总是以更快的方式.阅读有关查找表的信息.