Fonctionnement et utilisation au niveau du bit

Considérez ce code:

x = 1        # 0001
x << 2       # Shift left 2 bits: 0100
# Result: 4

x | 2        # Bitwise OR: 0011
# Result: 3

x & 1        # Bitwise AND: 0001
# Result: 1

Je peux comprendre les opérateurs arithmétiques en Python (et dans d'autres langages), mais je n'ai jamais très bien compris les opérateurs «bit à bit». Dans l'exemple ci-dessus (tiré d'un livre Python), je comprends le décalage à gauche mais pas les deux autres.

En outre, à quoi servent réellement les opérateurs bit à bit? J'apprécierais quelques exemples.

Les opérateurs au niveau du bit sont des opérateurs qui travaillent sur des valeurs multi-bits, mais conceptuellement un bit à la fois.

• ANDest 1 seulement si ses deux entrées sont 1, sinon c'est 0.
• ORvaut 1 si l' une ou les deux de ses entrées sont 1, sinon c'est 0.
• XORvaut 1 seulement si exactement l'une de ses entrées est 1, sinon c'est 0.
• NOT vaut 1 uniquement si son entrée est 0, sinon c'est 0.

Celles-ci peuvent souvent être mieux présentées sous forme de tables de vérité. Les possibilités d'entrée sont en haut et à gauche, le bit résultant est l'une des quatre (deux dans le cas de NOT car il n'a qu'une seule entrée) valeurs indiquées à l'intersection des entrées.

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+-----    ---+----     ----+----    ----+----
 0  | 0 0      0 | 0 1       0 | 0 1        | 1 0
 1  | 0 1      1 | 1 1       1 | 1 0

Un exemple est que si vous ne voulez que les 4 bits inférieurs d'un entier, vous ET avec 15 (binaire 1111) ainsi:

    201: 1100 1001
AND  15: 0000 1111
------------------
 IS   9  0000 1001

Les bits de zéro dans 15 dans ce cas agissent effectivement comme un filtre, forçant les bits du résultat à être également zéro.

De plus, >>et <<sont souvent inclus les opérateurs au niveau du bit, et ils « changement » d' une valeur respectivement à droite et à gauche par un certain nombre de bits, jeter bits rouleau de la fin que vous êtes déplacer vers, et l' alimentation en zéro bits à la autre fin.

Ainsi, par exemple:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Notez que le décalage à gauche en Python est inhabituel en ce qu'il n'utilise pas une largeur fixe où les bits sont supprimés - alors que de nombreux langages utilisent une largeur fixe basée sur le type de données, Python élargit simplement la largeur pour prendre en charge des bits supplémentaires. Afin d'obtenir le comportement d'élimination en Python, vous pouvez suivre un décalage vers la gauche avec un bit par andexemple, comme dans une valeur de 8 bits décalant vers la gauche de quatre bits:

bits8 = (bits8 << 4) & 255

Dans cet esprit, un autre exemple des opérateurs est au niveau du bit si vous avez deux valeurs de 4 bits que vous voulez emballer dans un un 8 bits, vous pouvez utiliser tous les trois de vos opérateurs ( left-shift, andet or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)

• L' & 15opération s'assurera que les deux valeurs n'ont que les 4 bits inférieurs.
• Le << 4est un décalage de 4 bits vers la gauche pour se déplacer val1dans les 4 premiers bits d'une valeur de 8 bits.
• Le |combine simplement ces deux ensemble.

Si val1vaut 7 et val24:

                val1            val2
                ====            ====
 & 15 (and)   xxxx-0111       xxxx-0100  & 15
 << 4 (left)  0111-0000           |
                  |               |
                  +-------+-------+
                          |
| (or)                0111-0100

Une utilisation typique:

| est utilisé pour mettre un certain bit à 1

& est utilisé pour tester ou effacer un certain bit

• Définissez un bit (où n est le numéro de bit et 0 est le bit le moins significatif):

  unsigned char a |= (1 << n);

• Effacer un peu:

  unsigned char b &= ~(1 << n);

• Basculez un peu:

  unsigned char c ^= (1 << n);

