Méditations LeetCode — Manipulation des bits de chapitre

Table des matières

• Présentation
• Opérateurs au niveau du bit
  • ET (&)
  • OU (|)
  • XOR (^)
  • PAS (~)
  • Décalage vers la gauche (remplissage zéro) (<<)
  • Décalage vers la droite (préservation du signe) (>>)
  • Décalage vers la droite (non signé) (>>>)
• Prendre un peu
• Réglage un peu
• Ressources

Nous sommes dans le dernier chapitre de cette série, et il est enfin temps de jeter un bref aperçu de la manipulation des bits.

Comme le définit Wikipédia, une opération au niveau du bit opère sur une chaîne de bits, un tableau de bits ou un chiffre binaire (considéré comme une chaîne de bits) au niveau de ses bits individuels.

---

Représentons d'abord un nombre en binaire (base 2). Nous pouvons utiliser la méthode toString sur un nombre et spécifier la base :

const n = 17;

console.log(n.toString(2)); // 10001

On peut aussi analyser un entier en lui donnant une base :

console.log(parseInt(10001, 2)); // 17

A noter qu'on peut aussi représenter un nombre binaire avec le préfixe 0b :

console.log(0b10001); // 17
console.log(0b101); // 5

Par exemple, ce sont les mêmes numéros :

0b1 === 0b00000001 // true

---

Toutes les opérations au niveau du bit sont effectuées sur des nombres binaires 32 bits en JavaScript.
Autrement dit, avant qu'une opération au niveau du bit ne soit effectuée, JavaScript convertit les nombres en entiers **signés* 32 bits.*

Ainsi, par exemple, 17 ne sera pas simplement 10001 mais 00000000 00000000 00000000 00010001.

Une fois l'opération au niveau du bit effectuée, le résultat est reconverti en nombres JavaScript 64 bits.

Opérateurs au niveau du bit

ET (&)

Si deux bits valent 1, le résultat est 1, sinon 0.

Note

The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const n = 17;

console.log(n.toString(2)); // 10001

OU (|)

Si l'un des bits est 1, le résultat est 1, sinon 0.

console.log(parseInt(10001, 2)); // 17

XOR (^)

Si les bits sont différents (l'un vaut 1 et l'autre vaut 0), le résultat est 1, sinon 0.

console.log(0b10001); // 17
console.log(0b101); // 5

PAS (~)

Inverse les bits (1 devient 0, 0 devient 1).

0b1 === 0b00000001 // true

Note

Bitwise NOTing any 32-bit integer x yields -(x 1).

Si nous utilisons une fonction d'assistance pour voir les représentations binaires, c'est comme prévu :

const n = 17;

console.log(n.toString(2)); // 10001

Le bit le plus à gauche indique le signal — si le nombre est négatif ou positif.

N'oubliez pas que nous avons dit que JavaScript utilise des entiers signés 32 bits pour les opérations au niveau du bit.
Le bit le plus à gauche est 1 pour les nombres négatifs et 0 pour les nombres positifs.
De plus, l'opérateur opère sur les représentations binaires des opérandes en complément à deux. L'opérateur est appliqué à chaque bit et le résultat est construit au niveau du bit.

Notez que le complément à deux permet d'obtenir un nombre avec un signal inverse.
Une façon de le faire est d'inverser les bits du nombre dans la représentation positive et d'y ajouter 1 :

console.log(parseInt(10001, 2)); // 17

Décalage vers la gauche (remplissage zéro) (<<)

Décale le nombre de bits donné vers la gauche, en ajoutant zéro bit décalé depuis la droite.

console.log(0b10001); // 17
console.log(0b101); // 5

Notez que le 32ème bit (celui le plus à gauche) est ignoré.

Décalage vers la droite (préservation des signes) (>>)

Décale le nombre de bits donné vers la droite, en préservant le signe lors de l'ajout de bits par la gauche.

0b1 === 0b00000001 // true

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

Décalage vers la droite (non signé) (>>>)

Décale le nombre de bits donné vers la droite, en ajoutant des 0 lors de l'ajout de bits par la gauche, quel que soit le signe.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

---

Obtenir un peu

Pour obtenir un bit spécifique, nous devons d'abord créer un masque de bits.
Nous pouvons le faire en décalant 1 vers la gauche de l'index du bit que nous voulons obtenir.
Le résultat est le et du nombre binaire et du masque de bits.

Cependant, en utilisant JavaScript, nous pouvons également effectuer un décalage à droite non signé de l'index pour mettre le bit en premier lieu (afin que nous n'obtenions pas la valeur réelle qui se trouve dans cette position, mais s'il s'agit d'un 1 ou un 0) :

const n = 17;

const result = ~n; // -18

Par exemple, essayons 13, qui vaut 1101 en binaire :

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

Régler un peu

Si nous voulons tourner un peu à 1 (en d'autres termes, "mettre un peu"), nous pouvons faire une chose similaire.

Tout d'abord, nous pouvons créer à nouveau un masque de bits en décalant 1 vers la gauche de l'index du bit que nous voulons mettre à 1.
Le résultat est le ou du nombre et du masque de bits :

function twosComplement(n) {
  return ~n + 0b1;
}

Rappelez-vous que dans notre exemple 13 était 1101 en binaire, disons que nous voulons définir le 0 à l'index 1 :

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

---

Nous avons brièvement examiné les opérations au niveau du bit, ainsi que l'obtention/la configuration d'un peu. Dans ce dernier chapitre, nous examinerons cinq problèmes, en commençant par le nombre de 1 bits. En attendant, bon codage.

Ressources

• "Les éléments essentiels absolus de la manipulation de bits en JavaScript" - Lucas F. Costa
• Opérateurs au niveau du bit JS
• Numéro (MDN)
• ET au niveau du bit (MDN)
• Non au niveau du bit (MDN)
• OU au niveau du bit (MDN)
• XOR au niveau du bit (MDN)
• Décalage vers la gauche (MDN)
• Décalage à droite (MDN)
• Décalage à droite non signé (MDN)

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!