J'ai essayé d'apprendre C dans mon temps libre, et d'autres langages (C#, Java, etc.) ont le même concept (et souvent les mêmes opérateurs) ...
Ce que je me demande, à un niveau de base, ce qui n'décalage de bits (<<, >>, >>>) faire, quels problèmes peut-il aider à résoudre, et quels pièges se cachent autour de la courbe? En d'autres termes, un absolu guide du débutant pour le décalage de bits dans toute sa bonté.
Les opérateurs de décalage de bits à faire exactement ce que leur nom l'indique. Ils décalage de bits. Voici un petit (ou pas si brève) présentation des différents opérateurs de décalage.
>> est la moyenne (ou signé) décalage à droite de l'opérateur.>>> est la logique (ou non signé) décalage à droite de l'opérateur. << est le décalage à gauche de l'opérateur, et qui répond aux besoins à la fois de logique et de l'arithmétique des quarts de travail.Tous ces opérateurs peuvent être appliqués à des valeurs entières (int, long,, éventuellement, short et byte ou char). Dans certaines langues, en appliquant les opérateurs de décalage à tout type de données plus petit que int redimensionne automatiquement l'opérande à un int.
Notez que <<< n'est pas un opérateur, parce que ce serait redondant. Notez également que le C et le C++ ne pas distingiush entre le droit d'opérateurs de décalage. Ils fournissent seulement l' >> de l'opérateur, et le décalage de comportement est définie par l'implémentation.
Les entiers sont stockés dans la mémoire, comme une série de bits. Par exemple, le nombre 6 stockées en 32 bits int serait:
00000000 00000000 00000000 00000110
L'évolution de cette séquence de bits vers la gauche d'une position (6 << 1) aurait pour conséquence le nombre de 12:
00000000 00000000 00000000 00001100
Comme vous pouvez le voir, les chiffres ont décalé vers la gauche par une position, et le dernier chiffre à droite est rempli avec un zéro. Vous pouvez également noter que le passage de gauche est équivalent à une multiplication par des puissances de 2. Donc, 6 << 1 est équivalent à 6 * 2, et 6 << 3 est équivalent à 6 * 8. Une bonne optimisation du compilateur remplacera changements pour les multiplications lorsque cela est possible.
Veuillez noter que ce ne sont pas circulaire quarts de travail. L'évolution de cette valeur à la gauche d'une position (3,758,096,384 << 1):
11100000 00000000 00000000 00000000
résultats dans 3,221,225,472:
11000000 00000000 00000000 00000000
Les chiffres qui obtient décalé "à la fin" est perdu. Il n'est pas autour.
Une logique décalage à droite est l'inverse pour le décalage à gauche. Plutôt que de déplacer des bits vers la gauche, il suffit de déplacer vers la droite. Par exemple, passer le nombre de 12:
00000000 00000000 00000000 00001100
à la droite d'une position (12 >>> 1) de revenir a l'origine, notre 6:
00000000 00000000 00000000 00000110
Nous voyons donc que se décalant sur la droite est l'équivalent de la division par puissances de 2.
Toutefois, un changement ne peut pas récupérer la "perte" de bits. Par exemple, si l'on passe ce modèle:
00111000 00000000 00000000 00000110
à la gauche de la 4 positions (939,524,102 << 4), nous obtenons 2,147,483,744:
10000000 00000000 00000000 01100000
et puis le retour ((939,524,102 << 4) >>> 4) nous obtenons 134,217,734:
00001000 00000000 00000000 00000110
Nous ne pouvons pas revenir notre valeur d'origine une fois que nous avons perdu bits.
L'arithmétique décalage à droite est exactement comme la logique décalage à droite, sauf qu'au lieu de rembourrage à zéro, il remplit avec le bit le plus significatif. C'est parce que le bit le plus significatif est le signe bits, ou le peu qui distingue les nombres positifs et négatifs. Par remplissage avec le bit le plus significatif, l'arithmétique décalage à droite est le signe de la préservation de.
Par exemple, si nous interprétons cette séquence de bits comme un nombre négatif:
10000000 00000000 00000000 01100000
nous avons le nombre -2,147,483,552. L'évolution de cette à la droite de 4 positions avec le décalage (-2,147,483,552 >> 4) nous donnerait:
11111000 00000000 00000000 00000110
ou le nombre -134,217,722.
Nous voyons donc que nous avons conservé le signe des nombres négatifs en utilisant l'arithmétique des maj de droite, plutôt que de la logique décalage à droite. Et encore une fois, nous voyons que nous sommes en effectuant la division par puissances de 2.
Disons que nous avons un seul octet:
0110110
L'application d'un seul de gauche Bitshift nous obtient:
1101100
Le plus à gauche du zéro a été déplacé hors de l'octet, et un nouveau zéro a été ajouté à l'extrémité droite de l'octet.
Les bits ne sont pas de roulement, elles sont ignorées, ce qui signifie que si vous maj gauche 1101100, puis à droite passer, vous n'obtiendrez pas le même résultat.
Décalage à gauche par N est équivalent à multiplier par 2N.
Décalage à droite de N est (si vous utilisez ceux compliment) est l'équivalent de la division par 2N et arrondi à zéro.
Bitshifting peut être utilisé pour incroyablement rapide de multiplication et de division, à condition que vous travaillez avec une puissance de 2, presque toutes les routines graphiques de l'utilisation bitshifting.
Par exemple, le chemin du retour dans les temps anciens, nous avons utilisé le mode 13h (320x200 en 256 couleurs) pour les jeux. En Mode 13h, la mémoire vidéo a été aménagé de façon séquentielle par pixel. Que signifiait pour calculer la position d'un pixel, vous pouvez utiliser le calcul suivant:
memoryOffset = (row * 320) + column
Maintenant, de retour dans cette journée et l'âge, de la vitesse, de sorte que nous pourrions utiliser bitshifts pour effectuer cette opération.
Cependant, 320 n'est pas une puissance de deux, de sorte à obtenir autour de cela, nous devons savoir ce qu'est une puissance de deux qui additionné fait 320:
(row * 320) = (row * 256) + (row * 64)
Maintenant, nous pouvons convertir en de gauche changements:
(row * 320) = (row << 8) + (row << 6)
Pour un résultat final de:
memoryOffset = ((row << 8) + (row << 6)) + column
Maintenant, nous obtenons la même position qu'avant, sauf qu'au lieu d'une coûteuse opération de multiplication, nous utilisons les deux bitshifts...en x86, il serait quelque chose comme ceci (à noter, sa fait toujours depuis que j'ai fait le montage):
mov al, 320; 2 cycles
mul [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
Total: 28 cycles
Vrs
mov al, [row]; 2
mov di,[row]; 2
shl al, 6; 2
shl di, 8; 2
add al, di; 2
add [column], ax; 2
12 cycles.
Oui, nous devons travailler dur pour se raser 16 cycles de processeur.
Ok, dans les temps modernes... quelque chose de plus utile serait d'utiliser bitshifting de stocker deux 8-bit valeurs dans un entier 16 bits, par exemple, en C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
Les opérations bit à bit, y compris de décalage de bits, sont fondamentales pour le bas niveau hw ou de la programmation embarquée. Si vous lisez une spécification pour un appareil ou même certains formats de fichier binaires, vous verrez octets, de mots, et dwords, divisé en non-octets aligné bitfields, qui contiennent des valeurs différentes d'intérêt. L'accès à ces bits-champs pour la lecture/écriture est l'utilisation la plus courante.
Un simple exemple réel dans les graphiques de programmation est un 16-bit pixel est représenté comme suit:
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |
Pour obtenir la valeur verte vous voulez faire cela:
#define GREEN_MASK 0x7e0
#define GREEN_OFFSET 5
// read grean
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Est également commune à l'aide de bits changements rapides de multiplication et de division par puissances de 2.
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
