[解決済み] すべての文字が一意であるかどうかを判断するためのビットベクトルの使用方法を説明します。

質問

ビットベクターがどのように作用してこれを行うのか混乱しています（ビットベクターにはあまり慣れていません）。以下は、与えられたコードです。どなたか教えていただけませんか？

public static boolean isUniqueChars(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;
        checker |= (1 << val);
    }
    return true;
}

特に、何 checker は何をしているのでしょうか？

解決方法は？

int checker は、ここではビットのストレージとして使用されています。整数値の各ビットはフラグとして扱えるので、最終的には int はビット(フラグ)の配列です。コード中の各ビットは、そのビットのインデックスを持つ文字が文字列中に見つかったかどうかを示しています。同じ理由で、ビットベクトルも使えます。 int . 両者の違いは2つあります。

• サイズ . int は固定サイズで、通常は4バイト、つまり8*4=32ビット(フラグ)です。ビットベクタは通常、異なるサイズにすることができますし、コンストラクタでサイズを指定する必要があります。

• API . ビットベクターを使えば、おそらく次のような読みやすいコードになるでしょう。

  vector.SetFlag(4, true); // set flag at index 4 as true

  について int の場合、下位のビットロジックコードになります。

  checker |= (1 << 5); // set flag at index 5 to true

また、おそらく int というのも、ビットを使った操作は非常に低レベルで、CPUがそのまま実行できるためです。BitVectorを使うと、暗号化されたコードを書く必要がなくなり、フラグをより多く格納できるようになります。

参考までに、ビットベクターはbitSetまたはbitArrayとも呼ばれます。このデータ構造について、さまざまな言語やプラットフォームでのリンクを紹介します。

• CPPです。 ビットセット
• Javaです。 ビットセット
• C#: ビットベクター32 と ビット配列