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

Nie wiem, jak działałby wektor bitowy, aby to zrobić (niezbyt zaznajomiony z wektorami bitowymi). Oto podany kod. Czy ktoś mógłby mnie przez to przeprowadzić?

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

W szczególności co to checkerrobi?

int checkerjest tutaj używany jako magazyn dla bitów. Każdy bit w wartości całkowitej może być traktowany jako flaga, więc ostatecznie intjest to tablica bitów (flaga). Każdy bit w twoim kodzie określa, czy znak z indeksem bitu został znaleziony w ciągu, czy nie. Możesz użyć wektora bitowego z tego samego powodu zamiast int. Są między nimi dwie różnice:

• Rozmiar . intma stały rozmiar, zwykle 4 bajty, co oznacza 8 * 4 = 32 bity (flagi). Wektor bitowy zwykle może mieć inny rozmiar lub należy określić rozmiar w konstruktorze.

• API . Dzięki wektorom bitowym będziesz miał łatwiejszy do odczytania kod, prawdopodobnie coś takiego:

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

  ponieważ intbędziesz mieć kod logiki bitowej niższego poziomu:

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

Prawdopodobnie również intmoże być trochę szybszy, ponieważ operacje na bitach są na bardzo niskim poziomie i mogą być wykonywane przez procesor w takiej postaci, w jakiej są. BitVector pozwala zamiast tego napisać nieco mniej tajemniczy kod, a ponadto może przechowywać więcej flag.

Na przyszłość: wektor bitowy jest również znany jako bitSet lub bitArray. Oto kilka linków do tej struktury danych dla różnych języków / platform:

• CPP: BitSet
• Java: BitSet
• C #: BitVector32 i BitArray

Podejrzewam, że masz ten kod z tej samej książki, którą czytam ... Sam kod nie jest tak tajemniczy jak operatory- | =, &, i <<, których normalnie nie używa my laicy - autor nie zawracał sobie głowy poświęcaniem dodatkowego czasu na wyjaśnienie procesu ani na temat rzeczywistej mechaniki. Na początku byłem zadowolony z poprzedniej odpowiedzi w tym wątku, ale tylko na poziomie abstrakcyjnym. Wróciłem do tego, bo czułem, że potrzebne jest bardziej konkretne wyjaśnienie - brak jednego zawsze wywołuje we mnie niepokój.

Ten operator << jest lewostronnym przesuwnikiem bitowym, który przyjmuje binarną reprezentację tej liczby lub operandu i przesuwa ją o dowolną liczbę miejsc określonych przez operand lub liczbę po prawej stronie, tak jak w liczbach dziesiętnych tylko w binarnych. Mnożymy przez podstawę 2 - kiedy przesuwamy się w górę, jednak o wiele miejsc nie ma podstawy 10 - więc liczba po prawej stronie jest wykładnikiem, a liczba po lewej jest podstawą wielokrotności 2.

Ten operator | = bierze operand po lewej stronie i lub jest z operandem po prawej - a ten - „&” i jest bitami obu operandów po lewej i po prawej stronie.

Mamy tu więc tablicę skrótów, która jest przechowywana w 32-bitowej liczbie binarnej za każdym razem, gdy kontroler otrzyma or'd ( checker |= (1 << val)) z wyznaczoną wartością binarną litery, której odpowiadający jej bit jest ustawiany na true. Wartość znaku jest równa i oznaczona za pomocą checker ( checker & (1 << val)) > 0) - jeśli jest większa niż 0, wiemy, że mamy podwójną wartość, ponieważ dwa identyczne bity ustawione na wartość true i razem zwrócą wartość true lub '1' '.

Istnieje 26 miejsc binarnych, z których każde odpowiada małej literze - autor powiedział, że łańcuch zawiera tylko małe litery - a to dlatego, że pozostało nam tylko 6 (w 32-bitowej liczbie całkowitej) miejsc do wykorzystania - i niż my dostać 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

Tak więc, dla ciągu wejściowego „azya”, przechodząc krok po kroku

ciąg „a”

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

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

a and checker=0 no dupes condition

ciąg „az”

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

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

ciąg „azy”

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

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

ciąg „azya”

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

Teraz deklaruje duplikat

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

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

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 tablicy kodowania, gwarantuje nam to, że wszystkie potencjalne różnice str.charAt(i) - 'a'będą mniejsze niż 32 (wielkość zmiennej int checker).

Jak wyjaśnił Snowbear, zamierzamy użyć checkerzmiennej jako tablicy bitów. Spójrzmy na przykład:

Powiedzmy str equals "test"

• Pierwsze przejście (i = t)

checker == 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)

