21

これは最近のGoogleのインタビューで尋ねられ、ビットシフトを含むO（n）の回答を提供しましたが、これはそれを実行するための最速の方法ではないと彼女は言いました。わかりません。提供されたビット全体を反復処理せずに、設定されたビットをカウントする方法はありますか？

4

5 に答える 5

19

ブルートフォース：10000 * 16 * 4 =640,000ops。（16ビットワードごとにシフト、比較、インクリメント、反復）

より速い方法：

テーブル00-FF->設定されたビット数を作成できます。256 * 8 * 4 = 8096 ops

つまり、バイトごとに設定されたビット数を計算するテーブルを作成します。

次に、16ビット整数ごとにそれを上下に分割します

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];
}

反復で合計60000ops。つまり、合計68096opsです。ただし、O（n）ですが、定数は少なくなります（〜9分の1）。

つまり、8ビットの数値ごとにビット数を計算し、事前に作成されたテーブルを使用して設定されたビットをカウントするために、各16ビットの数値を2つの8ビットに分割します。

于 2012-04-05T00:33:20.343 に答える
6

（ほとんど）常により速い方法があります。ルックアップテーブルについて読んでください。

于 2012-04-05T00:20:54.727 に答える
3

この質問をしたときの正解はわかりませんが、今日これを解決する最も賢明な方法は、POPCNT指示を使用することだと思います。具体的には、64ビットバージョンを使用する必要があります。セットビットの総数が必要なだけなので、16ビット要素間の境界は重要ではありません。32ビット命令と64ビットPOPCNT命令は同等に高速であるため、64ビットバージョンを使用して、サイクルごとに4要素分のビットをカウントする必要があります。

于 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 ops（shift、add）x16ビット=32 ops、0memアクセス時間10000= 320 000 ops + 0 mem access

事前計算アプローチ：

255 x 2 ops（シフト、追加）x8ビット=4080 ops + 255 memアクセス（結果を書き込む）

バイトごとに：2 ops（計算アドレス）+ 2 mem access + op（結果を追加）= 30 000 ops + 20 000 mem access

合計30480ops + 20255memアクセス

したがって、より少ない操作でより多くのメモリアクセスが可能になります

したがって、他のすべてが等しいと仮定すると、メモリアクセスが操作よりも（320 000-30 480）/ 20 255 = 14.29の係数で高速であると想定できる場合、10000バイトの事前計算は高速です。

これは、255バイトがキャッシュに収まるはずなので、適度に最新のボックスの専用コアを使用している場合はおそらく当てはまります。キャッシュミスが発生し始めると、その仮定が成り立たなくなる可能性があります。

また、この計算では、ポインタ演算とダイレクトメモリアクセス、およびアトミック操作とアトミックメモリアクセスを想定しています。選択した言語によっては（そして、明らかに、以前の回答に基づいて、コンパイラーの切り替えの選択）、その仮定は成り立たない場合があります。

最後に、スケーラビリティを考慮すると、事態はさらに興味深いものになります。シフトは最大10000コアに簡単に並列化できますが、事前計算は必ずしも必要ではありません。ただし、バイト数が増えると、ルックアップはますます有利になります。

つまり、要するに。はい、かなり合理的な仮定の下では事前計算が高速ですが、いいえ、高速であるとは限りません。

于 2017-01-24T07:59:06.570 に答える