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

Je suis confus quant à la façon dont un vecteur de bit fonctionnerait pour le faire (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(Ssortingng str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) - 'a'; if ((checker & (1 < 0) return false; checker |= (1 << val); } return true; } 

En particulier, que fait le checker ?

int checker est utilisé ici comme stockage pour les bits. Chaque bit de valeur entière peut être traité comme un drapeau, donc finalement, int est un tableau de bits (indicateur). Chaque bit de votre code indique si le caractère avec l’index du bit a été trouvé dans la chaîne ou non. Vous pouvez utiliser le bit vector pour la même raison au lieu de int . Il y a deux différences entre eux:

  • Taille int a une taille fixe, généralement 4 octets, ce qui signifie que 8 * 4 = 32 bits (indicateurs). Le vecteur de bits peut généralement être de taille différente ou vous devez spécifier la taille du constructeur.

  • API Avec les vecteurs binarys, vous aurez plus de facilité à lire le code, probablement quelque chose comme ceci:

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

    pour int vous aurez un code logique de bit de niveau inférieur:

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

Aussi, probablement, peut être un peu plus rapide, car les opérations avec les bits sont très faibles et peuvent être exécutées telles quelles par le CPU. BitVector permet d'écrire un peu moins de code cryptique, mais il peut stocker davantage de drapeaux.

Pour référence future: bit vector est également appelé bitSet ou bitArray. Voici quelques liens vers cette structure de données pour différentes langues / plates-formes:

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

J’ai un soupçon discret que vous avez ce code du même livre que je lis … Le code lui-même ici n’est pas aussi cryptique que les opérateurs – | =, &, et < < qui ne sont normalement pas utilisés par nous layman- l'auteur n'a pas pris la peine de prendre le temps supplémentaire pour expliquer le processus ni les mécanismes réels impliqués ici. Je me suis contenté de la réponse précédente sur ce sujet au début, mais seulement à un niveau abstrait. J'y suis revenu parce que je sentais qu'il y avait une explication plus concrète - le manque d'un me laisse toujours un sentiment de malaise.

Cet opérateur < < est un décaleur au niveau du bit de gauche, il prend la représentation binaire de ce nombre ou de cet opérande et le déplace sur autant d’endroits spécifiés par l’opérande ou le nombre à droite que dans des binaires. Nous multiplions par la base 2 - quand nous montons cependant beaucoup de places et non la base 10 - donc le nombre à droite est l'exposant et le nombre à gauche est un multiple de base de 2.

Cet opérateur | = prend l’opérande à gauche et ou est-ce avec l’opérande à droite et celui-ci – “&” 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 binary de 32 bits chaque fois que le vérificateur obtient ou a ( checker |= (1 < < val) ) avec la valeur binary désignée d'une lettre est mis à vrai. La valeur du caractère est et est obtenue avec le checker ( checker & (1 < < val)) > 0 ) - s'il est supérieur à 0, nous soaps que nous avons un dupe car deux bits identiques définis à true et ensemble seront renvoyés true ou '1' '.

Il y a 26 emplacements binarys, chacun correspondant à une lettre minuscule - l'auteur a dit supposer que la chaîne ne contient que des lettres minuscules- et c'est parce qu'il ne nous rest que 6 places (en entier 32 bits) à consumr- et que nous faire une collision

 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 

Donc, pour une chaîne de saisie 'azya', alors que nous avançons pas à pas

chaîne 'a'

 a =00000000000000000000000000000001 checker=00000000000000000000000000000000 checker='a' or checker; // checker now becomes = 00000000000000000000000000000001 checker=00000000000000000000000000000001 a and checker=0 no dupes condition 

chaîne 'az'

 checker=00000000000000000000000000000001 z =00000010000000000000000000000000 z and checker=0 no dupes checker=z or checker; // checker now becomes 00000010000000000000000000000001 

ssortingng 'azy'

 checker= 00000010000000000000000000000001 y = 00000001000000000000000000000000 checker and y=0 no dupes condition checker= checker or y; // checker now becomes = 00000011000000000000000000000001 

chaîne 'azya'

 checker= 00000011000000000000000000000001 a = 00000000000000000000000000000001 a and checker=1 we have a dupe 

Maintenant, il déclare un doublon

Je suppose également que votre exemple provient du livre Cracking The Code Interview et ma réponse est liée à ce contexte.

Pour utiliser cet algorithme pour résoudre le problème, nous devons admettre que nous allons seulement passer des caractères de a à z (minuscule).

Comme il n’y a que 26 lettres et que celles-ci sont correctement sortingées dans la table de codage utilisée, cela nous garantit que toutes les différences potentielles str.charAt(i) - 'a' seront inférieures à 32 (la taille du checker variables int) .

Comme l’explique Snowbear, nous sums sur le point d’utiliser la variable checker comme un tableau de bits. Avons une approche par exemple:

Disons que str equals "test"

  • Premier passage (i = t)

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)

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 trouvions un bit déjà défini dans le vérificateur pour un caractère spécifique via la condition

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