• Drugie przejście (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 ... aż znajdziemy już ustawiony bit w kontrolerze dla określonego znaku poprzez warunek

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

Mam nadzieję, że to pomoże

Powyżej podano kilka doskonałych odpowiedzi. Więc nie chcę powtarzać tego, co już zostało powiedziane. Ale chciałem dodać kilka rzeczy, które mogłyby pomóc w powyższym programie, ponieważ właśnie pracowałem nad tym samym programem i miałem kilka pytań, ale po spędzeniu trochę czasu mam więcej jasności co do tego programu.

Przede wszystkim „szachownica” służy do śledzenia znaku, który jest już przekroczony w ciągu znaków, aby sprawdzić, czy jakieś znaki są powtarzane.

Teraz „checker” jest typem danych typu 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 z zakresu 32 znaków. To jest powód, dla którego ten program odejmuje „a” od każdego znaku, aby program działał tylko dla małych liter. Jednak jeśli pomieszasz małe i duże litery, to nie zadziała.

Nawiasem mówiąc, jeśli nie odejmiesz „a” od każdego znaku (zobacz poniższą instrukcję), ten program będzie działał poprawnie tylko dla String z dużymi literami lub String z tylko małymi literami. Tak więc zakres powyższego programu zwiększa się od samych małych liter do wielkich liter, ale nie można ich mieszać razem.

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

Jednak chciałem napisać ogólny program wykorzystujący operację bitową, który powinien działać dla dowolnych znaków ASCII bez martwienia się o wielkie i małe litery, cyfry lub jakiekolwiek znaki specjalne. Aby to zrobić, nasz "checker" powinien być wystarczająco duży, aby pomieścić 256 znaków (rozmiar zestawu znaków ASCII). Ale int w Javie nie zadział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ć przekazany dowolny rozmiar zdefiniowany przez użytkownika podczas tworzenia instancji obiektu BitSet.

Oto program, który robi to samo, co powyższy program napisany przy użyciu operatora bitowego, ale ten program będzie działał dla łańcucha znaków z dowolnym znakiem z zestawu znaków 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;

}

Przeczytanie odpowiedzi Ivana powyżej bardzo mi pomogło, chociaż ująłbym to nieco inaczej.

<<W (1 << val)to operator nieco biegów. Bierze 1(co w systemie binarnym jest reprezentowane jako 000000001, z dowolną liczbą poprzedzających zer / jest przydzielonych przez pamięć) i przesuwa w lewo valspacjami. Ponieważ zakładamy tylko az i za akażdym razem odejmujemy , każda litera będzie miała wartość 0-25, która będzie indeksem tej litery od prawej strony checkerw logicznej reprezentacji liczby całkowitej, ponieważ będziemy przesuwać 1w lewo w checker valrazy.

Pod koniec każdego sprawdzenia widzimy |=operatora. To scala dwie liczby binarne, zastępując wszystkie 0's 1', jeśli 1istnieje w którymkolwiek operandzie w tym indeksie. Tutaj oznacza to, że wszędzie tam, gdzie 1istnieje (1 << val), 1zostanie skopiowane do checker, podczas gdy wszystkie checkeristniejące 1 zostaną zachowane.

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

&Operator realizuje ten czek. Podobny do |=The &operator skopiuje ponad 1 tylko jeśli oba argumenty mają 1w tym indeksie. Zasadniczo więc tylko flagi już obecne w programie, checkerktóre są również reprezentowane w, (1 << val)zostaną skopiowane. W tym przypadku oznacza to, że tylko wtedy, gdy aktualny znak był już reprezentowany, będzie 1obecny gdziekolwiek w wyniku checker & (1 << val). A jeśli 1gdziekolwiek w wyniku tej operacji występuje a, to wartość zwróconej wartości logicznej wynosi > 0, a metoda zwraca fałsz.

To jest, jak domyślam się, dlaczego wektory bitowe są również nazywane tablicami bitów . Ponieważ nawet jeśli nie są typu danych tablicowych, mogą być używane podobnie do sposobu, w jaki tablice są używane do przechowywania flag logicznych.

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

• Zmienna całkowita na kod maszynowy to tablica 32-bitowa
• Wszystkie mądre operacje są 32-bit
• Są agnostykami architektury OS / CPU lub wybranego systemu liczbowego języka, np. DEC64Dla JS.
• To podejście do znajdowania duplikatów jest podobne do przechowywania znaków w tablicy o rozmiarze 32, gdzie ustawiamy 0thindeks, jeśli znajdziemy aw ciągu, 1stdla bi tak dalej.
• Zduplikowany znak w ciągu będzie miał odpowiadający mu bit zajęty lub, w tym przypadku, ustawiony na 1.
• Ivan wyjaśnił już : Jak działa to obliczanie indeksu w poprzedniej odpowiedzi .

