Explicar el uso de un vector de bits para determinar si todos los caracteres son únicos.

Estoy confundido acerca de cómo funcionaría un vector de bits para hacer esto (no estoy demasiado familiarizado con los vectores de bits). Aquí está el código dado. ¿Podría alguien guiarme a través de esto?

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

En particular, ¿qué está checkerhaciendo?

int checkerse usa aquí como almacenamiento de bits. Cada bit en el valor entero se puede tratar como una bandera, por lo que eventualmente intes una matriz de bits (bandera). Cada bit en su código indica si el carácter con el índice del bit se encontró en cadena o no. Podría usar bit vector por la misma razón en lugar de int. Hay dos diferencias entre ellos:

• Tamaño . inttiene un tamaño fijo, generalmente 4 bytes, lo que significa 8 * 4 = 32 bits (banderas). El vector de bits generalmente puede tener un tamaño diferente o debe especificar el tamaño en el constructor.

• API . Con los vectores de bits tendrá un código más fácil de leer, probablemente algo como esto:

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

  porque inttendrás un código lógico de bit de nivel inferior:

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

También es probable intque sea un poco más rápido, porque las operaciones con bits son de muy bajo nivel y la CPU puede ejecutarlas tal cual. BitVector permite escribir un poco menos de código críptico y además puede almacenar más banderas.

Para referencia futura: el vector bit también se conoce como bitSet o bitArray. Aquí hay algunos enlaces a esta estructura de datos para diferentes idiomas / plataformas:

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

Tengo la sospecha de que obtuviste este código del mismo libro que estoy leyendo ... El código en sí no es tan críptico como los operadores- | =, &, y << que normalmente no usan nosotros legos: el autor no se molestó en tomarse un tiempo extra para explicar el proceso ni cuáles son los mecanismos reales involucrados aquí. Al principio estaba contento con la respuesta anterior en este hilo, pero solo en un nivel abstracto. Volví a ello porque sentí que tenía que haber una explicación más concreta: la falta de una siempre me deja con un sentimiento incómodo.

Este operador << es un desplazador de bits a la izquierda, toma la representación binaria de ese número u operando y la desplaza por todos los lugares especificados por el operando o número a la derecha como en números decimales solo en binarios. Estamos multiplicando por la base 2, cuando nos movemos hacia arriba, sin importar cuántos lugares no sean la base 10, por lo que el número a la derecha es el exponente y el número a la izquierda es un múltiplo base de 2.

Este operador | = toma el operando a la izquierda y / o está con el operando a la derecha, y este - '&' y son los bits de ambos operandos a izquierda y derecha.

Entonces, lo que tenemos aquí es una tabla hash que se almacena en un número binario de 32 bits cada vez que el verificador obtiene o'd ( checker |= (1 << val)) con el valor binario designado de una letra, su bit correspondiente se establece en verdadero. El valor del carácter es and'd con el verificador ( checker & (1 << val)) > 0), si es mayor que 0, sabemos que tenemos una duplicación, porque dos bits idénticos establecidos en verdadero y juntos devolverán verdadero o '1' '.

Hay 26 lugares binarios, cada uno de los cuales corresponde a una letra minúscula, dijo el autor para suponer que la cadena solo contiene letras minúsculas, y esto se debe a que solo tenemos 6 lugares más (en números enteros de 32 bits) para consumir, y que tener una colisión

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

Entonces, para una cadena de entrada 'azya', a medida que avanzamos paso a paso

cadena 'a'

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

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

a and checker=0 no dupes condition

cadena 'az'

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

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

cadena 'azy'

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

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

cadena 'azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

Ahora, declara un duplicado

Creo que todas estas respuestas explican cómo funciona esto, sin embargo, tuve ganas de dar mi opinión sobre cómo lo vi mejor, renombrando algunas variables, agregando otras y agregando comentarios:

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

También supongo que su ejemplo proviene del libro Cracking The Code Interview y mi respuesta está relacionada con este contexto.

Para utilizar este algoritmo para resolver el problema, debemos admitir que solo vamos a pasar caracteres de la a a la z (en minúsculas).

Como solo hay 26 letras y están ordenadas correctamente en la tabla de codificación que usamos, esto nos garantiza que todas las diferencias potenciales str.charAt(i) - 'a'serán inferiores a 32 (el tamaño de la variable int checker).

Como explica Snowbear, estamos a punto de usar la checkervariable como una matriz de bits. Tengamos un enfoque por ejemplo:

Digamos str equals "test"

• Primer pase (i = t)

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

• Segunda pasada (i = e)

corrector == 524288 (00000000000010000000000000000000)

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

