모든 문자가 고유한지 확인하기 위해 비트 벡터 사용을 설명하십시오. = 0; for

비트 벡터가 어떻게 작동하는지 혼란 스럽습니다 (비트 벡터에 익숙하지 않음). 주어진 코드는 다음과 같습니다. 누군가 나를 통해 안내해 주시겠습니까?

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. 그들 사이에는 두 가지 차이점이 있습니다.

  • 크기 . 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라고도합니다. 다른 언어 / 플랫폼에 대한이 데이터 구조에 대한 링크는 다음과 같습니다.

답변

나는 당신이 읽고있는 동일한 책 에서이 코드를 얻었다는 의심을 가지고 있습니다 … 여기서 코드 자체는 연산자-| =, & 및 <<만큼 일반적으로 사용되지 않습니다. 우리 평신도-저자는 과정과 여기에 포함 된 실제 기계가 무엇인지 설명하는 데 시간이 더 걸리지 않았습니다. 처음에는이 스레드에 대한 이전 답변에 만족했지만 추상 수준에서만 만족했습니다. 좀 더 구체적인 설명이 필요하다고 느꼈기 때문에 다시 돌아 왔습니다. 하나가 없으면 항상 불안한 느낌이 듭니다.

이 연산자 <<는 왼쪽 비트 단위 시프터로 해당 숫자 또는 피연산자의 이진 표현을 취하고 오른쪽에있는 피연산자 또는 숫자로 지정된 많은 위치를 이진수로만 십진수로 이동합니다. 우리는 밑이 10이 아닌 많은 장소로 올라갈 때 밑이 2를 곱합니다. 그래서 오른쪽의 숫자는 지수이고 왼쪽의 숫자는 2의 기본 배수입니다.

이 연산자 | =는 왼쪽에있는 피연산자를 가져 오거나 오른쪽에있는 피연산자와 함께 있고이 연산자는 왼쪽과 오른쪽에있는 두 피연산자의 비트입니다.

그래서 우리가 가진 것은 체커가 checker |= (1 << val)문자의 지정된 이진 값으로 해당 비트를 true로 설정 하거나 검사 할 때마다 32 비트 이진수로 저장되는 해시 테이블 입니다. 캐릭터의 값은 체커 ( checker & (1 << val)) > 0) 와 함께 사용됩니다. 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

따라서 입력 문자열 ‘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

문자열 ‘아지’

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

이제 중복을 선언합니다

답변

나는이 모든 대답이 이것이 어떻게 작동하는지 설명한다고 생각하지만, 변수의 이름을 바꾸고 다른 변수를 추가하고 주석을 추가하여 더 잘 본 방법에 대한 정보를 제공하는 것처럼 느꼈습니다.

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"

  • 첫 패스 (i = t)

검사기 == 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)
  • 두 번째 패스 (i = e)

검사기 == 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

그것이 도움이되기를 바랍니다.

답변

위에 제공된 훌륭한 답변이 몇 가지 있습니다. 그래서 나는 이미 말한 모든 것을 반복하고 싶지 않습니다. 그러나 방금 동일한 프로그램을 통해 작업하고 몇 가지 질문을했지만 위의 프로그램에 도움이되는 몇 가지 사항을 추가하고 싶었지만 시간을 보낸 후이 프로그램에 대해 더 명확하게 설명했습니다.

우선 “체커”는 문자가 반복되는지 확인하기 위해 문자열에서 이미 순회 한 문자를 추적하는 데 사용됩니다.

이제 “checker”는 int 데이터 형식이므로 32 비트 또는 4 바이트 (플랫폼에 따라 다름) 만 가질 수 있으므로이 프로그램은 32 자 범위의 문자 집합에 대해서만 올바르게 작동 할 수 있습니다. 그렇기 때문에이 프로그램은 각 문자에서 ‘a’를 빼서이 프로그램을 소문자로만 실행합니다. 그러나 소문자와 대문자를 혼합하면 작동하지 않습니다.

그건 그렇고, 각 문자에서 ‘a’를 빼지 않으면 (아래 문장 참조)이 프로그램은 대문자가있는 문자열 또는 소문자 만있는 문자열에 대해서만 올바르게 작동합니다. 따라서 위 프로그램의 범위는 소문자에서 대문자로 증가하지만 함께 혼합 할 수는 없습니다.

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