Podsumowanie operacji:

• Wykonaj operację AND pomiędzy checker& indexznaku
• Wewnętrznie oba są Int-32-Arrays
• Jest to nieco mądra operacja między tymi dwoma.
• Sprawdź ifwynik operacji1
• Jeśli output == 1
  • checkerZmienna ma tego konkretnego indeksu-ty bit zestaw w obu tablicach
  • Zatem jest to duplikat.
• Jeśli output == 0
  • Ta postać do tej pory nie została znaleziona
  • Wykonaj operację LUB między checker& indexznaku
  • W ten sposób aktualizacja indeksu bitowego do 1
  • Przypisz wyjście do checker

Założenia:

• Założyliśmy, że otrzymamy wszystkie małe litery
• I ten rozmiar 32 wystarczy
• Dlatego zaczęliśmy nasz indeks licząc od 96 jako punktu odniesienia, biorąc pod uwagę kod ascii dla ais97

Poniżej podano 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 mają 64 bity, nieco mądra operacja jest zawsze wykonywana na 32 bitach.

Przykład: Jeśli ciąg to 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

Pozwala rozbić kod wiersz po wierszu.

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

int val = str.charAt (i) - 'a'; Pobieramy wartość ASCII znaku na „i” pozycji ciągu i odejmujemy ją od wartości ASCII „a”. Ponieważ założenie jest takie, że łańcuch składa się tylko z mniejszych znaków, liczba znaków jest ograniczona do 26. Hece, wartość „val” zawsze będzie> = 0.

if ((checker & (1 << val))> 0) return false;

checker | = (1 << val);

To jest trudna część. Rozważmy przykład ze stringiem „abcda”. Powinno to w idealnym przypadku zwrócić fałsz.

Dla iteracji pętli 1:

Checker: 00000000000000000000000000000000

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

checker & (1 << val): 00000000000000000000000000000000 nie jest> 0

Stąd kontroler: 00000000000000000000000000000001

Dla iteracji pętli 2:

Kontroler: 00000000000000000000000000000001

wartość: 98-97 = 1

1 << 0: 00000000000000000000000000000010

checker & (1 << val): 00000000000000000000000000000000 nie jest> 0

Stąd kontroler: 00000000000000000000000000000011

Dla iteracji pętli 3:

Kontroler: 00000000000000000000000000000011

val: 99-97 = 0

1 << 0: 00000000000000000000000000000100

checker & (1 << val): 00000000000000000000000000000000 nie jest> 0

Stąd kontroler: 00000000000000000000000000000111

Dla iteracji pętli 4:

Kontroler: 00000000000000000000000000000111

val: 100-97 = 0

1 << 0: 00000000000000000000000000001000

checker & (1 << val): 00000000000000000000000000000000 nie jest> 0

Stąd kontroler: 00000000000000000000000000001111

Dla iteracji pętli 5:

Kontroler: 00000000000000000000000000001111

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

checker & (1 << val): 00000000000000000000000000000001 jest> 0

Stąd zwrot fałsz.

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 wyjaśniają dobrze, co robi blok kodu i chcę dodać moje proste rozwiązanie za pomocą 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";
}

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

Sposób, w jaki rozumiałem używanie Javascript. Zakładając wejścievar inputChar = "abca"; //find if inputChar has all unique characters

Zaczynajmy

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

Powyższy wiersz Znajduje wartość binarną pierwszego znaku w inputChar, czyli a , a = 97 w ascii, a następnie konwertuje 97 na binarny i staje się 1100001 .

W JavaScript Np .: "a".charCodeAt().toString(2) zwraca 1100001

checker = 0 // binarna 32-bitowa reprezentacja = 00000000000000000000000

checker = 1100001 | checker; // kontroler staje się 1100001 (w 32-bitowej reprezentacji staje się 000000000 ..... 00001100001)

Ale chcę, aby moja int checkermaska ​​bitowa ( ) ustawiała tylko jeden bit, ale kontroler to 1100001

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

Teraz powyższy kod jest przydatny. Po prostu zawsze odejmuję 97 (wartość a w ASCII)

val = 0; // 97 - 97  Which is  a - a
val = 1; // 98 - 97 Which is b - a
val = 1;  // 99 - 97 Which is c - a

Użyjmy, valktóry jest zresetowany

Wiersze 5 i 6 są dobrze wyjaśnione @Ivan answer

Na wszelki wypadek, jeśli ktoś szuka odpowiednika kotlin dla unikalnych znaków w łańcuchu za pomocą wektora bitowego

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
}

Ref: https://www.programiz.com/kotlin-programming/bitwise