1

よく聞かれる質問が、40億個の数字の中から欠けている数字を見つけようとしているようです。
推奨されるアプローチは、ビットセットを使用することです (メモリの制約が問題の一部である場合)。
投稿の例は次のとおりです。find-an-integer-not-among-ofour-billion-given-onesであり、SO の詳細にリンクすることもできます。

私の問題は次のとおりです。ビットセットのアプローチは、数値が負ではないことを暗黙的に想定しているようです。リンク先の投稿の例として、Java で次のコード スニペットがあります。 

int radix = 8; 
byte[] bitfield = new byte[0xffffffff/radix]; 
void F() throws FileNotFoundException{ 
    Scanner in = new Scanner(new FileReader("a.txt")); 
    while(in.hasNextInt()){ 
        int n = in.nextInt(); 
        bitfield[n/radix] |= (1 << (n%radix)); 
    } 

    for(int i = 0; i< bitfield.lenght; i++){ 
        for(int j =0; j<radix; j++){ 
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j); 
        } 
    } 
}

しかし Java では、すべての整数が署名されています。その結果、投稿されたコードは負の数で壊れます。これint n = in.nextInt();により、負の値が返される場合があります。

だから、どういうわけか私の混乱は、この種の問題/演習の約2つの部分であると思います:
1)ビットセットを使用して負の数を表すことはできますか? どのように？
2) 問題の解決策は、何らかの形で特定のプログラミング言語に関連していますか? たとえば、符号なしの数値があるC++では、範囲が負ではないという仮定を受け入れることができると思います。

誰かがこれを理解するのを手伝ってくれませんか?

4

2 に答える 2

4

試す

long n = in.nextInt() & 0xFFFFFFFFL; 
bitfield[(int) (n/radix)] |= (1 << (n%radix));

または使用

final int bits = 3; 

bitfield[(int) (n >>> bits)] |= (1 << (n & ((1 << bits) -1)));

後で

System.out.print((int) (i*radix+j));

andint[]またはを使用long[]すると、byte[]

于 2012-04-16T09:35:21.797 に答える
3

明らかな解決策があります。すべての数値には特定の範囲 [a, b) があることがわかっているので、すべての数値に下限を追加するだけで、正の数値が保証されます。

これは任意の長い数値では機能しませんが、通常は問題ありません

于 2012-04-16T09:30:53.863 に答える