• Testez un peu:

  unsigned char e = d & (1 << n);

Prenons le cas de votre liste par exemple:

x | 2est utilisé pour mettre le bit 1 de xà 1

x & 1est utilisé pour tester si le bit 0 de xest 1 ou 0

à quoi servent réellement les opérateurs bit à bit? J'apprécierais quelques exemples.

L'une des utilisations les plus courantes des opérations au niveau du bit est l'analyse des couleurs hexadécimales.

Par exemple, voici une fonction Python qui accepte un String comme #FF09BEet renvoie un tuple de ses valeurs Rouge, Vert et Bleu.

def hexToRgb(value):
    # Convert string to hexadecimal number (base 16)
    num = (int(value.lstrip("#"), 16))

    # Shift 16 bits to the right, and then binary AND to obtain 8 bits representing red
    r = ((num >> 16) & 0xFF)

    # Shift 8 bits to the right, and then binary AND to obtain 8 bits representing green
    g = ((num >> 8) & 0xFF)

    # Simply binary AND to obtain 8 bits representing blue
    b = (num & 0xFF)
    return (r, g, b)

Je sais qu'il existe des moyens plus efficaces pour y parvenir, mais je pense que c'est un exemple vraiment concis illustrant à la fois les décalages et les opérations booléennes au niveau du bit.

Je pense que la deuxième partie de la question:

En outre, à quoi servent réellement les opérateurs bit à bit? J'apprécierais quelques exemples.

N'a été que partiellement abordé. Ce sont mes deux cents à ce sujet.

Les opérations au niveau du bit dans les langages de programmation jouent un rôle fondamental dans le traitement de nombreuses applications. Presque tous les calculs de bas niveau doivent être effectués à l'aide de ce type d'opérations.

Dans toutes les applications qui doivent envoyer des données entre deux nœuds, telles que:

• réseaux informatiques;

• applications de télécommunications (téléphones cellulaires, communications par satellite, etc.).

Dans la couche de communication de niveau inférieur, les données sont généralement envoyées dans ce qu'on appelle des trames . Les trames ne sont que des chaînes d'octets envoyées via un canal physique. Ces trames contiennent généralement les données réelles plus quelques autres champs (codés en octets) qui font partie de ce qu'on appelle l'en- tête . L'en-tête contient généralement des octets qui codent certaines informations relatives à l'état de la communication (par exemple, avec des indicateurs (bits)), des compteurs de trame, des codes de correction et de détection d'erreur, etc. Pour obtenir les données transmises dans une trame, et pour construire le frames pour envoyer des données, vous aurez besoin pour certaines opérations au niveau du bit.

En général, lorsque vous traitez avec ce type d'applications, une API est disponible pour que vous n'ayez pas à gérer tous ces détails. Par exemple, tous les langages de programmation modernes fournissent des bibliothèques pour les connexions socket, vous n'avez donc pas réellement besoin de créer les trames de communication TCP / IP. Mais pensez aux bonnes personnes qui ont programmé ces API pour vous, elles ont dû s'occuper de la construction du cadre à coup sûr; en utilisant toutes sortes d'opérations au niveau du bit pour aller et venir de la communication de bas niveau à la communication de niveau supérieur.

À titre d'exemple concret, imaginez que quelqu'un vous donne un fichier contenant des données brutes qui ont été capturées directement par le matériel de télécommunication. Dans ce cas, pour trouver les trames, vous devrez lire les octets bruts dans le fichier et essayer de trouver une sorte de mots de synchronisation, en scannant les données bit par bit. Après avoir identifié les mots de synchronisation, vous devrez obtenir les images réelles et les SHIFT si nécessaire (et ce n'est que le début de l'histoire) pour obtenir les données réelles qui sont transmises.

Une autre famille d'applications de bas niveau très différente est lorsque vous devez contrôler le matériel à l'aide de certains ports (anciens), tels que les ports parallèles et série. Ces ports sont contrôlés en définissant certains octets, et chaque bit de ces octets a une signification spécifique, en termes d'instructions, pour ce port (voir par exemple http://en.wikipedia.org/wiki/Parallel_port ). Si vous souhaitez créer un logiciel qui fait quelque chose avec ce matériel, vous aurez besoin d'opérations au niveau du bit pour traduire les instructions que vous souhaitez exécuter en octets que le port comprend.