그러나 대문자, 소문자, 숫자 또는 특수 문자를 걱정하지 않고 모든 ASCII 문자에서 작동하는 Bitwise Operation을 사용하여 일반 프로그램을 작성하고 싶었습니다. 이렇게하려면 “체커”가 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;

}

답변

위의 Ivan의 대답을 읽으면 실제로 도움이되었지만 다소 다르게 표현할 수는 있습니다.

<<에서이 (1 << val)비트 쉬프트 연산자이다. 그것은 1(바이너리에서로 표시되고 000000001원하는만큼의 0을 메모리에 의해 할당 됨) val공백으로 왼쪽으로 이동 합니다. 우리는 az 만 가정하고 a매번 빼기 때문에 각 문자의 값은 0-25입니다.이 숫자는 checker정수의 부울 표현의 오른쪽에서 해당 문자의 인덱스 가됩니다 . 시간을 1왼쪽으로 이동 하기 때문 checker val입니다.

각 점검이 끝나면 |=운영자 가 보입니다 . 이 인덱스에서 두 피연산자에 존재 하는 경우 모든이를 0의로 대체하여 두 개의 이진수를 병합합니다 . 여기에 있음은이 곳마다 그 수단 에 존재 , 로 복사됩니다 의 동안 모두 의 기존 1 개의은 유지됩니다.111(1 << val)1checkerchecker

짐작할 수 있듯이 1여기 의 함수는 true에 대한 부울 플래그입니다. 문자열에 문자가 이미 표시되어 있는지 확인하면 checker이 시점에서 이미 표현 된 1문자 색인의 기본 부울 플래그 ( 값) 배열과 기본 배열이 무엇인지 비교합니다. 1현재 문자의 색인에 플래그 가있는 부울 값

&오퍼레이터는이 검사를 달성한다. 받는 유사 |=의 &연산자는 이상 복사합니다 1 에만 두 피연산자가있는 경우 1해당 인덱스에서. 따라서 기본적으로 이미 checker표시된 플래그 만 (1 << val)복사됩니다. 이 경우, 현재 문자가 이미 표시된 경우에만 1결과의 어디에나 선물 이 표시됩니다 checker & (1 << val). 그리고 1그 연산의 결과에 a 가 있으면 반환 된 부울의 값은 > 0이고, 메소드는 false를 반환합니다.

이것은 비트 벡터가 비트 배열 이라고도하는 이유 입니다. 배열 데이터 유형이 아니더라도 부울 플래그를 저장하기 위해 배열을 사용하는 방식과 유사하게 사용할 수 있습니다.

답변

간단한 설명 (아래 JS 코드 포함)

  • 머신 코드 당 정수 변수는 32 비트 배열입니다.
  • 모든 비트 현명한 작업은 32-bit
  • 그것들은 OS / CPU 아키텍처 또는 DEC64JS 와 같은 선택된 언어의 숫자 체계 를 무시합니다.
  • 이 중복 찾는 방법과 유사한 크기 (32)의 배열에 문자를 저장 , 우리가 설정 0th우리가 발견하는 경우 인덱스를 a, 문자열에 1st대한 b& 등등.
  • 문자열의 중복 문자는 해당 비트를 점유하거나이 경우 1로 설정합니다.
  • Ivan은 이미 설명했다 :이 이전 답변에서이 인덱스 계산이 어떻게 작동 하는가 .

작업 요약 :

  • 문자 & 사이의 AND 연산 수행checkerindex
  • 내부적으로 둘 다 Int-32-Arrays
  • 이 둘 사이의 비트 단위 연산입니다.
  • if작업의 출력을 확인하십시오1
  • 만약 output == 1
    • checker변수를 갖는 특정 인덱스 번째 비트 두 배열의 집합
    • 따라서 중복입니다.
  • 만약 output == 0
    • 이 캐릭터는 지금까지 발견되지 않았습니다
    • & 의 문자 사이에 OR 연산을 수행하십시오.checkerindex
    • 이에 의해, 인덱스 비트를 다음으로 갱신한다 1
    • 출력을 할당 checker

가정 :

  • 우리는 모든 소문자를 얻을 것이라고 가정했습니다
  • 그리고 그 크기 32면 충분합니다
  • 따라서, 우리는에서 우리의 인덱스 계산을 시작 기준으로 96 고려 점 아스키 에 대한 코드 aIS를97

아래는 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

나는 = 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

나는 = 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