Wyjaśnij użycie wektora bitowego do określenia, czy wszystkie znaki są unikalne

Podejrzewam, że masz ten kod z tej samej książki, którą czytam...Sam kod nie jest tak tajemniczy, jak operatory -/=, & i

Ten operator

Ten operator |= bierze operand po lewej i or 's it z operandem po prawej - i ten -' & ' i jest bitami obu operandów po lewej i prawej stronie.

Mamy więc tabelę hash, która jest przechowywana w 32-bitowej liczbie binarnej za każdym razem, gdy kontroler dostaje or ' D (checker |= (1 << val)) z wyznaczoną wartością binarną litery odpowiadającej jej bitowi, jest ustawiana na true. Wartość znaku jest i ' D z checkerem (checker & (1 << val)) > 0) - jeśli jest większa od 0 wiemy, że mieć dupe - ponieważ dwa identyczne bity ustawione na true I 'd razem zwrócą true lub '1".

Jest 26 miejsc binarnych, z których każdy odpowiada małej literze-autor powiedział, aby założyć, że łańcuch zawiera tylko małe litery - a to dlatego, że mamy tylko 6 Więcej (w 32-bitowej liczbie całkowitej) miejsc do pochłonięcia-i wtedy otrzymujemy kolizję

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

Więc dla ciągu wejściowego 'azya', gdy poruszamy się krok po kroku

String ' a '

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001

a and checker=0 no dupes condition

String "az"

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

checker=z or checker;
// checker now becomes 00000010000000000000000000000001  

String ' azy '

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

checker= checker or y;
// checker now becomes = 00000011000000000000000000000001

String 'azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

Teraz deklaruje duplikat

Zakładam również, że twój przykład pochodzi z książki Cracking the Code Interview i moja odpowiedź jest związana z tym kontekstem.

Aby użyć tego algorytmu do rozwiązania problemu, musimy przyznać, że będziemy przekazywać tylko znaki od a do Z (małe litery).

Ponieważ jest tylko 26 liter i są one odpowiednio posortowane w używanej przez nas tabeli kodowania, gwarantuje nam to, że wszystkie potencjalne różnice str.charAt(i) - 'a' będą mniejsze niż 32 (wielkość int zmienna checker).

Jak wyjaśnia Snowbear, zamierzamy użyć zmiennej checker jako tablicy bitów. Lets have a approach by example:

Powiedzmy str equals "test"

• pierwsze przejście (i = t)

Checker == 0 (000000000000000000000000000000000000000)

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)

• Second pass (i = e)

Checker = = 524288 (00000000000010000000000000000000)

val = 101 - 97 = 4
1          == 00000000000000000000000000000001
1 << 4     == 00000000000000000000000000010000
checker |= (1 << val) 
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)

I tak dalej.. dopóki nie znajdziemy już ustawionego bitu w checkerze dla określonego znaku poprzez warunek

(checker & (1 << val)) > 0

Hope it helps

Myślę, że wszystkie te odpowiedzi wyjaśniają, jak to działa, jednak miałem ochotę dać swój wkład w to, jak widziałem to lepiej, zmieniając nazwy niektórych zmiennych, dodając kilka innych i dodając komentarze do niego:

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;
}

Przeczytanie powyższej odpowiedzi Ivana naprawdę mi pomogło, chociaż sformułowałbym ją nieco inaczej.

<< W (1 << val) jest operatorem przesunięcia bitowego. Przyjmuje 1 (które w systemie binarnym jest reprezentowane jako 000000001 , z dowolną liczbą poprzedzających zer / przydzielonych przez pamięć) i przesuwa je w lewo przez val spacje. Ponieważ zakładamy tylko a-z i odejmujemy a za każdym razem, każda litera będzie miała wartość 0-25, która będzie indeksem tej litery z prawej strony checker reprezentację boolowską integera, ponieważ przesuniemy 1 w lewo w checker val razy.

Na końcu każdej kontroli widzimy operator |=. To łączy dwie liczby binarne, zamieniając wszystkie 0 'S na 1' S, Jeśli 1 istnieje w którymś z operandów w tym indeksie. Oznacza to, że gdziekolwiek 1 istnieje w (1 << val), to 1 zostanie skopiowane do checker, podczas gdy wszystkie istniejące 1 checker zostaną zachowane.

Jak można się domyślać, a 1 funkcjonuje tutaj jako flaga logiczna dla true. Kiedy sprawdzamy, czy znak jest już reprezentowany w łańcuchu, porównujemy checker, który w tym momencie jest zasadniczo tablicą znaczników logicznych (1 wartości) w indeksach znaków, które zostały już reprezentowane, z tym, co jest zasadniczo tablicą wartości logicznych z znacznikiem 1 w indeksie bieżącego znaku.

Operator & dokonuje tego sprawdzenia. Podobnie do |=, operator & skopiuje 1 tylko jeśli oba operandy mają {[2] } w tym indeksie. Tak więc zasadniczo kopiowane będą tylko flagi obecne w checker, które są również reprezentowane w (1 << val). W tym przypadku oznacza to, że tylko wtedy, gdy obecny znak został już reprezentowany, będzie 1 obecny w dowolnym miejscu w wyniku checker & (1 << val). A jeśli 1 jest obecny w dowolnym miejscu w wyniku tej operacji, to wartością zwracanej wartości logicznej jest > 0, A Metoda zwraca false.

To jest, Jestem zgadywanie, dlaczego wektory bitowe nazywane są również tablicami bitowymi . Ponieważ, mimo że nie są one typu danych array, mogą być używane podobnie jak tablice używane do przechowywania FLAG logicznych.

