Méditations LeetCode : bits inversés

La description de Reverse Bits est très brève :

Inverser les bits d'un entier non signé de 32 bits donné.

Il y a aussi une note :

• Notez que dans certains langages, comme Java, il n'existe pas de type entier non signé. Dans ce cas, l’entrée et la sortie seront données sous forme de type entier signé. Ils ne devraient pas affecter votre implémentation, car la représentation binaire interne de l'entier est la même, qu'elle soit signée ou non signée.

• En Java, le compilateur représente les entiers signés en utilisant la notation complément à 2. Par conséquent, dans Exemple 2, l'entrée représente l'entier signé -3 et la sortie représente l'entier signé -1073741825.

Par exemple :

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Ou :

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Il est également indiqué que L'entrée doit être une chaîne binaire de longueur 32 dans les contraintes.

---

Comme nous savons que l'entrée est un entier de 32 bits, nous pouvons facilement calculer la position inversée de chaque bit. Par exemple, le 0ème correspond au 31, le 1er au 30, et ainsi de suite.

Mais nous faisons de la manipulation de bits, ce qui signifie que nous devons traiter chaque bit un par un.
Nous pouvons donc exécuter une boucle for pour faire exactement cela. A chaque fois, on peut décaler le bit de l'index vers la position la plus à droite, ce qui peut ressembler à ceci :

n >>> idx

Obtenir un peu (que ce soit 0 ou 1) peut être facilement réalisé avec une opération ET avec 1.
Si le bit est 0, 0 et 1 donneront 0.
Si c'est 1, 1 & 1 donneront 1.

Remarque ête> Nous pouvons considérer

Note

We can think of ANDing with 1 as the multiplicative identity (for example, $7\cdot 1=7$7⋅1=7 ).

AND avec 1 comme identité multiplicative (par exemple, $$7⋅ 1=77 cdot 1 = 7 7⋅1=7 ).

Tout d'abord, nous pouvons comprendre :

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Ensuite, nous devons mettre le foret que nous avons en position inversée. Pour cela, nous pouvons décaler le bit à gauche, en ajoutant au résultat au fur et à mesure :

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Nous devons renvoyer le résultat sous forme d'entier 32 bits, pour ce faire, nous pouvons faire une astuce en utilisant l'opérateur de décalage à droite non signé :

n >>> idx

Et la solution finale ressemble à ceci :

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

Complexité temporelle et spatiale

Nous savons que l'entrée et notre résultat sont toujours des entiers de 32 bits (et nous n'avons pas besoin d'utiliser d'autres structures de données supplémentaires), nous exécutons également une boucle 32 fois, ce qui est un nombre fixe, donc les complexités temporelles et spatiales sont $O(1)$O(1) .

---

Ensuite, nous examinerons le numéro manquant. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!