Par exemple, si vous avez des boutons physiques connectés au port parallèle pour contrôler un autre périphérique, il s'agit d'une ligne de code que vous pouvez trouver dans l'application logicielle:

read = ((read ^ 0x80) >> 4) & 0x0f; 

J'espère que cela contribue.

J'espère que cela clarifie ces deux:

x | 2

0001 //x
0010 //2

0011 //result = 3

x & 1

0001 //x
0001 //1

0001 //result = 1

Considérez 0 comme faux et 1 comme vrai. Ensuite, au niveau du bit et (&) et ou (|) fonctionnent exactement comme des et et ou, sauf qu'ils font tous les bits de la valeur à la fois. En règle générale, vous les verrez utilisés pour les indicateurs si vous avez 30 options qui peuvent être définies (par exemple, en tant que styles de dessin sur une fenêtre), vous ne voulez pas avoir à passer 30 valeurs booléennes distinctes pour définir ou annuler chacune d'entre elles, vous utilisez donc | pour combiner les options en une seule valeur, puis vous utilisez & pour vérifier si chaque option est définie. Ce style de passage de drapeau est largement utilisé par OpenGL. Étant donné que chaque bit est un indicateur séparé, vous obtenez des valeurs d'indicateur sur des puissances de deux (c'est-à-dire des nombres qui n'ont qu'un seul bit défini) 1 (2 ^ 0) 2 (2 ^ 1) 4 (2 ^ 2) 8 (2 ^ 3) le la puissance de deux vous indique quel bit est activé si le drapeau est activé.

Notez également 2 = 10 donc x | 2 vaut 110 (6) et non 111 (7) Si aucun des bits ne se chevauche (ce qui est vrai dans ce cas) | agit comme une addition.

Je ne l'ai pas vu mentionné ci-dessus, mais vous verrez également que certaines personnes utilisent le décalage gauche et droit pour les opérations arithmétiques. Un décalage vers la gauche par x équivaut à multiplier par 2 ^ x (tant qu'il ne déborde pas) et un décalage vers la droite équivaut à une division par 2 ^ x.

Récemment, j'ai vu des gens utiliser x << 1 et x >> 1 pour doubler et diviser par deux, bien que je ne sois pas sûr s'ils essayaient simplement d'être intelligents ou s'il y avait vraiment un avantage distinct sur les opérateurs normaux.

Ensembles

Les ensembles peuvent être combinés à l'aide d'opérations mathématiques.

• L'opérateur union |combine deux ensembles pour en former un nouveau contenant des éléments dans l'un ou l'autre.
• L'opérateur d'intersection &obtient des éléments uniquement dans les deux.
• L'opérateur de différence -obtient des éléments dans le premier ensemble mais pas dans le second.
• L'opérateur de différence symétrique ^obtient des éléments dans l'un ou l'autre ensemble, mais pas dans les deux.

Essayez-le vous-même:

first = {1, 2, 3, 4, 5, 6}
second = {4, 5, 6, 7, 8, 9}

print(first | second)

print(first & second)

print(first - second)

print(second - first)

print(first ^ second)

Résultat:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

{4, 5, 6}

{1, 2, 3}

{8, 9, 7}

{1, 2, 3, 7, 8, 9}

Cet exemple vous montrera les opérations pour les quatre valeurs de 2 bits:

10 | 12

1010 #decimal 10
1100 #decimal 12

1110 #result = 14

10 & 12

1010 #decimal 10
1100 #decimal 12

1000 #result = 8

Voici un exemple d'utilisation:

x = raw_input('Enter a number:')
print 'x is %s.' % ('even', 'odd')[x&1]

Un autre cas d'utilisation courant est la manipulation / le test des autorisations de fichiers. Voir le module de statistiques Python: http://docs.python.org/library/stat.html .

Par exemple, pour comparer les autorisations d'un fichier à un ensemble d'autorisations souhaité, vous pouvez faire quelque chose comme:

import os
import stat