Istnieje kilka doskonałych odpowiedzi już podanych powyżej. Więc nie chcę powtarzać tego, co już zostało powiedziane. Ale chciał dodać kilka rzeczy, aby pomóc w powyższym programie, ponieważ po prostu pracował przez ten sam program i miał kilka pytań, ale po spędzeniu trochę czasu, mam więcej jasności w tym programie.

Przede wszystkim "checker" jest używany do śledzenia znaku, który jest już przejechany w ciągu znaków, aby sprawdzić, czy są jakieś znaki, które otrzymują powtórzone.

Teraz "checker" jest typem danych int, więc może mieć tylko 32 bity lub 4 bajty (w zależności od platformy), więc ten program może działać poprawnie tylko dla zestawu znaków w zakresie 32 znaków. To jest powód, ten program odejmuje 'a' od każdego znaku, aby ten program działał tylko dla małych liter. Jeśli jednak połączysz małe i wielkie litery, to nie zadziała.

Przy okazji, jeśli nie odejmujesz 'a' od każdego znaku (patrz poniżej) wtedy ten program będzie działał poprawnie tylko dla łańcucha z dużymi literami lub łańcucha z małymi literami. Tak więc zakres powyższego programu zwiększa się z małych znaków do wielkich znaków zbyt, ale nie mogą być mieszane razem.

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

Chciałem jednak napisać ogólny program za pomocą operacji bitowej, która powinna działać dla dowolnych znaków ASCII bez martwienia się o wielkie litery, małe litery, cyfry lub jakikolwiek znak specjalny. W celu w tym celu nasz "checker" powinien być wystarczająco duży, aby pomieścić 256 znaków (rozmiar zestawu znaków ASCII). Ale int w Javie nie działa, ponieważ może przechowywać tylko 32 bity. Stąd w poniższym programie używam klasy BitSet dostępnej w JDK, która może mieć dowolny rozmiar zdefiniowany przez użytkownika podczas tworzenia instancji obiektu BitSet.

Oto program, który robi to samo, co powyżej program napisany operatorem bitowym, ale ten program będzie działał Dla ciągu znaków z dowolnym znakiem ASCII gotowi.

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;

}

Proste wyjaśnienie (z kodem JS poniżej)

• zmienna całkowita NA kod maszynowy to 32-bitowa tablica
• wszystkie operacje bitowe są 32-bit
• są agnostykiem architektury OS / CPU lub wybranego systemu liczbowego języka, np. DEC64 dla JS.
• to podejście do wyszukiwania duplikacji jest podobne doprzechowywania znaków w tablicy o rozmiarze 32 gdzie ustawiamy 0th indeks, jeśli znajdziemy a w łańcuchu, 1st dla b & i tak dalej.
• zduplikowany znak w łańcuchu będzie miał odpowiadający mu bit, lub, w tym przypadku, ustawiony na 1.
• Ivan już wyjaśnił: Jak to obliczenie wskaźnika działa w poprzedniej odpowiedzi.

Podsumowanie operacji:

• Wykonywanie i operacji pomiędzy checker & index of the character
• wewnętrznie oba są Int-32-Arrays
• jest to nieco mądra operacja pomiędzy tymi 2.
• Sprawdź if wynik operacji był 1
• if output == 1
  • zmienna checker ma ten konkretny indeks-ten bit ustawiony w obu tablicach
  Więc jest duplikatem.

Założenia:

• założyliśmy, że otrzymamy wszystkie małe litery
• i ten rozmiar 32 wystarczy
• dlatego rozpoczęliśmy nasz indeks licząc od 96 jako punkt odniesienia , biorąc pod uwagę } kod ascii dla a to 97

Poniżej znajduje się kod źródłowy 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

Zauważ , że w JS, mimo że liczby całkowite są 64 bitów, nieco mądre operacja jest zawsze wykonywana na 32 bitach.

Przykład: Jeśli łańcuch jest aa, to:

// 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

Pozwala podzielić linię kodu po linii.

Int checker = 0; rozpoczynamy sprawdzanie, które pomoże nam znaleźć zduplikowane wartości.

Int val = str.charAt (i) - 'a'; otrzymujemy wartość ASCII znaku na ' i '- tej pozycji łańcucha i odejmujemy ją wartością ASCII 'a'. Ponieważ zakłada się, że łańcuch jest tylko dolnymi znakami, liczba znaków ograniczona jest do 26. Hece, wartość 'val' zawsze będzie >= 0.

If ((checker & (1 0) return false;

Checker / = (1

Teraz to jest najtrudniejsza część. Rozważmy przykład z łańcuchem "abcda". Powinno to zwracać wartość false.

dla iteracji pętli 1:

Checker: 00000000000000000000000000000000000000

Val: 97-97 = 0

1

Checker & (1 0

Stąd checker: 000000000000000000000000000000000001

dla iteracji pętli 2:

Checker: 00000000000000000000000000000000001

Val: 98-97 = 1

1

Checker & (1 0

Stąd checker: 00000000000000000000000000000000011

dla iteracji pętli 3:

Checker: 00000000000000000000000000000011

Val: 99-97 = 0

1

Checker & (1 0

Stąd checker: 00000000000000000000000000000000111

dla iteracji pętli 4:

Checker: 0000000000000000000000000000000111

Val: 100-97 = 0

1

Checker & (1 0

Stąd checker: 00000000000000000000000000000001111

dla iteracji pętli 5:

Checker: 0000000000000000000000000000001111

Val: 97-97 = 0

1

Checker & (1 0

Stąd return 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;
}

Poprzednie posty dobrze wyjaśniają, co robi blok kodu i chcę dodać moje proste rozwiązanie przy użyciu struktury danych BitSet java:

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";
}