C++
Bit Manipulation

Remarques

#include <bitset>

Mettre un peu

Manipulation de bits de style C

Un bit peut être défini à l'aide de l'opérateur OU bit à bit ( | ).

// Bit x will be set
number |= 1LL << x; 

Utiliser std :: bitset

set(x) ou set(x,true) - définit bit à la position x sur 1 .

std::bitset<5> num(std::string("01100"));
num.set(0);      // num is now 01101
num.set(2);      // num is still 01101
num.set(4,true); // num is now 11110

Effacer un peu

Manipulation de bits de style C

Un bit peut être effacé à l'aide de l'opérateur AND bitwise ( & ).

// Bit x will be cleared
number &= ~(1LL << x);

Utiliser std :: bitset

reset(x) ou set(x,false) - efface le bit à la position x .

std::bitset<5> num(std::string("01100"));
num.reset(2);     // num is now 01000
num.reset(0);     // num is still 01000
num.set(3,false); // num is now 00000

En changeant un peu

Manipulation de bits de style C

Un bit peut être basculé à l'aide de l'opérateur XOR ( ^ ).

// Bit x will be the opposite value of what it is currently
number ^= 1LL << x;

Utiliser std :: bitset

std::bitset<4> num(std::string("0100"));
num.flip(2); // num is now 0000
num.flip(0); // num is now 0001
num.flip();  // num is now 1110 (flips all bits)

Vérification un peu

Manipulation de bits de style C

La valeur du bit peut être obtenue en décalant le nombre vers la droite x puis en effectuant un bit ET ( & ) dessus:

(number >> x) & 1LL;  // 1 if the 'x'th bit of 'number' is set, 0 otherwise

L'opération de décalage vers la droite peut être mise en œuvre sous la forme d'un décalage arithmétique (signé) ou d'un décalage logique (non signé). Si number dans le number >> x expression number >> x a un type signé et une valeur négative, la valeur résultante est définie par l'implémentation.

Si nous avons besoin de la valeur de ce bit directement sur place, nous pourrions au lieu de cela déplacer le masque:

(number & (1LL << x));  // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise

L'un ou l'autre peut être utilisé comme conditionnel, car toutes les valeurs non nulles sont considérées comme vraies.

Utiliser std :: bitset

std::bitset<4> num(std::string("0010"));
bool bit_val = num.test(1);  // bit_val value is set to true;

Changer le nième bit en x

Manipulation de bits de style C

// Bit n will be set if x is 1 and cleared if x is 0.
number ^= (-x ^ number) & (1LL << n);

Utiliser std :: bitset

set(n,val) - met le bit n à la valeur val .

std::bitset<5> num(std::string("00100"));
num.set(0,true);  // num is now 00101
num.set(2,false); // num is now 00001

Définir tous les bits

Manipulation de bits de style C

x = -1; // -1 == 1111 1111 ... 1111b

^{(Voir ici pour expliquer pourquoi cela fonctionne et est en fait la meilleure approche.)}

Utiliser std :: bitset

std::bitset<10> x;
x.set(); // Sets all bits to '1'

Supprimer le bit mis à l'extrême droite

Manipulation de bits de style C

template <typename T>
T rightmostSetBitRemoved(T n)
{
    // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later
    return n & (n - 1);
}

Explication

• si n est zéro, on a 0 & 0xFF..FF qui est zéro
• sinon n peut être écrit 0bxxxxxx10..00 et n - 1 est 0bxxxxxx011..11 , donc n & (n - 1) est 0bxxxxxx000..00 .

Jeu de bits de comptage

Le décompte de population d'une chaîne de bits est souvent nécessaire en cryptographie et dans d'autres applications et le problème a été largement étudié.

La manière naïve nécessite une itération par bit:

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1)
  bits += value & 1;

Une bonne astuce (basée sur l' option Retirer le bit le plus à droite ) est la suivante:

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits)
  value &= value - 1;

Il traverse autant d'itérations qu'il y a de bits définis, donc c'est bien quand on s'attend à ce que la value ait peu de bits non nuls.

La méthode a été proposée pour la première fois par Peter Wegner (dans CACM 3/322 - 1960) et elle est bien connue depuis son apparition dans C Programming Language par Brian W. Kernighan et Dennis M. Ritchie.

Cela nécessite 12 opérations arithmétiques, dont une multication:

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Ce type d'implémentation a le meilleur comportement dans le pire des cas (voir Poids de Hamming pour plus de détails).

De nombreux processeurs ont une instruction spécifique (comme le popcnt de x86) et le compilateur peut offrir une fonction intégrée spécifique ( non standard ). Par exemple, avec g ++, il y a:

int __builtin_popcount (unsigned x);

Vérifiez si un entier est une puissance de 2

L'astuce n & (n - 1) (voir Remove bit le plus à droite ) est également utile pour déterminer si un entier est une puissance de 2:

bool power_of_2 = n && !(n & (n - 1));

Notez que sans la première partie de la vérification ( n && ), 0 est considéré à tort comme une puissance de 2.

Application de manipulation de bits: Lettre minuscule à majuscule

L'une des nombreuses applications de la manipulation de bits consiste à convertir une lettre du petit au capital ou vice versa en choisissant un masque et une opération de bit appropriée. Par exemple, la lettre a cette représentation binaire 01(1)00001 tandis que son homologue du capital a 01(0)00001 . Ils diffèrent uniquement par le bit entre parenthèses. Dans ce cas, convertir une lettre de petite en majuscule met fondamentalement le bit entre parenthèses à un. Pour ce faire, nous faisons ce qui suit:

/****************************************
convert small letter to captial letter.
========================================
     a: 01100001
  mask: 11011111  <-- (0xDF)  11(0)11111
      :---------
a&mask: 01000001  <-- A letter
*****************************************/

Le code pour convertir une lettre en lettre A est

#include <cstdio>

int main()
{
    char op1 = 'a';  // "a" letter (i.e. small case)
    int mask = 0xDF; // choosing a proper mask

    printf("a (AND) mask = A\n");
    printf("%c   &   0xDF = %c\n", op1, op1 & mask);
    
    return 0;
}

Le résultat est

$ g++ main.cpp -o test1
$ ./test1
a (AND) mask = A
a   &   0xDF = A