Opérations bit à bit

On a parfois à manipuler l'écriture binaire d'un entier. On utilise alors les opérateurs suivants:

• et : &. Effectue un et sur chacun des bits de ses deux opérandes. Ainsi 6&3 vaut 2 puisque $0110_2\ and\ 0011_2=0010_2$.
• ou : |. Effectue un ou sur chacun des bits de ses deux opérandes. Ainsi 6|3 vaut 7 puisque $0110_2\ or\ 0011_2=0111_2$.
• ou exclusif : ^. Effectue un ou exclusif sur chacun des bits de ses deux opérandes. Ainsi 6^3 vaut 5 puisque $0110_2\ xor\ 0011_2=0101_2$.
• décalage à droite : >>n. Effectue un décalage à droite de n crans de tous les bits (ceux le plus à droite << tombent dans le vide >>, des zéros rentrent par la gauche). Ainsi 14>>2 vaut 3 puisque $1110_2\ shr\ 2\ =0011_2$.
• décalage à gauche : <<n. Effectue un décalage à gauche de n crans de tous les bits (ceux le plus à gauche << tombent dans le vide >>, des zéros rentrent par la droite). Ainsi 3<<2 vaut 12 puisque $0011_2\ shl\ 2\ =001100_2$.
• complémentaire : ~. Effectue un complément de tous les bits (les zéros deviennent des 1 et réciproquement). Ainsi ~5 vaut -6 puisque $comp\ 00...0101_2=11...11010_2$, qui se trouve valoir -6 (car $0=0...0_2,\ 1=0...01_2,\ 2=0...010_2,$ etc., mais $-1=1...1_2,\ -2=1...10_2,\ -3=1...101_2,$ $-4=1...100_2,$ etc.)

Ces opérateurs sont utilisés pour travailler sur les bits de la façon suivante :

• Lever le $n^\mathrm{eme}$ bit : i |= (1<<n)
• Baisser le $n^\mathrm{eme}$ bit : i &= ~(1<<n)
• Complémenter le $n^\mathrm{eme}$ bit : i ^= (1<<n)
• Tester si le $n^\mathrm{eme}$ bit est levé : if (i&(1<<n)) ...

mais aussi dans les cas fréquents suivants où elles accélèrent le programme :

• Non-parité d'un nombre : if (i&1) ... et plus généralement pour calculer le reste de la division par une puissance de 2 : j = i&63 équivaut à j = i%64
• Division par 2 : j = i>>1 et plus généralement pour calculer le quotient de la division par une puissance de 2 : j = i>>6 équivaut à j = i/64;
• Multiplication par 2 : j = i<<1 et plus généralement pour toute multiplication par une puissance de 2 : j = i<<6 équivaut à j = i*64;.
  Cas particulier important : on utilise 1<<n pour obtenir $2^n$.