これを行うためにビットベクトルがどのように機能するかについて私は混乱しています（ビットベクトルにあまり精通していません）。これが与えられたコードです。誰かが私にこれを教えてもらえますか？
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ですか？
私が読んでいるのと同じ本からこのコードを入手したのではないかと疑っています...ここのコード自体は、演算子-| =、＆、<<によって通常は使用されないほど不可解ではありません私たち素人-著者は、プロセスを説明するのに余分な時間を費やすことも、ここに含まれる実際のメカニズムが何であるかを気にしませんでした。私は最初はこのスレッドの前の答えに満足していましたが、抽象的なレベルでしかありませんでした。もっと具体的な説明が必要だと感じたので、戻ってきました。説明がないので、いつも不安になります。
この演算子<<は左ビット単位のシフターであり、その数値またはオペランドのバイナリ表現を取得し、バイナリのみの10進数のように、右側のオペランドまたは数値で指定された多くの場所にシフトします。10を底としない多くの場所を上に移動すると、2を底で乗算します。したがって、右側の数値は指数であり、左側の数値は2の底の倍数です。
この演算子|=（ビット単位のOR代入と呼ばれます）は、左側のオペランドを取得し、右側のオペランドを使用して、結果を左側のオペランドに割り当てます（x |=yはx=x | yと同等です）。同様に、演算子（'＆'）は'および'演算子の左側と右側になります。これにはビット単位のAND割り当てもあります（x＆=yはx= x＆yと同等です）。
checker |= (1 << val)したがって、ここにあるのは、チェッカーが文字の指定されたバイナリ値を取得または取得するたびに32ビットの2進数で格納され、対応するビットがtrueに設定されているハッシュテーブルです。文字の値はチェッカー（checker & (1 << val)) > 0）で「d」されます。0より大きい場合は、重複があることがわかります。これは、2つの同一のビットがtrueに設定され、「d」が一緒になってtrueまたは「1」を返すためです。
それぞれが小文字に対応する26のバイナリの場所があります-著者は、文字列には小文字のみが含まれていると仮定しました-これは、消費する場所が6つ（32ビット整数）残っているためです-そして私たちよりも衝突する
00000000000000000000000000000001 a 2^0
00000000000000000000000000000010 b 2^1
00000000000000000000000000000100 c 2^2
00000000000000000000000000001000 d 2^3
00000000000000000000000000010000 e 2^4
00000000000000000000000000100000 f 2^5
00000000000000000000000001000000 g 2^6
00000000000000000000000010000000 h 2^7
00000000000000000000000100000000 i 2^8
00000000000000000000001000000000 j 2^9
00000000000000000000010000000000 k 2^10
00000000000000000000100000000000 l 2^11
00000000000000000001000000000000 m 2^12
00000000000000000010000000000000 n 2^13
00000000000000000100000000000000 o 2^14
00000000000000001000000000000000 p 2^15
00000000000000010000000000000000 q 2^16
00000000000000100000000000000000 r 2^17
00000000000001000000000000000000 s 2^18
00000000000010000000000000000000 t 2^19
00000000000100000000000000000000 u 2^20
00000000001000000000000000000000 v 2^21
00000000010000000000000000000000 w 2^22
00000000100000000000000000000000 x 2^23
00000001000000000000000000000000 y 2^24
00000010000000000000000000000000 z 2^25
したがって、入力文字列'azya'の場合、段階的に移動します
文字列'a'
a =00000000000000000000000000000001
checker=00000000000000000000000000000000
checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001
a and checker=0 no dupes condition
文字列'az'
checker=00000000000000000000000000000001
z =00000010000000000000000000000000
z and checker=0 no dupes
checker=z or checker;
// checker now becomes 00000010000000000000000000000001
文字列'azy'
checker= 00000010000000000000000000000001
y = 00000001000000000000000000000000
checker and y=0 no dupes condition
checker= checker or y;
// checker now becomes = 00000011000000000000000000000001
文字列'azya'
checker= 00000011000000000000000000000001
a = 00000000000000000000000000000001
a and checker=1 we have a dupe
今、それは重複を宣言します
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としても知られています。さまざまな言語/プラットフォームのこのデータ構造へのリンクは次のとおりです。
これらの答えはすべて、これがどのように機能するかを説明していると思いますが、いくつかの変数の名前を変更し、他の変数を追加し、それにコメントを追加することによって、私がそれをよりよく見た方法についての私の入力を与えたいと思いました：
public static boolean isUniqueChars(String str) {
/*
checker is the bit array, it will have a 1 on the character index that
has appeared before and a 0 if the character has not appeared, you
can see this number initialized as 32 0 bits:
00000000 00000000 00000000 00000000
*/
int checker = 0;
//loop through each String character
for (int i = 0; i < str.length(); ++i) {
/*
a through z in ASCII are charactets numbered 97 through 122, 26 characters total
with this, you get a number between 0 and 25 to represent each character index
0 for 'a' and 25 for 'z'
renamed 'val' as 'characterIndex' to be more descriptive
*/
int characterIndex = str.charAt(i) - 'a'; //char 'a' would get 0 and char 'z' would get 26
/*
created a new variable to make things clearer 'singleBitOnPosition'
It is used to calculate a number that represents the bit value of having that
character index as a 1 and the rest as a 0, this is achieved
by getting the single digit 1 and shifting it to the left as many
times as the character index requires
e.g. character 'd'
00000000 00000000 00000000 00000001
Shift 3 spaces to the left (<<) because 'd' index is number 3
1 shift: 00000000 00000000 00000000 00000010
2 shift: 00000000 00000000 00000000 00000100
3 shift: 00000000 00000000 00000000 00001000
Therefore the number representing 'd' is
00000000 00000000 00000000 00001000
*/
int singleBitOnPosition = 1 << characterIndex;
/*
This peforms an AND between the checker, which is the bit array
containing everything that has been found before and the number
representing the bit that will be turned on for this particular
character. e.g.
if we have already seen 'a', 'b' and 'd', checker will have:
checker = 00000000 00000000 00000000 00001011
And if we see 'b' again:
'b' = 00000000 00000000 00000000 00000010
it will do the following:
00000000 00000000 00000000 00001011
& (AND)
00000000 00000000 00000000 00000010
-----------------------------------
00000000 00000000 00000000 00000010
Since this number is different than '0' it means that the character
was seen before, because on that character index we already have a
1 bit value
*/
if ((checker & singleBitOnPosition) > 0) {
return false;
}
/*
Remember that
checker |= singleBitOnPosition is the same as
checker = checker | singleBitOnPosition
Sometimes it is easier to see it expanded like that.
What this achieves is that it builds the checker to have the new
value it hasnt seen, by doing an OR between checker and the value
representing this character index as a 1. e.g.
If the character is 'f' and the checker has seen 'g' and 'a', the
following will happen
'f' = 00000000 00000000 00000000 00100000
checker(seen 'a' and 'g' so far) = 00000000 00000000 00000000 01000001
00000000 00000000 00000000 00100000
| (OR)
00000000 00000000 00000000 01000001
-----------------------------------
00000000 00000000 00000000 01100001
Therefore getting a new checker as 00000000 00000000 00000000 01100001
*/
checker |= singleBitOnPosition;
}
return true;
}
また、あなたの例は「Cracking The Code Interview 」という本からのものであり、私の答えはこの文脈に関連していると思います。
このアルゴリズムを使用して問題を解決するには、aからz（小文字）までの文字のみを渡すことを認める必要があります。
26文字しかなく、これらは使用するエンコーディングテーブルで適切にソートされているため、これにより、すべての潜在的な差異str.charAt(i) - 'a'が32（int変数のサイズ）よりも低くなることが保証されますchecker。
Snowbearで説明されているように、checker変数をビットの配列として使用しようとしています。例を挙げてアプローチしましょう：
まあ言ってみれば
str equals "test"
チェッカー==0（00000000000000000000000000000000）
In ASCII, val = str.charAt(i) - 'a' = 116 - 97 = 19
What about 1 << val ?
1 == 00000000000000000000000000000001
1 << 19 == 00000000000010000000000000000000
checker |= (1 << val) means checker = checker | (1 << val)
so checker = 00000000000000000000000000000000 | 00000000000010000000000000000000
checker == 524288 (00000000000010000000000000000000)
チェッカー==524288（00000000000010000000000000000000）
val = 101 - 97 = 4
1 == 00000000000000000000000000000001
1 << 4 == 00000000000000000000000000010000
checker |= (1 << val)
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)
など..条件を介して特定の文字のチェッカーにすでに設定されているビットが見つかるまで
(checker & (1 << val)) > 0
それが役に立てば幸い
上記のIvanの答えを読むことは私を本当に助けてくれましたが、私はそれを少し違った言い方をします。
<<inは(1 << val)ビットシフト演算子です。それは1（バイナリでは000000001、必要な数の先行ゼロを含む/として表され、メモリによって割り当てられます）、valスペースによって左にシフトします。azのみを想定し、毎回減算aするため、各文字の値は0〜25になります。これは、checker整数のブール表現の右からのその文字のインデックスになります。これは、時間1を左に移動するためchecker valです。
各チェックの最後に、|=オペレーターが表示されます。これにより、2つの2進数がマージされ、そのインデックスのいずれかのオペランドにaが存在する場合は、すべて0の'が'に置き換えられます。ここで、これは、が存在する場合は常に、にコピーされ、既存の1はすべて保持されることを意味します。111(1 << val)1checkerchecker
ご想像のとおり、1ここでの関数はtrueのブールフラグとして機能します。文字が文字列にすでに表現されているかどうかを確認するとき、checkerこの時点で、本質的にはすでに表現されている文字1のインデックスにあるブールフラグ（値）の配列であり、本質的には1現在の文字のインデックスにフラグが設定されたブール値。
オペレーターはこの&チェックを実行します。と同様に|=、演算子は、両方のオペランドがそのインデックスにある場合にのみ&コピーします。したがって、基本的に、にすでに存在し、で表されているフラグのみがコピーされます。この場合、これは、現在の文字がすでに表現されている場合にのみ、の結果のどこかに存在することを意味します。そして、その操作の結果のどこかにaが存在する場合、返されるブール値はであり、メソッドはfalseを返します。1 1checker(1 << val)1checker & (1 << val)1> 0
これが、ビットベクトルがビット配列とも呼ばれる理由だと思います。なぜなら、それらは配列データ型ではありませんが、ブールフラグを格納するために配列が使用されるのと同じように使用できるからです。
上記ですでに提供されている優れた回答がいくつかあります。だから私はすでに言ったことを繰り返したくありません。しかし、私は同じプログラムを実行し、いくつかの質問があったので、上記のプログラムを支援するためにいくつかのことを追加したいと思いましたが、しばらく時間を費やした後、このプログラムについてより明確になりました。
まず、「チェッカー」を使用して、文字列内ですでにトラバースされている文字を追跡し、繰り返されている文字があるかどうかを確認します。
現在、「チェッカー」はintデータ型であるため、32ビットまたは4バイト（プラットフォームによって異なります）しか持てないため、このプログラムは32文字の範囲内の文字セットに対してのみ正しく機能します。そのため、このプログラムは小文字のみで実行されるように、各文字から「a」を減算します。ただし、小文字と大文字を混在させると機能しません。
ちなみに、各文字から「a」を減算しない場合（以下のステートメントを参照）、このプログラムは大文字の文字列または小文字の文字列に対してのみ正しく機能します。したがって、上記のプログラムの範囲は、小文字から大文字に拡大しますが、それらを混在させることはできません。
int val = str.charAt(i) - 'a';
ただし、大文字、小文字、数字、または特殊文字を気にせずに、ASCII文字で機能するビット演算を使用して汎用プログラムを作成したかったのです。これを行うには、「チェッカー」が256文字（ASCII文字セットサイズ）を格納するのに十分な大きさである必要があります。ただし、Javaのintは、32ビットしか格納できないため、機能しません。したがって、以下のプログラムでは、JDKで使用可能なBitSetクラスを使用しています。このクラスは、BitSetオブジェクトのインスタンス化中に任意のユーザー定義のサイズを渡すことができます。
これは、ビット演算子を使用して記述された上記のプログラムと同じことを行うプログラムですが、このプログラムは、ASCII文字セットの任意の文字を含む文字列に対して機能します。
public static boolean isUniqueStringUsingBitVectorClass(String s) {
final int ASCII_CHARACTER_SET_SIZE = 256;
final BitSet tracker = new BitSet(ASCII_CHARACTER_SET_SIZE);
// if more than 256 ASCII characters then there can't be unique characters
if(s.length() > 256) {
return false;
}
//this will be used to keep the location of each character in String
final BitSet charBitLocation = new BitSet(ASCII_CHARACTER_SET_SIZE);
for(int i = 0; i < s.length(); i++) {
int charVal = s.charAt(i);
charBitLocation.set(charVal); //set the char location in BitSet
//check if tracker has already bit set with the bit present in charBitLocation
if(tracker.intersects(charBitLocation)) {
return false;
}
//set the tracker with new bit from charBitLocation
tracker.or(charBitLocation);
charBitLocation.clear(); //clear charBitLocation to store bit for character in the next iteration of the loop
}
return true;
}
簡単な説明（以下のJSコード付き）
32-bitDEC64、JSなどの言語の選択された記数法に依存しません。0th場合はインデックスを設定します。a1stb操作の概要：
checkerindexInt-32-Arraysif操作の出力を確認してください1output == 1
checker変数には、両方の配列に設定された特定のインデックス番目のビットがありますoutput == 0
checkerindex1checker仮定：
a97以下にJavaScriptのソースコードを示します。
function checkIfUniqueChars (str) {
var checker = 0; // 32 or 64 bit integer variable
for (var i = 0; i< str.length; i++) {
var index = str[i].charCodeAt(0) - 96;
var bitRepresentationOfIndex = 1 << index;
if ( (checker & bitRepresentationOfIndex) > 1) {
console.log(str, false);
return false;
} else {
checker = (checker | bitRepresentationOfIndex);
}
}
console.log(str, true);
return true;
}
checkIfUniqueChars("abcdefghi"); // true
checkIfUniqueChars("aabcdefghi"); // false
checkIfUniqueChars("abbcdefghi"); // false
checkIfUniqueChars("abcdefghii"); // false
checkIfUniqueChars("abcdefghii"); // false
JSでは、整数が64ビットであるにもかかわらず、ビット単位の演算は常に32ビットで実行されることに注意してください。
例：
文字列が次の場合aa：
// checker is intialized to 32-bit-Int(0)
// therefore, checker is
checker= 00000000000000000000000000000000
i = 0
str[0] is 'a'
str[i].charCodeAt(0) - 96 = 1
checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000000
Boolean(0) == false
// So, we go for the '`OR`' operation.
checker = checker OR 32-bit-Int(1)
checker = 00000000000000000000000000000001
i = 1
str[1] is 'a'
str[i].charCodeAt(0) - 96 = 1
checker= 00000000000000000000000000000001
a = 00000000000000000000000000000001
checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000001
Boolean(1) == true
// We've our duplicate now
コードを1行ずつ分解してみましょう。
intチェッカー=0; 重複する値を見つけるのに役立つチェッカーを開始しています。
int val = str.charAt（i）-'a'; 文字列の「i」番目の位置にある文字のASCII値を取得し、それを「a」のASCII値で減算しています。文字列は下位文字のみであると想定されているため、文字数は26文字に制限されています。つまり、「val」の値は常に>=0になります。
if（（checker＆（1 << val））> 0）falseを返します;
チェッカー|=（1 << val）;
さて、これはトリッキーな部分です。文字列「abcda」の例を考えてみましょう。これは理想的にはfalseを返すはずです。
ループ反復の場合1：
チェッカー：000000000000000000000000000000000000
val：97-97 = 0
1 << 0：00000000000000000000000000000001
チェッカー＆（1 << val）：000000000000000000000000000000000000は>0ではありません
したがって、チェッカー：00000000000000000000000000000001
forループ反復2：
チェッカー：00000000000000000000000000000001
val：98-97 = 1
1 << 1：00000000000000000000000000000010
チェッカー＆（1 << val）：000000000000000000000000000000000000は>0ではありません
したがって、チェッカー：00000000000000000000000000000011
ループ反復3の場合：
チェッカー：00000000000000000000000000000011
val：99-97 = 2
1 << 2：00000000000000000000000000000100
チェッカー＆（1 << val）：000000000000000000000000000000000000は>0ではありません
したがって、チェッカー：00000000000000000000000000000111
ループ反復の場合4：
チェッカー：00000000000000000000000000000111
val：100-97 = 3
1 << 3：00000000000000000000000000001000
チェッカー＆（1 << val）：000000000000000000000000000000000000は>0ではありません
したがって、チェッカー：00000000000000000000000000001111
ループ反復5の場合：
チェッカー：00000000000000000000000000001111
val：97-97 = 0
1 << 0：00000000000000000000000000000001
チェッカー＆（1 << val）：00000000000000000000000000000001は>0です
したがって、falseを返します。
public static void main (String[] args)
{
//In order to understand this algorithm, it is necessary to understand the following:
//int checker = 0;
//Here we are using the primitive int almost like an array of size 32 where the only values can be 1 or 0
//Since in Java, we have 4 bytes per int, 8 bits per byte, we have a total of 4x8=32 bits to work with
//int val = str.charAt(i) - 'a';
//In order to understand what is going on here, we must realize that all characters have a numeric value
for (int i = 0; i < 256; i++)
{
char val = (char)i;
System.out.print(val);
}
//The output is something like:
// !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ
//There seems to be ~15 leading spaces that do not copy paste well, so I had to use real spaces instead
//To only print the characters from 'a' on forward:
System.out.println();
System.out.println();
for (int i=0; i < 256; i++)
{
char val = (char)i;
//char val2 = val + 'a'; //incompatible types. required: char found: int
int val2 = val + 'a'; //shift to the 'a', we must use an int here otherwise the compiler will complain
char val3 = (char)val2; //convert back to char. there should be a more elegant way of doing this.
System.out.print(val3);
}
//Notice how the following does not work:
System.out.println();
System.out.println();
for (int i=0; i < 256; i++)
{
char val = (char)i;
int val2 = val - 'a';
char val3 = (char)val2;
System.out.print(val3);
}
//I'm not sure why this spills out into 2 lines:
//EDIT I cant seem to copy this into stackoverflow!
System.out.println();
System.out.println();
//So back to our original algorithm:
//int val = str.charAt(i) - 'a';
//We convert the i'th character of the String to a character, and shift it to the right, since adding shifts to the right and subtracting shifts to the left it seems
//if ((checker & (1 << val)) > 0) return false;
//This line is quite a mouthful, lets break it down:
System.out.println(0<<0);
//00000000000000000000000000000000
System.out.println(0<<1);
//00000000000000000000000000000000
System.out.println(0<<2);
//00000000000000000000000000000000
System.out.println(0<<3);
//00000000000000000000000000000000
System.out.println(1<<0);
//00000000000000000000000000000001
System.out.println(1<<1);
//00000000000000000000000000000010 == 2
System.out.println(1<<2);
//00000000000000000000000000000100 == 4
System.out.println(1<<3);
//00000000000000000000000000001000 == 8
System.out.println(2<<0);
//00000000000000000000000000000010 == 2
System.out.println(2<<1);
//00000000000000000000000000000100 == 4
System.out.println(2<<2);
// == 8
System.out.println(2<<3);
// == 16
System.out.println("3<<0 == "+(3<<0));
// != 4 why 3???
System.out.println(3<<1);
//00000000000000000000000000000011 == 3
//shift left by 1
//00000000000000000000000000000110 == 6
System.out.println(3<<2);
//00000000000000000000000000000011 == 3
//shift left by 2
//00000000000000000000000000001100 == 12
System.out.println(3<<3);
// 24
//It seems that the - 'a' is not necessary
//Back to if ((checker & (1 << val)) > 0) return false;
//(1 << val means we simply shift 1 by the numeric representation of the current character
//the bitwise & works as such:
System.out.println();
System.out.println();
System.out.println(0&0); //0
System.out.println(0&1); //0
System.out.println(0&2); //0
System.out.println();
System.out.println();
System.out.println(1&0); //0
System.out.println(1&1); //1
System.out.println(1&2); //0
System.out.println(1&3); //1
System.out.println();
System.out.println();
System.out.println(2&0); //0
System.out.println(2&1); //0 0010 & 0001 == 0000 = 0
System.out.println(2&2); //2 0010 & 0010 == 2
System.out.println(2&3); //2 0010 & 0011 = 0010 == 2
System.out.println();
System.out.println();
System.out.println(3&0); //0 0011 & 0000 == 0
System.out.println(3&1); //1 0011 & 0001 == 0001 == 1
System.out.println(3&2); //2 0011 & 0010 == 0010 == 2, 0&1 = 0 1&1 = 1
System.out.println(3&3); //3 why?? 3 == 0011 & 0011 == 3???
System.out.println(9&11); // should be... 1001 & 1011 == 1001 == 8+1 == 9?? yay!
//so when we do (1 << val), we take 0001 and shift it by say, 97 for 'a', since any 'a' is also 97
//why is it that the result of bitwise & is > 0 means its a dupe?
//lets see..
//0011 & 0011 is 0011 means its a dupe
//0000 & 0011 is 0000 means no dupe
//0010 & 0001 is 0011 means its no dupe
//hmm
//only when it is all 0000 means its no dupe
//so moving on:
//checker |= (1 << val)
//the |= needs exploring:
int x = 0;
int y = 1;
int z = 2;
int a = 3;
int b = 4;
System.out.println("x|=1 "+(x|=1)); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(y|=1); // 0001 |= 0001 == ?? 1????
System.out.println(y|=2); // ??? == 3 why??? 0001 |= 0010 == 3... hmm
System.out.println(y); //should be 3??
System.out.println(y|=1); //already 3 so... 0011 |= 0001... maybe 0011 again? 3?
System.out.println(y|=2); //0011 |= 0010..... hmm maybe.. 0011??? still 3? yup!
System.out.println(y|=3); //0011 |= 0011, still 3
System.out.println(y|=4); //0011 |= 0100.. should be... 0111? so... 11? no its 7
System.out.println(y|=5); //so we're at 7 which is 0111, 0111 |= 0101 means 0111 still 7
System.out.println(b|=9); //so 0100 |= 1001 is... seems like xor?? or just or i think, just or... so its 1101 so its 13? YAY!
//so the |= is just a bitwise OR!
}
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a'; //the - 'a' is just smoke and mirrors! not necessary!
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
public static boolean is_unique(String input)
{
int using_int_as_32_flags = 0;
for (int i=0; i < input.length(); i++)
{
int numeric_representation_of_char_at_i = input.charAt(i);
int using_0001_and_shifting_it_by_the_numeric_representation = 1 << numeric_representation_of_char_at_i; //here we shift the bitwise representation of 1 by the numeric val of the character
int result_of_bitwise_and = using_int_as_32_flags & using_0001_and_shifting_it_by_the_numeric_representation;
boolean already_bit_flagged = result_of_bitwise_and > 0; //needs clarification why is it that the result of bitwise & is > 0 means its a dupe?
if (already_bit_flagged)
return false;
using_int_as_32_flags |= using_0001_and_shifting_it_by_the_numeric_representation;
}
return true;
}
以前の投稿では、コードブロックの機能がよく説明されており、BitSetjavaデータ構造を使用して簡単なソリューションを追加したいと思います。
private static String isUniqueCharsUsingBitSet(String string) {
BitSet bitSet =new BitSet();
for (int i = 0; i < string.length(); ++i) {
int val = string.charAt(i);
if(bitSet.get(val)) return "NO";
bitSet.set(val);
}
return "YES";
}
Line 1: public static boolean isUniqueChars(String str) {
Line 2: int checker = 0;
Line 3: for (int i = 0; i < str.length(); ++i) {
Line 4: int val = str.charAt(i) - 'a';
Line 5: if ((checker & (1 << val)) > 0) return false;
Line 6: checker |= (1 << val);
Line 7: }
Line 8: return true;
Line 9: }
私がJavascriptを使って理解した方法。入力を想定var inputChar = "abca"; //find if inputChar has all unique characters
Line 4: int val = str.charAt(i) - 'a';
上記の行は、ASCIIでa、a = 97であるinputCharの最初の文字のバイナリ値を検索し 、97をバイナリに変換すると 1100001になります。
Javascriptの場合例："a".charCodeAt().toString(2) 1100001を返します
checker = 0//バイナリ32ビット表現=0000000000000000000000000
checker = 1100001 | checker;//チェッカーは1100001になります（32ビット表現では000000000 ..... 00001100001になります）
int checkerしかし、ビットマスク（ ）で1ビットだけを設定したいのですが、チェッカーは1100001です。
Line 4: int val = str.charAt(i) - 'a';
上記のコードが便利です。常に97を引くだけです（ASCII val of a）
val = 0; // 97 - 97 Which is a - a
val = 1; // 98 - 97 Which is b - a
val = 1; // 99 - 97 Which is c - a
リセットされたものを使用valしましょう
5行目と6行目は@Ivanの回答でよく説明されています
誰かがビットベクトルを使用して文字列内の一意の文字に相当するkotlinを探している場合に備えて
fun isUnique(str: String): Boolean {
var checker = 0
for (i in str.indices) {
val bit = str.get(i) - 'a'
if (checker.and(1 shl bit) > 0) return false
checker = checker.or(1 shl bit)
}
return true
}