Expliquer l'utilisation d'un vecteur de bits pour déterminer si tous les caractères sont uniques

Question

Je ne comprends pas comment un vecteur de bits fonctionnerait (pas trop familier avec les vecteurs de bits). Voici le code donné. Quelqu'un pourrait-il s'il vous plaît me guider à travers cela?

 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 particulier, que font les checker ?

Answer 1

J'ai l'intuition que vous avez obtenu ce code à partir du même livre que je suis en train de lire...Le code lui-même, ici, n'est pas aussi cryptique que les opérateurs- |=, &, et << qui ne sont pas normalement utilisés par nous layman - l'auteur n'a pas pris la peine de prendre le temps pour expliquer le processus et les mécanismes impliqués ici sont. Moi, j'étais content avec la réponse précédente sur ce sujet au début, mais uniquement sur un niveau d'abstraction. Je suis revenue parce que j'ai senti le besoin de plus d'explication concrète - l'absence de celle-ci me laisse toujours avec un sentiment de malaise.

Cet opérateur << est à gauche au niveau du bit shifter il prend la représentation binaire d'un nombre ou d'opérande et décale sur cependant de nombreux endroits spécifié par l'opérande ou le numéro de la droite comme dans les nombres décimaux seulement dans les binaires. Nous sommes en multipliant par la base 2-lorsque nous passons cependant de nombreux endroits, pas de base de 10 - de sorte que le nombre sur la droite est l'exposant et le nombre sur la gauche est une base de multiples de 2.

Cet opérateur |= prendre l'opérande de gauche et ou avec l'opérande à droite - et ce d'un'&'et les bits des deux opérandes à gauche et à droite.

Donc, ce que nous avons ici est une table de hachage qui est stockée dans un nombre binaire de 32 bits à chaque fois que le vérificateur obtient ou ( checker |= (1 << val)) le représentant désigné en valeur binaire d'une lettre de son correspondant bits il est défini à true. Le caractère de la valeur, et souhaitez avec le vérificateur (checker & (1 << val)) > 0)- si elle est supérieure à 0, nous savons que nous avons un double - parce que les deux identiques bits défini à true, et avait ainsi va retourner true ou "1".

Il y a 26 binaire lieux dont chacune correspond à une lettre minuscule-l'auteur fait dire à assumer la chaîne ne contient que des lettres minuscules - et c'est parce que nous avons seulement 6 plus (en entier de 32 bits) lieux de gauche à consommer - et que nous obtenons une collision

00000000000000000000000000000001 2^0

00000000000000000000000000000010 b 2^1

00000000000000000000000000000100 c 2^2

00000000000000000000000000001000 d 2^3

00000000000000000000000000010000 e 2^4

00000000000000000000000000100000 f 2^5

00000000000000000000000001000000 g 2^6

00000000000000000000000010000000 h 2^7

00000000000000000000000100000000 i 2^8

00000000000000000000001000000000 j 2^9

00000000000000000000010000000000 k 2^10

00000000000000000000100000000000 l 2^11

00000000000000000001000000000000 m 2^12

00000000000000000010000000000000 n 2^13

00000000000000000100000000000000 o 2^14

00000000000000001000000000000000 p 2^15

00000000000000010000000000000000 q 2^16

00000000000000100000000000000000 r 2^17

00000000000001000000000000000000 s 2^18

00000000000010000000000000000000 t 2^19

00000000000100000000000000000000 u 2^20

00000000001000000000000000000000 v 2^21

00000000010000000000000000000000 w 2^22

00000000100000000000000000000000 x 2^23

00000001000000000000000000000000 y 2^24

00000010000000000000000000000000 z 2^25

a= 00000000000000000000000000000001

le vérificateur=00000000000000000000000000000000

le vérificateur='a' ou checker

le vérificateur=00000000000000000000000000000001

un et le vérificateur=0 pas dupes condition

chaîne 'az'

le vérificateur=00000000000000000000000000000001

z =00000010000000000000000000000000

z et le vérificateur=0 pas dupes

le vérificateur=z ou checker= 00000010000000000000000000000001

string 'azy'

le vérificateur=00000010000000000000000000000001

y =00000001000000000000000000000000

checker et y=0 pas dupes condition

le vérificateur= vérificateur ou y =00000011000000000000000000000001

string 'azya'

le vérificateur= 00000011000000000000000000000001

a= 00000000000000000000000000000001

un et le vérificateur=1, nous avons une dupe

Answer 2

int checker est utilisé ici comme un stockage de bits. Tous les bits en entier de la valeur peut être considérée comme un drapeau, donc finalement, int est un tableau de bits (drapeau). Chaque bit de votre code indique si le personnage avec les bits de l'indice a été trouvé dans la chaîne ou pas. Vous pourriez utiliser un vecteur de bits pour la même raison, au lieu de int. Il y a deux différences entre eux:

• Taille. int a taille fixe, généralement de 4 octets, ce qui signifie 8*4=32 bits (drapeaux). Vecteur de bits peuvent être de taille différente ou vous devez spécifier la taille dans le constructeur.

• L'API. Avec des vecteurs de bits, vous aurez plus facile à lire le code, probablement quelque chose comme ceci:

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

  pour int vous aurez de niveau inférieur bits code de la logique:

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

Aussi, probablement, int peut-être un peu plus vite, parce que les opérations avec des morceaux sont très bas niveau, et peut être exécuté comme tel par la CPU. BitVector permet d'écrire un peu moins cryptique code au lieu de cela, de plus il peut stocker plus de drapeaux.

Pour une référence future: vecteur de bits est également connu comme bitSet ou bitArray. Voici quelques liens de cette structure de données pour les différentes langues/plates-formes:

• RPC: BitSet
• Java: BitSet
• C#: BitVector32 et BitArray

Answer 3

J'ai aussi supposer que votre exemple est tiré du livre de Fissuration Du Code de l'Interview et ma réponse est liée à ce contexte.

Afin d'utiliser cet algorithme pour résoudre le problème, nous devons admettre que nous n'allons passer les caractères de a à z (minuscules).

Comme il n'y a que 26 lettres et ils sont correctement triés dans la table d'encodage que nous utilisons, cela nous garantit que toutes les différences potentielles str.charAt(i) - 'a' seront inférieures à 32 (la taille de la variable int checker).

Comme l'a expliqué Snowbear, nous sommes sur le point d'utiliser l' checker variable comme un tableau de bits. Permet d'avoir une approche par l'exemple :

Disons str equals "test"

• Premier passage (i = t)

le vérificateur == 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)

• Deuxième passage (i = e)

le vérificateur == 524288 (00000000000010000000000000000000)

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

et ainsi de suite ... jusqu'à ce que nous trouvons déjà une de bit de checker pour un caractère spécifique par l'état

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

J'espère que ça aide

Answer 4

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

    //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?? yah!!
    System.out.println(y|=1); //already 3 so... 0011 |= 0001... maybe 0011 again? 3? YAHYAH!
    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, DUH 4+2+1=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;
}

Answer 5

Aux lignes 4 et 5 de la question, ces 2 déclarations ne représentent-elles pas la même chose?

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

Par exemple, if (str.charAt(i)) == 'b' , qui correspond à 00000010 (uniquement les bits 0 à 7)

 int val = 0000001;
(1 << val) == 00000010;
 

Ensuite, la ligne 5 a cette vérification ((checker & (1 << val)) > 0)

Pourquoi plutôt un - 'a' sur val, pourquoi ne pas simplement utiliser (checker & val) > 0) ?