#Get the actual mode of a file
mode = os.stat('file.txt').st_mode

#File should be a regular file, readable and writable by its owner
#Each permission value has a single 'on' bit.  Use bitwise or to combine 
#them.
desired_mode = stat.S_IFREG|stat.S_IRUSR|stat.S_IWUSR

#check for exact match:
mode == desired_mode
#check for at least one bit matching:
bool(mode & desired_mode)
#check for at least one bit 'on' in one, and not in the other:
bool(mode ^ desired_mode)
#check that all bits from desired_mode are set in mode, but I don't care about 
# other bits.
not bool((mode^desired_mode)&desired_mode)

J'ai converti les résultats en booléens, car je ne me soucie que de la vérité ou du mensonge, mais ce serait un exercice intéressant d'imprimer les valeurs bin () pour chacun.

Les représentations binaires d'entiers sont souvent utilisées dans le calcul scientifique pour représenter des tableaux d'informations vrai-faux, car une opération au niveau du bit est beaucoup plus rapide que l'itération dans un tableau de booléens. (Les langages de niveau supérieur peuvent utiliser l'idée d'un tableau de bits.)

Un exemple sympa et assez simple de ceci est la solution générale au jeu de Nim. Jetez un œil au code Python sur la page Wikipédia . Il utilise beaucoup exclusif ou bitwise, ^.

Il peut y avoir un meilleur moyen de trouver où un élément de tableau est entre deux valeurs, mais comme le montre cet exemple, le & fonctionne ici, alors que et ne le fait pas.

import numpy as np
a=np.array([1.2, 2.3, 3.4])
np.where((a>2) and (a<3))      
#Result: Value Error
np.where((a>2) & (a<3))
#Result: (array([1]),)

Je ne l'ai pas vu mentionné, cet exemple vous montrera l'opération (-) décimale pour les valeurs de 2 bits: AB (uniquement si A contient B)

cette opération est nécessaire lorsque nous détenons un verbe dans notre programme qui représente des bits. parfois nous devons ajouter des bits (comme ci-dessus) et parfois nous devons supprimer des bits (si le verbe contient alors)

111 #decimal 7
-
100 #decimal 4
--------------
011 #decimal 3

avec python: 7 & ~ 4 = 3 (enlevez de 7 les bits qui représentent 4)

001 #decimal 1
-
100 #decimal 4
--------------
001 #decimal 1

avec python: 1 & ~ 4 = 1 (enlevez de 1 les bits qui représentent 4 - dans ce cas 1 n'est pas 'contient' 4) ..

Bien que la manipulation de bits d'un entier soit utile, souvent pour les protocoles réseau, qui peuvent être spécifiés jusqu'au bit, on peut exiger la manipulation de séquences d'octets plus longues (qui ne sont pas facilement converties en un entier). Dans ce cas, il est utile d'utiliser la bibliothèque de chaînes de bits qui permet des opérations au niveau du bit sur les données - par exemple, on peut importer la chaîne 'ABCDEFGHIJKLMNOPQ' en tant que chaîne ou en hexadécimal et la décaler (ou effectuer d'autres opérations au niveau du bit):

>>> import bitstring
>>> bitstring.BitArray(bytes='ABCDEFGHIJKLMNOPQ') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')
>>> bitstring.BitArray(hex='0x4142434445464748494a4b4c4d4e4f5051') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')

les opérateurs binaires suivants: & , | , ^ et ~ renvoient des valeurs (en fonction de leur entrée) de la même manière que les portes logiques affectent les signaux. Vous pouvez les utiliser pour émuler des circuits.

Pour inverser les bits (c'est-à-dire le complément / l'inversion de 1), vous pouvez faire ce qui suit:

Puisque la valeur ExORed avec tous les 1 entraîne une inversion, pour une largeur de bit donnée, vous pouvez utiliser ExOR pour les inverser.

In Binary
a=1010 --> this is 0xA or decimal 10
then 
c = 1111 ^ a = 0101 --> this is 0xF or decimal 15
-----------------
In Python
a=10
b=15
c = a ^ b --> 0101
print(bin(c)) # gives '0b101'