Super Introduction Arithmétique Bit Python
Cette section décrit les bases des opérations sur les bits effectuées sur des nombres binaires. Python est utilisé pour l'explication.
Nombre binaire
Décrivez avec «0b». Si vous le saisissez dans REPL, il sera converti en nombre décimal.
>>> 0b101
5
Utilisez bin () pour convertir en un nombre binaire.
>>> bin(5)
'0b101'
Hexadécimal
Vous pouvez convertir de l'hexadécimal en binaire en écrivant le nombre d'origine en hexadécimal.
>>> bin(0x12)
'0b10010'
Utilisez hex () pour convertir en hexadécimal.
>>> hex(0b10010)
'0x12'
décalage
Décalez les chiffres. Il existe un décalage à gauche et un décalage à droite en fonction de la direction.
Décalage à gauche
L'opérateur «<<». Décale le chiffre spécifié vers la gauche et 0 est entré dans le bit vide.
Un exemple est présenté avec une justification correcte.
| Entrée | Sortie |
|---|---|
| bin(5<<0) | '0b101' |
| bin(5<<1) | '0b1010' |
| bin(5<<2) | '0b10100' |
| bin(5<<3) | '0b101000' |
Shift vers la droite
L'opérateur «>>». Décale le chiffre spécifié vers la droite et les bits extrudés avant le plus petit ordre disparaissent.
Un exemple est présenté avec une justification correcte.
| Entrée | Sortie |
|---|---|
| bin(5>>0) | '0b101' |
| bin(5>>1) | '0b10' |
| bin(5>>2) | '0b1' |
| bin(5>>3) | '0b0' |
Opération logique
C'est un calcul pour chaque chiffre du nombre binaire.
L'idée de base est le traitement avec des valeurs booléennes, où 1 est considéré comme vrai et 0 est considéré comme faux.
Produit logique (ET)
L'opérateur «&». Ne tient (1) que lorsque ** les deux ** sont vrais (1). Si vous ne regardez qu'un seul chiffre, c'est la même chose que la multiplication.
| AND | multiplication | résultat |
|---|---|---|
| 0 & 0 | 0 * 0 | 0 |
| 0 & 1 | 0 * 1 | 0 |
| 1 & 0 | 1 * 0 | 0 |
| 1 & 1 | 1 * 1 | 1 |
Pour plusieurs chiffres, chaque chiffre est multiplié indépendamment sans tenir compte de toute retenue.
10010010
&) 10100111
-----------
10000010
Vérifiez avec Python.
>>> bin(0b10010010 & 0b10100111)
'0b10000010'
Somme logique (OR)
L'opérateur «|». Si l'un ou l'autre ** est vrai (1), il tient (1). Si vous regardez un seul chiffre, c'est similaire à l'addition, mais tous les 1 ou plus du résultat du calcul sont traités comme 1 (2 → 1).
| OR | une addition | résultat |
|---|---|---|
| 0 | 0 | 0 + 0 | 0 |
| 0 | 1 | 0 + 1 | 1 |
| 1 | 0 | 1 + 0 | 1 |
| 1 | 1 | 1 + 1 | 2→1 |
Pour plusieurs chiffres, ajoutez chaque chiffre indépendamment sans tenir compte de report. Tous les 1 ou plus des résultats de calcul sont traités comme 1 (2 → 1).
10010010
|) 10100111
-----------
10110111
Vérifiez avec Python.
>>> bin(0b10010010 | 0b10100111)
'0b10110111'
Somme logique exclusive (XOR)
L'opérateur «^». Si ** un seul ** est vrai (1), il contient (1) (le point incompatible est ** exclusif **). Si vous ne regardez qu'un seul chiffre binaire, c'est une addition qui élimine le report (1 + 1 = 2 = 0b10 → 0).
| XOR | une addition | résultat |
|---|---|---|
| 0 ^ 0 | 0 + 0 | 0 |
| 0 ^ 1 | 0 + 1 | 1 |
| 1 ^ 0 | 1 + 0 | 1 |
| 1 ^ 1 | 1 + 1 | 2→0 |
Pour plusieurs chiffres, ajoutez chaque chiffre indépendamment sans tenir compte de report.
10010010
^) 10100111
-----------
00110101
Vérifiez avec Python.
>>> bin(0b10010010 ^ 0b10100111)
'0b110101'
Il a la propriété que si vous XOR deux fois avec la même valeur, il reviendra à la valeur d'origine.
a ^ b ^ b→a
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'
Vous pouvez également effacer la valeur d'origine.
a ^ b ^ a→b
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10010010)
'0b10100111'
Inverser (PAS)
L'opérateur «~». Inverser 0 et 1.
En Python, le chiffre supérieur est supposé être rempli à l'infini de 0, et l'inversion renvoie également un moins en supposant que le chiffre supérieur est infiniment rempli de 1.
>>> ~1
-2
Ce calcul signifie «000 ... 0001» → «111 ... 1110».
Comme nous le verrons plus tard dans la combinaison de AND et NOT, nous nous concentrons généralement uniquement sur les bits et non sur les valeurs numériques spécifiques (moins ici). Si l'idée de signe vous intéresse, veuillez vous référer à l'article suivant.
-
@ 7shi: Pensée intuitive des nombres signés 2014.10.8
-
L'expression
~ x→- (x + 1)peut être introduite en se concentrant uniquement sur la valeur. Même si vous regardez cela, vous ne comprenez pas la signification de l'inversion de bits, donc je ne vais pas approfondir ici.
Exemple d'utilisation
L'opération sur les bits est souvent utilisée lors de l'extraction de certains bits seulement.
Masque de bits
Lors de l'extraction uniquement de la partie nécessaire du bit, ET de la partie nécessaire avec le numéro mis à 1.
Exemple: extraire les 3 bits inférieurs (partie en gras) de 101 110 </ strong>.
101110
&) 000111
---------
000110
Utilisation combinée avec shift
Si vous souhaitez extraire uniquement les bits du milieu, utilisez la combinaison de décalage et de masque.
Exemple: extraire les 2 bits du milieu (partie en gras) de 10 11 </ strong> 10.
>>> bin((0b101110 >> 2) & 0b11)
'0b11'
Utilisation combinée avec NOT
Lorsque vous utilisez NOT en combinaison avec AND, cela signifie que vous pouvez l'utiliser sans vous soucier du résultat négatif de NOT.
En masquant le résultat du calcul NOT avec AND, vous pouvez limiter le nombre de chiffres et éliminer les négatifs.
>>> bin(~1 & 0b1111)
'0b1110'
Ce calcul montre l'inversion de «0001» → «1110» en le limitant à 4 chiffres binaires.
NOT est souvent utilisé pour créer des valeurs de masque, et même dans ce cas, nous ne sommes pas conscients des inconvénients.
Par exemple, si vous souhaitez effacer uniquement les 2 bits centraux (partie en gras) de 10 11 </ strong> 10, vous pouvez utiliser NOT pour vous concentrer sur la partie que vous souhaitez effacer.
>>> bin(0b101110 & ~0b001100)
'0b100010'
Voici le code qui n'utilise PAS pour la comparaison. Je fais attention à la part que je souhaite conserver.
>>> bin(0b101110 & 0b110011)
'0b100010'
Composition de bits
Si vous souhaitez conserver plusieurs valeurs dans des positions différentes, utilisez les touches Maj et OR ensemble.
Exemple: Combinez «101» et «110» côte à côte en une seule valeur.
>>> bin((0b101 << 3) | 0b110)
'0b101110'
Utilisation combinée avec AND
Si une autre valeur se trouve déjà dans la partie que vous souhaitez combiner, effacez-la d'abord avec ET puis OU.
Exemple: remplacez les 3 bits inférieurs (partie en gras) de 101 101 </ strong> par «011».
101101
&) 111000
---------
101000
|) 011
---------
101011
Vérifiez avec Python.
>>> bin(0b101101 & 0b111000 | 0b011)
'0b101011'
Cette technique est également utilisée pour combiner des arrière-plans et des caractères dans la génération d'images.
Trouver des erreurs
Vous pouvez utiliser XOR pour voir les différents bits des deux nombres.
11101011101110101
^) 11101101101110101
--------------------
00000110000000000
Vérifiez avec Python.
>>> bin(0b11101011101110101 ^ 0b11101101101110101)
'0b110000000000'
Échangez les valeurs
[Note] Ceci est une introduction en tant que connaissance plutôt que pratique.
Dans l'application de multiples XOR, il existe une technique d'échange des valeurs de variables.
- [XOR Exchange Algorithm-Wikipedia](http://ja.wikipedia.org/wiki/XOR%E4%BA%A4%E6%8F%9B%E3%82%A2%E3%83%AB%E3%82 % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)
Vérifiez avec Python.
>>> a = 12
>>> b = 34
>>> a, b
(12, 34)
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> a, b
(34, 12)
En pratique, il est plus facile d'utiliser le tapple.
>>> a, b = b, a
Relation avec le calcul
Un certain type de calcul peut être remplacé par une opération sur bit. Voici quelques exemples couramment utilisés.
multiplication
Les nombres binaires doublent à mesure que les chiffres augmentent.
| Nombre binaire | Nombre décimal | Décalage à gauche | Calcul |
|---|---|---|---|
| 0b1 | 1 | 1 << 0 | |
| 0b10 | 2 | 1 << 1 | |
| 0b100 | 4 | 1 << 2 | |
| 0b1000 | 8 | 1 << 3 |
Autrement dit, «1 << n» est égal à 2 $ ^ n $.
Chaque fois que vous décalez un nombre arbitraire de 1 bit vers la gauche, il double.
| Décalage à gauche | multiplication | production |
|---|---|---|
| bin(5<<0) | bin(5) | '0b101' |
| bin(5<<1) | bin(5*2) | '0b1010' |
| bin(5<<2) | bin(522) | '0b10100' |
| bin(5<<3) | bin(522*2) | '0b101000' |
En d'autres termes, "décalage de n bits à gauche" a le même résultat que "multiplication de 2 $ ^ n $".
division
Dans la théorie opposée, "décalage à droite de n bits" a le même résultat que "division $ 2 ^ n $ (troncature)".
| Shift vers la droite | division | production |
|---|---|---|
| bin(45>>0) | bin(45) | '0b101101' |
| bin(45>>1) | bin(45/2) | '0b10110' |
| bin(45>>2) | bin(45/2/2) | '0b1011' |
| bin(45>>3) | bin(45/2/2/2) | '0b101' |
Résidu de division
"Le reste de la division par $ 2 ^ n $" est égal à "ET avec $ 2 ^ n-1 $".
x % (2 ** n)==x & ((2 ** n) - 1)
Exemple: x% 8 == x & 7
La description
J'expliquerai la raison pour laquelle cela est vrai aussi intuitivement que possible.
Décaler «0b110101» vers la droite de 3 bits équivaut à diviser par 2 $ ^ 3 = 8 $ et à tronquer.
>>> bin(0b110101 >> 3)
'0b110'
>>> bin(0b110101 / 8)
'0b110'
Les 3 bits inférieurs «101» extrudés par le décalage à ce moment correspondent au reste de la division. Vous pouvez le récupérer en le masquant avec «111».
>>> bin(0b110101 & 0b111)
'0b101'
>>> bin(0b110101 % 8)
'0b101'
«0b111» est «7», c'est-à-dire «8-1». Cela a confirmé la relation suivante.
x % 8==x & 7
Dévaluation
"Effacer les n bits inférieurs" équivaut à "dévaluation à 2 $ ^ n $".
À titre d'exemple, la dévaluation à 2 $ ^ 3 = 8 $ due au décalage est indiquée. Le décalage à droite repousse les 3 bits inférieurs et le décalage à gauche revient à la largeur de bit d'origine.
>>> 15 >> 3 << 3
8
>>> 16 >> 3 << 3
16
>>> 17 >> 3 << 3
16
Il est également possible d'effacer un bit spécifique avec une combinaison de AND et NOT. Cela peut sembler déroutant au début, mais cette méthode est plus souvent utilisée que les quarts de travail.
>>> 15 & ~0b111
8
>>> 16 & ~0b111
16
>>> 17 & ~0b111
16
«0b111» est «7», c'est-à-dire «8-1». C'est une relation qui est également apparue dans la méthode de recherche du reste que nous avons vue précédemment.
En utilisant la relation «~ 7» → «-8», la dévaluation en 8 peut être exprimée par -8.
>>> 15 & -8
8
>>> 16 & -8
16
>>> 17 & -8
16
La première fois que vous voyez cela, vous pouvez ne pas le comprendre. Pour le moment, il suffit de reconnaître que "parfois c'est écrit dans une telle expression".
Recommended Posts