모든 문자가 고유한지 여부를 판단하기 위한 비트 벡터 사용법을 설명합니다.
비트 벡터가 어떻게 동작하는지가 헷갈립니다(비트 벡터는 그다지 익숙하지 않습니다).여기 암호가 있습니다.누가 이것 좀 알려주시겠어요?
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;
}
특, 어, 이, 이, 이, partic, partic, partic, partic, 가 뭐죠?checker하고 있어요?
내가 읽고 있는 책과 같은 책에서 이 코드를 가져왔다는 게 은근히 의심되네코드 자체는 |=, & 및 <<> 연산자만큼 이해하기 어렵지만, 일반인들은 보통 사용하지 않습니다. 저자는 프로세스와 실제 관련된 메커니즘에 대해 설명하는 데 시간을 할애하지 않았습니다.처음에는 이 스레드에 대한 이전 답변에 만족했지만 추상적인 수준에 그쳤다.나는 좀 더 구체적인 설명이 필요하다고 느꼈기 때문에 돌아왔다.- 설명이 부족하면 항상 불안감을 느낀다.
이 연산자 <<는 왼쪽 비트 단위 시프터이며, 이 숫자 또는 피연산자의 이진 표현을 취하여 이진수에서만 10진수처럼 피연산자 또는 오른쪽 숫자에 의해 지정된 여러 자리 위로 이동합니다.베이스 2를 곱하고 있습니다.단, 베이스 10이 아닌 많은 장소가 올라가면 오른쪽의 숫자는 지수이고 왼쪽의 숫자는 베이스 2의 배수입니다.
이 연산자 |=(비트 OR 할당이라고 함)는 왼쪽 피연산자와 오른쪽 피연산자를 가져와서 결과를 왼쪽 피연산자에 할당합니다(x = x | y와 동일).마찬가지로 연산자('&')는 연산자의 왼쪽과 오른쪽을 '및'합니다.여기에는 비트 AND 할당도 있습니다(x &= y는 x = x & y와 동일).
가 or'd(d)를 얻을 됩니다.이 테이블은 체커가 or'd를 얻을 때마다 32비트 이진수로 저장됩니다.checker |= (1 << val) 값을 하는 비트를true로 합니다.)는 문자의 지정된 바이너리 값으로 대응하는 비트가 true로 설정되어 있습니다.와 '입니다.checker & (1 << val)) > 0보다 클 두 또는 '을 알 수 두 개의 동일한 비트가 true로 설정되어 'd'가 함께 true 또는 '1'을 반환하기 때문입니다.
각각 소문자에 대응하는 바이너리 자리수는 26개입니다.저자는 문자열에 소문자만 포함되어 있다고 가정합니다.이는 소비할 곳이 (32비트 정수)6개밖에 남지 않았기 때문입니다.충돌은 이 값보다 커집니다.
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
자, 입력 문자열 '아자'는 한 단계씩 이동하면서
문자열 '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
현악기 '아자'
checker= 00000011000000000000000000000001
a = 00000000000000000000000000000001
a and checker=1 we have a dupe
이것으로, 중복이 선언됩니다.
int checker여기서 비트 저장소로 사용됩니다.의 모든 할 수 때문에, 으로 「」라고 하는 것이 .int는 비트 배열(표준)입니다.코드의 각 비트는 비트의 인덱스를 가진 문자가 문자열에서 발견되었는지 여부를 나타냅니다.로 비트 할 수 .int 가지 이들 사이에는 두 가지 차이점이 있습니다.
사이즈
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
아마 또마 also also alsoint비트 조작이 매우 낮고 CPU에 의해 그대로 실행될 수 있기 때문에 조금 더 빠를 수 있습니다.BitVector는 대신 조금 더 적은 암호 코드를 쓸 수 있고 더 많은 플래그를 저장할 수 있습니다.
향후 참조용으로 비트 벡터는 bitSet 또는 bitArray라고도 합니다.다음은 다양한 언어/플랫폼의 이 데이터 구조에 대한 몇 가지 링크입니다.
- CPP: 비트 세트
- Java: 비트셋
- C#: BitVector32 및 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;
}
나는 또한 당신의 예가 코드인터뷰를 깨는 책에서 나온 것이라고 추측하고 나의 대답은 이 맥락과 관련이 있다고 생각한다.
이 알고리즘을 사용하여 문제를 해결하려면 a에서 z(소문자)로 문자만 전달한다는 것을 인정해야 합니다.
에서는 이러한 되어 있기 에, 으로 됩니다.str.charAt(i) - 'a' 변수 의 크기)보다 작습니다.checker를 참조해 주세요.
스노우베어에 의해 설명되었듯이, 우리는 이제 막 그 기술을 사용하려고 합니다.checker비트 배열로서 변수입니다. 예를들면 과 같이 접근하다.
'우리'라고 합시다.str equals "test"
- 퍼스트 패스(i = t)
체커 == 0 (0000000000000000000000000000)
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)
- 세컨드 패스(i = e)
체커 == 524288 (0000000000000000000000000000000)
val = 101 - 97 = 4
1 == 00000000000000000000000000000001
1 << 4 == 00000000000000000000000000010000
checker |= (1 << val)
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)
기타 등등..조건을 통해 특정 문자의 체커에 이미 설정된 비트를 찾을 수 있습니다.
(checker & (1 << val)) > 0
도움이 되었으면 좋겠다
위의 이반의 답변을 읽는 것은 나에게 큰 도움이 되었지만, 다소 다르게 표현하고 싶다.
<<(1 << val)는 약간 시프트 연산자입니다.이 걸린다.1에서는 (이진법으로 )000000001 임의의 수의 를 지정하거나 하거나 하고, 시킵니다( 「0」).val하고 a-z를 빼기때문에a, 이은 0~ 오른쪽에서 보면 0.checker 표현입니다. '부울 표현 '부울 표현'을 입니다.1checker valtimesdiscloss.discloss를 합니다.
체크의 에, 「 」가 표시됩니다.|= 모든 숫자가 바뀌게 됩니다.0에는 님님이 있습니다11이 인덱스의 어느 피연산자에도 존재합니다.은, 「어디서나」가 있는 , 「어디서나 「어디서나」가 되는 것을 합니다.1 (1 << val) , disclossible1에 복사되다checker , , , , , , 「」의 ,checker1번입니다.
와 같이, 하겠 as as as as as as as as as as as 。1사실되어 있는지 할 때 합니다.checker으로 부울플래그의부울플래그 배열).1values)는 이미에 값이 되어 있습니다).기본적으로 부울 값의 배열은 다음과 같습니다.1현재 문자의 인덱스에 플래그가 표시됩니다.
&이치노 와슷비 the the the the the similar와 비슷해요.|= , . . . . . . . .&1 두 오퍼랜드가 모두1그래서 이미 있는 거예요.checker 있습니다.(1 << val)이 현재 경우에만 이 문자가 표시됩니다.1 checker & (1 << val) ★★★★★★★★★★★★★★★★★★★★.1 그 의 결과 중 , 은 「」입니다.> 0거짓
이것이 비트 벡터가 비트 어레이라고도 불리는 이유라고 생각합니다.어레이 데이터 타입은 아니지만 부울 플래그를 저장하기 위해 어레이를 사용하는 방법과 유사하게 사용할 수 있기 때문입니다.
위에 제시된 몇 가지 훌륭한 답변이 있습니다.그래서 나는 이미 말한 것을 반복하고 싶지 않다.다만, 같은 프로그램을 통해서 몇 가지 질문이 있었기 때문에, 상기의 프로그램에 도움이 되는 몇 가지를 추가하고 싶다고 생각하고 있었습니다만, 시간이 좀 걸리면, 이 프로그램에 대해 보다 명확하게 알 수 있게 되었습니다.
우선 "체커"는 문자열에서 이미 통과된 문자를 추적하여 반복되는 문자가 있는지 확인합니다.
이제 "체커"는 int 데이터 유형이므로 32비트 또는 4바이트(플랫폼에 따라 다름)만 가질 수 있으므로 이 프로그램은 32자 이내의 문자 집합에서만 올바르게 작동합니다.그렇기 때문에 이 프로그램은 각 문자에서 'a'를 빼서 소문자에 대해서만 실행되도록 합니다.단, 소문자와 대소문자를 혼재시키면 동작하지 않습니다.
덧붙여서, 각 문자로부터 「a」를 빼지 않는 경우(아래 문 참조), 이 프로그램은 대문자 문자열 또는 소문자 문자열에 대해서만 올바르게 동작합니다.따라서 위 프로그램의 범위는 소문자에서 대문자로 늘어나지만 함께 사용할 수 없습니다.
int val = str.charAt(i) - 'a';
그러나 대문자, 소문자, 숫자, 특수문자를 신경 쓰지 않고 어떤 ASCII 문자에서도 사용할 수 있는 Bitwise Operation을 사용하여 범용 프로그램을 만들고 싶었습니다.그러기 위해서는, 「체커」가 256 문자(ASCII 문자 세트 사이즈)를 격납할 수 있을 만큼 커야 합니다.그러나 Java의 int는 32비트만 저장할 수 있기 때문에 작동하지 않습니다.따라서 아래 프로그램에서는 BitSet 객체를 인스턴스화하는 동안 사용자 정의 크기를 전달할 수 있는 JDK에서 사용 가능한 BitSet 클래스를 사용하고 있습니다.
이것은 Bitwise 연산자를 사용하여 작성된 위와 같은 프로그램을 수행하는 프로그램이지만, 이 프로그램은 ASCII 문자 집합의 문자를 가진 String에서 작동합니다.
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비트 어레이입니다.
- 은 " " " 입니다.
32-bit - OS/CPU 아키텍처나 선택된 언어 번호 체계에 구애받지 않습니다.
DEC64JS の js js 。 - 이 중복 검색 접근법은 32사이즈의 배열에 문자를 저장하는 것과 비슷합니다.
0th(인덱스)를 검출했을 경우a'''는1st★★★★★★에b기타 등등. - 문자열 내의 중복된 문자는 대응하는 비트를 점유합니다.이 경우 1로 설정됩니다.
- Ivan은 이미 설명했습니다. 이 이전 답변에서 이 인덱스 계산이 작동하는 방식입니다.
조작의 개요:
- AND 연산을 실행하다
checker&index - 으로는 둘 다 부부 intern intern intern intern이다.
Int-32-Arrays - 이 두 가지 사이의 비트 단위 연산입니다.
- 마크를 켜주세요.
if수술의 성과는 다음과 같았다.1 output == 1checker변수는 두 배열 모두에서 특정 인덱스번째 비트를 설정합니다.- 그래서 복제품인 거죠.
output == 0- 이 캐릭터는 아직 발견되지 않았습니다.
- 다음 사이에 OR 작업을 수행합니다.
checker&index - 를 index-th 비트로 합니다.
1 - 을 " " 에 할당합니다.
checker
전제 조건:
- 소문자를 모두 사용할 수 있다고 가정했습니다.
- 그리고 32사이즈면 충분합니다.
- 따라서, 우리는 기준점으로서 96부터 index counting을 시작했습니다.
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
코드를 한 줄씩 분해해 봅시다.
int checker = 0; 중복된 값을 찾는 데 도움이 되는 체커를 시작합니다.
int val = str.charAt(i) - 'a'입니다. 문자열의 'i' 위치에 있는 문자의 ASCII 값을 가져와서 ASCII 값 'a'로 뺍니다.문자열은 소문자만 사용하는 것이 전제이므로 글자 수는 26자로 제한됩니다.'val' 값은 항상 >= 0입니다.
(false & ( 1 < val )> 0)이 false를 반환하는 경우,
체커 |= (1 << val );
이게 어려운 부분이에요.문자열 "abcda"의 예를 살펴보겠습니다.이상적으로는 false가 반환됩니다.
루프 반복 1의 경우:
검사기: 00000000000000000000000000000000
값: 97-97 = 0
1 < 0 : 0000000000000000000000000000000001
checker & ( 1 < val ) : 000000000000000000000000000000이 0을 넘지 않음
따라서 체커: 00000000000000000000000000000001
루프 반복 2의 경우:
검사기: 00000000000000000000000000000001
값: 98-97 = 1
1 < 1 : 0000000000000000000000000010
checker & ( 1 < val ) : 000000000000000000000000000000이 0을 넘지 않음
따라서 체커: 00000000000000000000000011
루프 반복 3의 경우:
검사기: 00000000000000000000000011
값: 99-97 = 2
1 < 2 : 0000000000000000000000000000000000100
checker & ( 1 < val ) : 000000000000000000000000000000이 0을 넘지 않음
따라서 체커: 000000000000000000000000000111
루프 반복 4의 경우:
검사기: 00000000000000000000000000000111
값: 100-97 = 3
1 < 3 : 000000000000000000000000000
checker & ( 1 < val ) : 000000000000000000000000000000이 0을 넘지 않음
따라서 체커: 0000000000000000000000111
루프 반복 5의 경우:
검사기: 0000000000000000000000111
값: 97-97 = 0
1 < 0 : 0000000000000000000000000000000001
checker & ( 1 < val ) : 0000000000000000000000000001은 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;
}
이전 투고에서는 코드 블록의 기능에 대해 잘 설명하고 있으며, BitSet Java Data 구조를 사용하여 간단한 솔루션을 추가하고 싶습니다.
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';
위 라인 입력차르에서 첫 번째 문자의 이진수 값(asciii에서는 a = 97)을 찾은 다음 97을 이진수로 변환하면 1100001이 됩니다.
예: Javascript : : :"a".charCodeAt().toString(2)11000011001이됩니다.
checker = 0//
checker = 1100001 | checker;)./'110000001이 됩니다(32비트 표현에서는 000000000.....000011001이 됩니다).
내 비트마스크를 .int checker)의 1비트입니다.
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
용용 lets lets lets lets를 합시다.val 있다
5호선, 6호선 모두 잘 설명되어 있습니다 @Ivan answer
비트 벡터를 사용하여 문자열에서 고유 문자에 해당하는 코틀린을 찾는 사람이 있을 경우
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
}
참고 자료: https://www.programiz.com/kotlin-programming/bitwise
언급URL : https://stackoverflow.com/questions/9141830/explain-the-use-of-a-bit-vector-for-determining-if-all-characters-are-unique
'programing' 카테고리의 다른 글
| Vuejs 2: 워치옵션으로 동작하지 않음 (0) | 2022.08.12 |
|---|---|
| 컴포넌트 마운트 시 Vuex의 상태 데이터에 액세스하는 방법 (0) | 2022.08.12 |
| 정적과 최종의 차이점 (0) | 2022.08.12 |
| 루프에서 For 확인란을 렌더링하고 Vue JS에서 해당 값을 바인딩합니다. (0) | 2022.08.12 |
| 탭을 사용하여 다른 컴포넌트를 로드하는 Vue.js 방법 (0) | 2022.08.08 |