y así sucesivamente ... hasta que encontremos un bit ya establecido en el verificador para un personaje específico a través de la condición

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

Espero eso ayude

Hay un par de excelentes respuestas ya proporcionadas anteriormente. Así que no quiero repetir lo que ya ha dicho todo. Pero quería agregar un par de cosas para ayudar con el programa anterior, ya que solo trabajé en el mismo programa y tuve un par de preguntas, pero después de pasar un tiempo, tengo más claridad sobre este programa.

En primer lugar, "checker" se utiliza para rastrear el carácter que ya está atravesado en la cadena para ver si hay caracteres que se repiten.

Ahora "checker" es un tipo de datos int, por lo que solo puede tener 32 bits o 4 bytes (según la plataforma), por lo que este programa solo puede funcionar correctamente para un conjunto de caracteres dentro de un rango de 32 caracteres. Esa es la razón, este programa resta 'a' de cada carácter para hacer que este programa se ejecute solo con caracteres en minúscula. Sin embargo, si combina caracteres en mayúsculas y minúsculas, no funcionaría.

Por cierto, si no resta 'a' de cada carácter (vea la siguiente declaración), este programa funcionará correctamente solo para Cadena con caracteres en mayúscula o Cadena con solo caracteres en minúscula. Por lo tanto, el alcance del programa anterior aumenta de caracteres en minúsculas a caracteres en mayúsculas también, pero no se pueden mezclar.

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

Sin embargo, quería escribir un programa genérico usando Bitwise Operation que debería funcionar para cualquier carácter ASCII sin preocuparme por mayúsculas, minúsculas, números o cualquier carácter especial. Para hacer esto, nuestro "verificador" debe ser lo suficientemente grande como para almacenar 256 caracteres (tamaño del conjunto de caracteres ASCII). Pero un int en Java no funcionaría, ya que solo puede almacenar 32 bits. Por lo tanto, en el siguiente programa, estoy usando la clase BitSet disponible en JDK, que puede pasar cualquier tamaño definido por el usuario al crear instancias de un objeto BitSet.

Aquí hay un programa que hace lo mismo que el programa anterior escrito con el operador Bitwise, pero este programa funcionará para una cadena con cualquier carácter del conjunto de caracteres 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;

}

Leer la respuesta de Ivan arriba realmente me ayudó, aunque lo expresaría de manera algo diferente.

El <<en (1 << val)es un operador de desplazamiento de bits. Toma 1(que en binario se representa como 000000001, con tantos ceros anteriores como desee / son asignados por la memoria) y lo desplaza a la izquierda por valespacios. Dado que estamos asumiendo solo az y restando acada vez, cada letra tendrá un valor de 0-25, que será el índice de esa letra desde la derecha en la checkerrepresentación booleana del entero, ya que nos desplazaremos 1hacia la izquierda en checker valocasiones.

Al final de cada verificación, vemos al |=operador. Esto combina dos números binarios, reemplazando todos los 0's con 1' s si 1existe uno en cualquiera de los operandos en ese índice. Aquí, eso significa que donde sea que 1exista un (1 << val), 1se copiará en checker, mientras que todos checkerlos 1 existentes se conservarán.

Como probablemente pueda adivinar, un 1aquí funciona como un indicador booleano para verdadero. Cuando verificamos si un carácter ya está representado en la cadena, comparamos checker, que en este punto es esencialmente una matriz de banderas booleanas ( 1valores) en los índices de caracteres que ya han sido representados, con lo que es esencialmente una matriz de valores booleanos con una 1bandera en el índice del carácter actual.

El &operador realiza esta verificación. Similar al |=, el &operador copiará 1 solo si ambos operandos tienen un 1índice en ese índice. Entonces, esencialmente, solo se copiarán las banderas ya presentes en las checkerque también estén representadas (1 << val). En este caso, eso significa que solo si el carácter actual ya ha sido representado habrá un 1presente en cualquier parte del resultado de checker & (1 << val). Y si a 1está presente en alguna parte del resultado de esa operación, entonces el valor del booleano devuelto es > 0, y el método devuelve falso.

Esto es, supongo, por qué los vectores de bits también se llaman matrices de bits . Porque, aunque no son del tipo de datos de matriz, se pueden usar de forma similar a la forma en que se usan las matrices para almacenar banderas booleanas.

Explicación simple (con el código JS a continuación)

