21

这是我最近在谷歌采访中提出的问题，我提供了一个涉及位移的答案，并且是 O(n)，但她说这不是最快的方法。我不明白，有没有办法计算所设置的位而不必遍历提供的整个位？

4

5 回答 5

19

蛮力：10000 * 16 * 4 = 640,000 次操作。（每个 16 位字的移位、比较、递增和迭代）

更快的方式：

我们可以建立表 00-FF -> 设置的位数。256 * 8 * 4 = 8096 次操作

即，我们建立一个表格，我们为每个字节计算一组位。

然后对于每个 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 位，以便计算使用预建表设置的位。

于 2012-04-05T00:33:20.343 回答
6

（几乎）总是有更快的方法。阅读有关查找表的信息。

于 2012-04-05T00:20:54.727 回答
3

当被问到这个问题时，我不知道正确答案是什么，但我相信今天解决这个问题最明智的方法是使用POPCNT指令。具体来说，您应该使用64 位版本。由于我们只需要设置位的总数，因此我们不关心 16 位元素之间的边界。由于 32 位和 64 位POPCNT指令同样快，因此您应该使用 64 位版本来计算每个周期的四个元素的位数。

于 2015-03-17T02:08:23.120 回答
0

我刚刚用Java实现了它：

import java.util.Random;


public class Main {

static int array_size = 1024;
static int[] array = new int[array_size];
static int[] table = new int[257];
static int total_bits_in_the_array = 0;

private static void create_table(){
    int i;
    int bits_set = 0;

    for (i = 0 ; i <= 256 ; i++){
        bits_set = 0;
        for (int z = 0; z <= 8 ; z++){
            bits_set += i>>z & 0x1;
        }
    table[i] = bits_set;
    //System.out.println("i = " + i + " bits_set = " + bits_set);
    }



}

public static void main(String args[]){
        create_table();
        fill_array();
        parse_array();
        System.out.println("The amount of bits in the array is: " + total_bits_in_the_array);
}


private static void parse_array() {
    int current;

    for (int i = 0; i < array.length; i++){
        current = array[i];

        int down = current & 0xff; 
        int up = current & 0xff00;

        int sum = table[up] + table[down];

        total_bits_in_the_array += sum;
    }       
}

private static void fill_array() {
    Random ran = new Random();

    for (int i = 0; i < array.length; i++){
        array[i] = Math.abs(ran.nextInt()%512);
    }

}
}

也在https://github.com/leitao/bits-in-a-16-bits-integer-array/blob/master/Main.java

于 2015-03-16T20:51:46.980 回答
0

您可以预先计算以字节为单位的位计数，然后将其用于查找。如果您做出某些假设，它会更快。

操作数（仅计算，不读取输入）应采用以下

换档方法：

对于每个字节：2 次操作（移位、加法）乘以 16 位 = 32 次操作，0 次内存访问次数 10000 = 320 000 次操作 + 0 次内存访问

预计算方法：

255 次 2 次操作（移位、加法）乘以 8 位 = 4080 次操作 + 255 次内存访问（写入结果）

对于每个字节：2 ops（计算地址）+ 2 mem 访问 + op（添加结果）= 30 000 ops + 20 000 mem 访问

总计 30 480 个操作 + 20 255 个内存访问

所以更多的内存访问和更少的操作

因此，假设其他一切都相同，如果我们可以假设内存访问比操作快 (320 000 - 30 480)/20 255 = 14.29 倍，那么 10 000 字节的预计算会更快

如果您独自在一个相当现代的盒子上的专用内核上，这可能是正确的，因为 255 字节应该适合缓存。如果您开始出现缓存未命中，则该假设可能不再成立。

此外，该数学假设指针算术和直接内存访问以及原子操作和原子内存访问。根据您选择的语言（显然，根据之前的答案，您选择的编译器切换），该假设可能不成立。

最后，如果您考虑可扩展性，事情会变得更有趣：移位可以轻松地并行化到多达 10000 个内核上，但不一定要进行预计算。然而，随着字节数的增加，查找变得越来越有利。

所以，简而言之。是的，在相当合理的假设下，预计算会更快，但不，不能保证会更快。

于 2017-01-24T07:59:06.570 回答