文字列内の一意の文字を見つける際のビットベクトルの使い方を理解する

Question

ビットベクトルを使って文字列内で一意の文字を見つける次のコードがあります。私たちはそれが小文字だけでASCII文字セットだと仮定します。

以下のビットベクトルの使用を理解するのは苦労しています。プログラムをデバッグした後でも、各ループの後に変更変数が続きます。左1でのval（文字列の各文字のint型の表現）をシフトして（0に初期化）チェッカーでそれをAND'ingし、他のブロックでそれを論理和（OR）の目的は何

// assuming that the characters range from a-z 
static boolean isUniqueBitVector(String str) { 
    int checker = 0; 

    for(int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i) - 'a'; 

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

。

Answer 1

checkerは32ビットの整数で、各文字のフラグを格納する最下位ビットはa-zです。文字は一度だけ非一意である可能性があるため、これにビットを使用できます。

int val = str.charAt(i) - 'a';は、現在の文字に対応するビットのインデックスを計算します。入力のみa-zを含ん仮定の出番である。valは、一般的にゼロと

25の間の数になり、(1 << val)が選択された文字に対応するビットです。 <<は左シフト演算子です。これは1を移動するために使用され、1ビットだけがオンになり、valの位置が左に移動します。たとえば、1<<3は8になります。実際、左シフトは2の累乗に掛けることに相当します。

(checker & (1 << val))選択ビットがオンかどうかを確認します。 &演算子は、ビットごとにと呼ばれます。これは2つの数字を結合し、両方にあるビットをオンに設定します。 1 << valは、単一ビットのみがオンになっていることを覚えておいてください。唯一の方法は、checkerが0以外の値になることです。checkerにはすでに同じビットがオンになっています。その場合、手紙が繰り返されているので、我々はfalseを返す。

新しい文字が見つかった場合は、checkerの正しいビットをオンにする必要があります。これはchecker |= (1 << val);の機能です。ビットまたは演算子|は、いずれかのオペランドでオンの場合、結果のビットをオンにします。ここでも、1 << valには1ビットしかありません。したがって、またはの結果はcheckerを複製し、その1ビットをオンにします（既にオンになっているかどうかにかかわらず）。

ここに表示されている操作はすべて、非常に一般的なイディオムです。うまくいけば私の説明は何らかの形であなたを助けてくれました。なぜなら、単純なビットのコードでは似たようなことがほぼ確実に見られるからです。