1

ビット単位/シフト操作を学習しようとしています。

以下のプログラムに出くわしましたが、以下のプログラムの AND 条件部分 (checker & (1 << val) を理解していません。最終的な値が 0 より大きいのはいつですか?誰かがそこで何が起こっているのか説明してもらえますか?

入力例: xyzz

出力例:

8388608値 0チェッカー 0最終値

16777216Value 8388608checker 0最終値

33554432Value 25165824checker 0最終値

33554432値 58720256チェッカー 33554432最終値

public static boolean isUniqueChars(String str) {
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i) - 'a';

            System.out.println((1 << val) + "Value");
            System.out.println((checker) + "checker");
            System.out.println(((checker & (1 << val))) + "final value\n");

            if ((checker & (1 << val)) > 0) {
                return false;
            } else {
                checker = checker | (1 << val);
            }
        }
        return true;
    }

}
4

2 に答える 2

6

OK、何が起こっているのかを確認するために:

int val = str.charAt(i) - 'a';

英語のアルファベットを想定すると、これは (小文字の) 文字の char 値を取得し、97 (「a」の char 値) を減算して、0 から 25 までの数値を生成します。大文字でこの関数を試さないでください.toLowerCase()。.charAt(i)

1 << valval左に1桁ビットシフトしています。たとえば、「x」(120 - 97 = 23、つまり... 1 << 23) の場合、バイナリ表現は次のようになります。00000000010000000000000000000000

OK、これまでのところ私と一緒ですか？

最初、チェッカーはすべて 0 のビットを持っているので、00000000000000000000000000000000

変数の代わりに数字を入れましょう。私たちのxチェックでは、ビット 23 がチェッカーに設定されていないため、どちらが等しいかにchecker & (1 << val)なります。00000000000000000000000000000000 & 0000000001000000000000000000000000000000000000000000000000000000

xが処理されると、ビット 23 をチェッカーに追加し、次の文字に進みます。今回y は、ビット 24 がチェッカーに設定されていないため、どちらが等しいかにchecker & (1 << val)なります。00000000010000000000000000000000 & 0000000010000000000000000000000000000000000000000000000000000000

最初のは、ビット 25 がチェッカーに設定されていないためz、checker & (1 << val)が00000000110000000000000000000000 & 00000001000000000000000000000000等しくなります。00000000000000000000000000000000

2 番目zのは、チェッカーでビット 25が設定されているため (10 進数の33554432または 2^25)にchecker & (1 << val)なり、したがって は になり、関数は を返します。00000001110000000000000000000000 & 0000000100000000000000000000000000000001000000000000000000000000> 0truefalse

于 2013-04-09T19:06:56.043 に答える
1

あなたの関数が行うことは、入力文字列のすべての文字が異なるかどうかを確認することだと思います。同じ (小文字の) 文字が複数回出現する場合は false を返します。

変数は、checkerこれまでに登場した文字を蓄積する一種のビット マップとして機能します。データ型intは 32 ビットで構成され、各文字 (26) に 1 ビットを割り当てるのに十分です。

この関数は、str のすべての文字をループします。行は、文字に応じてint val = str.charAt(i) - 'a';ある種の序数値を割り当てます('a' => 0、'b' => 1、'c' => 2 など)。val

この式1 << valは、(0..25) の範囲内の各 val をそのビット位置に割り当てます。したがって、文字「a」は 1 << 0 == 1 == 00000001 にマップされ、文字「d」は 1 << 3 == 00001000 にマップされます。各文字には、1 つのビットだけが設定され、他のすべてのビットがクリアされた一意のビット マスクが割り当てられます。

設定されているビットがチェッカーでも設定されている場合、式(checker & (1 << val))は正確に > 0 です1 << val(チェッカーには複数のビットが設定されている可能性があることに注意してください)。そうである場合、現在反復されている文字は以前に出現しており、関数は false を返します。それ以外の場合、現在の文字のビット マスクは、ビットごとの OR 演算子|を介して、アキュムレータとして機能するチェッカーに追加されます。すべての文字がループされ、どの文字も 2 回遭遇しなかった場合、関数は true を返します。関数は大文字やその他の文字を無視する場合があることに注意してください。

于 2013-04-09T19:07:53.687 に答える