J'espère que cela aide

Je pense que toutes ces réponses expliquent comment cela fonctionne, mais j’ai eu envie de donner mon avis sur la façon dont je l’ai vu mieux, en renommant certaines variables, en en ajoutant d’autres et en y ajoutant des commentaires:

 public static boolean isUniqueChars(Ssortingng 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 Ssortingng 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 eg 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. eg 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. eg 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; } 

La lecture de la réponse d’Ivan ci-dessus m’a vraiment aidé, bien que je l’aurais exprimé différemment.

Le < < in (1 < < val) est un opérateur à décalage de bits. Il prend 1 (qui en binary est représenté par 000000001 , avec autant de zéros précédents que vous le souhaitez / est affecté par la mémoire) et le déplace vers la gauche par des espaces de val . Puisque nous supposons que az et soustrayons a chaque fois, chaque lettre aura une valeur de 0-25, qui sera l'index de cette lettre de la droite dans la représentation booléenne de l'entier checker , puisque nous allons déplacer le 1 vers la gauche checker

A la fin de chaque vérification, nous voyons l'opérateur |= . Cela fusionne deux nombres binarys, remplaçant tous les 0 par 1 si un 1 existe dans l'un ou l'autre des opérandes de cet index. Ici, cela signifie que partout où un 1 existe dans (1 < < val) , celui-ci sera copié dans le checker , alors que tous les 1 existants du checker seront conservés.

Comme vous pouvez probablement le deviner, un 1 fonctionne ici comme un indicateur booléen pour true. Lorsque nous vérifions si un caractère est déjà représenté dans la chaîne, nous comparons le checker , qui à ce stade est essentiellement un tableau de drapeaux booléens ( 1 valeurs) aux index des caractères déjà représentés, avec ce qui est essentiellement un tableau de valeurs booléennes avec un drapeau 1 à l'index du caractère actuel.

L'opérateur & accomplit cette vérification. Semblable à |= , l'opérateur & va copier sur un 1 uniquement si les deux opérandes ont un 1 à cet index. Donc, essentiellement, seuls les indicateurs déjà présents dans le checker qui sont également représentés dans (1 < < val) seront copiés. Dans ce cas, cela signifie que si le caractère actuel a déjà été représenté, il y aura 1 présent dans le résultat du checker & (1 < < val) . Et si un 1 est présent n'importe où dans le résultat de cette opération, alors la valeur du booléen renvoyé est > 0 et la méthode retourne false.

C'est, je suppose, pourquoi les vecteurs de bits sont aussi appelés tableaux de bits . Parce que, même s'ils ne sont pas du type de données tableau, ils peuvent être utilisés de la même façon que les tableaux sont utilisés pour stocker des indicateurs booléens.

Il y a quelques excellentes réponses déjà fournies ci-dessus. Je ne veux donc pas répéter ce que tout a déjà dit. Mais je voulais append quelques éléments pour aider avec le programme ci-dessus, car je viens de travailler sur le même programme et j’avais quelques questions, mais après un certain temps, j’ai plus de clarté sur ce programme.

Tout d’abord, “checker” est utilisé pour suivre le caractère déjà parcouru dans la chaîne afin de voir si des caractères sont répétés.

Maintenant, “checker” est un type de données int, donc il ne peut contenir que 32 bits ou 4 octets (selon la plate-forme), donc ce programme ne peut fonctionner correctement que pour un jeu de caractères de 32 caractères. C’est la raison pour laquelle ce programme soustrait «a» de chaque caractère afin que ce programme ne s’exécute que pour les minuscules. Cependant, si vous mélangez des caractères minuscules et majuscules, cela ne fonctionnera pas.

Au fait, si vous ne soustrayez pas “a” de chaque caractère (voir l’instruction ci-dessous), ce programme fonctionnera correctement uniquement pour Ssortingng avec des caractères majuscules ou Ssortingng avec uniquement des caractères minuscules. La scope du programme ci-dessus augmente donc des caractères minuscules aux majuscules, mais ils ne peuvent pas être mélangés.

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

Cependant, je voulais écrire un programme générique à l’aide de l’opération binary qui devrait fonctionner pour tous les caractères ASCII sans se soucier des majuscules, des minuscules, des chiffres ou de tout caractère spécial. Pour ce faire, notre “checker” doit être suffisamment grand pour stocker 256 caractères (taille du jeu de caractères ASCII). Mais un int en Java ne fonctionnerait pas car il ne peut stocker que 32 bits. Par conséquent, dans le programme ci-dessous, j’utilise la classe BitSet disponible dans JDK qui peut avoir n’importe quelle taille définie par l’utilisateur lors de l’instanciation d’un object BitSet.