• Una variable entera por código de máquina es una matriz de 32 bits
• Todas las operaciones poco sabias son 32-bit
• Son independientes de la arquitectura OS / CPU o del sistema numérico elegido del idioma, por ejemplo, DEC64para JS.
• Este enfoque de búsqueda de duplicación es similar al almacenamiento de caracteres en una matriz de tamaño 32 donde, establecemos el 0thíndice si lo encontramos aen la cadena, 1stpara by así sucesivamente.
• Un carácter duplicado en la cadena tendrá su bit correspondiente ocupado o, en este caso, establecido en 1.
• Ivan ya explicó : cómo funciona este cálculo de índice en esta respuesta anterior .

Resumen de operaciones:

• Realizar Y operación entre checkery indexdel personaje
• Internamente ambos son Int-32-Arrays
• Es una operación inteligente entre estos 2.
• Compruebe que ifla salida de la operación fue1
• Si output == 1
  • La checkervariable tiene ese índice-bit particular establecido en ambas matrices
  • Por lo tanto, es un duplicado.
• Si output == 0
  • Este personaje no se ha encontrado hasta ahora
  • Realizar una operación OR entre checkery indexdel personaje
  • De este modo, actualizando el bit de índice a 1
  • Asignar la salida a checker

Suposiciones

• Asumimos que obtendremos todos los caracteres en minúscula
• Y, ese tamaño 32 es suficiente
• Por lo tanto, comenzamos nuestro índice contando desde 96 como punto de referencia considerando el código ascii para ais97

A continuación se muestra el código fuente de 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

Tenga en cuenta que en JS, a pesar de que los enteros son de 64 bits, una operación inteligente se realiza siempre en 32 bits.

Ejemplo: si la cadena es aaentonces:

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

Vamos a desglosar el código línea por línea.

int checker = 0; Estamos iniciando un verificador que nos ayudará a encontrar valores duplicados.

int val = str.charAt (i) - 'a'; Estamos obteniendo el valor ASCII del carácter en la 'i' posición de la cadena y restandolo con el valor ASCII de 'a'. Como se supone que la cadena tiene solo caracteres inferiores, el número de caracteres está limitado a 26. Hece, el valor de 'val' siempre será> = 0.

if ((checker & (1 << val))> 0) devuelve falso;

corrector | = (1 << val);

Ahora esta es la parte difícil. Consideremos un ejemplo con la cadena "abcda". Idealmente, esto debería devolver falso.

Para la iteración de bucle 1:

Verificador: 00000000000000000000000000000000

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

corrector & (1 << val): 00000000000000000000000000000000 no es> 0

Por lo tanto, corrector: 00000000000000000000000000000001

Para la iteración de bucle 2:

Comprobador: 00000000000000000000000000000001

val: 98-97 = 1

1 << 0: 00000000000000000000000000000010

corrector & (1 << val): 00000000000000000000000000000000 no es> 0

Por lo tanto, corrector: 00000000000000000000000000000011

Para la iteración de bucle 3:

Verificador: 00000000000000000000000000000011

val: 99-97 = 0

1 << 0: 00000000000000000000000000000100

corrector & (1 << val): 00000000000000000000000000000000 no es> 0

Por lo tanto, corrector: 00000000000000000000000000000111

Para la iteración de bucle 4:

Verificador: 00000000000000000000000000000111

val: 100-97 = 0

1 << 0: 00000000000000000000000000001000

corrector & (1 << val): 00000000000000000000000000000000 no es> 0

Por lo tanto, corrector: 00000000000000000000000000001111

Para la iteración de bucle 5:

Comprobador: 00000000000000000000000000001111

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

corrector y (1 << val): 00000000000000000000000000000001 es> 0

Por lo tanto, devuelve falso.

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

Las publicaciones anteriores explican bien lo que hace el bloque de código y quiero agregar mi solución simple usando la estructura de datos 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:   }

La forma en que entendí usando Javascript. Asumiendo entradavar inputChar = "abca"; //find if inputChar has all unique characters

Empecemos

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

Por encima de la línea Encuentra el valor binario del primer carácter en inputChar que es a , a = 97 en ascii, luego convierte 97 en binario y se convierte en 1100001 .

En Javascript Ej .: "a".charCodeAt().toString(2) devuelve 1100001

checker = 0 // representación binaria de 32 bits = 0000000000000000000000000

checker = 1100001 | checker; // el corrector se convierte en 1100001 (en la representación de 32 bits se convierte en 000000000 ..... 00001100001)

Pero quiero que mi bitmask ( int checker) establezca solo un bit, pero el verificador es 1100001

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

Ahora el código anterior es útil. Acabo de restar 97 siempre (valor ASCII de 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

Permite el uso valque se restablece

La línea 5 y la línea 6 están bien explicadas @Ivan answer

Solo en caso de que alguien esté buscando kotlin equivalente de caracteres únicos en una cadena usando un vector de bits

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