Voici un programme qui fait la même chose que le programme ci-dessus écrit en utilisant l’opérateur Bitwise, mais ce programme fonctionnera pour une chaîne avec n’importe quel caractère du jeu de caractères ASCII.

 public static boolean isUniqueSsortingngUsingBitVectorClass(Ssortingng 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 Ssortingng 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; } 

Explication simple (avec le code JS ci-dessous)

  • Une variable entière par code machine est un tableau 32 bits
  • Toutes les opérations sur les bits sont en 32-bit
  • Ils sont indépendants de l’architecture OS / CPU ou du système de DEC64 choisi du langage, par exemple DEC64 pour JS.
  • Cette approche de recherche de duplication est similaire à la mémorisation de caractères dans un tableau de taille 32 où, nous définissons le 0th index si nous trouvons a dans la chaîne, le 1st pour b et ainsi de suite.
  • Un caractère dupliqué dans la chaîne aura son bit correspondant occupé ou, dans ce cas, défini sur 1.
  • Ivan a déjà expliqué : Comment ce calcul d’index fonctionne dans cette réponse précédente .

Résumé des opérations:

  • Effectuer l’opération AND entre le checker et l’ index du caractère
  • En interne, les deux sont Int-32-Arrays
  • C’est une opération entre les deux.
  • Vérifiez if le résultat de l’opération était 1
  • si output == 1
    • La variable de checker a cet index-e bit particulier défini dans les deux tableaux
    • C’est donc un doublon.
  • si output == 0
    • Ce personnage n’a pas été trouvé jusqu’à présent
    • Effectuer une opération OU entre le checker et l’ index du caractère
    • De ce fait, mettre à jour le index-e bit à 1
    • Atsortingbuer la sortie au checker

Hypothèses:

  • Nous avons supposé que nous aurons tous les caractères minuscules
  • Et cette taille 32 suffit
  • Par conséquent, nous avons commencé notre index en comptant à partir de 96 en considérant le code ASCII pour a

Le code source JavaScript est indiqué ci-dessous.

 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 

Notez que dans JS, bien que les entiers soient de 64 bits, une opération par bit est toujours effectuée sur 32 bits.

Exemple: Si la chaîne est aa alors:

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

Permet de décomposer le code ligne par ligne.

int checker = 0; Nous lançons un checker qui nous aidera à trouver des valeurs en double.

int val = str.charAt (i) – ‘a’; Nous obtenons la valeur ASCII du caractère à la position de la chaîne et en la soustrayant avec la valeur ASCII de «a». Puisque l’hypothèse est que la chaîne ne contient que des caractères inférieurs, le nombre de caractères est limité à 26. Hece, la valeur de ‘val’ sera toujours> = 0.

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

vérificateur | = (1 < < val);

Maintenant, c’est la partie délicate. Considérons un exemple avec la chaîne “abcda”. Cela devrait idéalement retourner faux.

Pour l’itération de boucle 1:

Vérificateur: 00000000000000000000000000000000

val: 97-97 = 0

1 < < 0: 00000000000000000000000000000001

checker & (1 < < val): 00000000000000000000000000000000 is not> 0

Par conséquent, vérificateur: 00000000000000000000000000000001

Pour l’itération de boucle 2:

Vérificateur: 00000000000000000000000000000001

val: 98-97 = 1

1 < < 0: 00000000000000000000000000000010

checker & (1 < < val): 00000000000000000000000000000000 is not> 0

Par conséquent, vérificateur: 00000000000000000000000000000011

Pour l’itération de boucle 3:

Vérificateur: 00000000000000000000000000000011

val: 99-97 = 0

1 < < 0: 00000000000000000000000000000100100

checker & (1 < < val): 00000000000000000000000000000000 is not> 0

Par conséquent, vérificateur: 00000000000000000000000000000111

Pour l’itération de boucle 4:

Checker: 00000000000000000000000000000111

val: 100-97 = 0

1 < < 0: 00000000000000000000000000001000

checker & (1 < < val): 00000000000000000000000000000000 is not> 0

Par conséquent, vérificateur: 00000000000000000000000000001111

Pour l’itération de boucle 5:

Checker: 00000000000000000000000000001111

val: 97-97 = 0

1 < < 0: 00000000000000000000000000000001

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

Par conséquent, retournez faux.

 public static void main (Ssortingng[] 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; } 

Les messages précédents expliquent bien ce que fait le bloc de code et je veux append ma solution simple en utilisant la structure de données java de BitSet:

 private static Ssortingng isUniqueCharsUsingBitSet(Ssortingng ssortingng) { 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"; }