C++
Manipulación de bits

Observaciones

#include <bitset>

Poniendo un poco

Manipulación de bits estilo C

Se puede configurar un bit utilizando el operador OR bit a bit ( | ).

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

Usando std :: bitset

set(x) o set(x,true) : establece el bit en la posición x en 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

Despejando un poco

Manipulación de bits estilo C

Se puede borrar un bit usando el operador AND a bit ( & ).

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

Usando std :: bitset

reset(x) o set(x,false) : borra el bit en la posición 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

Toggling un poco

Manipulación de bits estilo C

Se puede alternar un bit usando el operador XOR ( ^ ).

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

Usando 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)

Revisando un poco

Manipulación de bits estilo C

El valor del bit se puede obtener desplazando el número a la derecha x veces y luego ejecutando el bit AND ( & ) en él:

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

La operación de desplazamiento a la derecha puede implementarse como un cambio aritmético (con signo) o como un cambio lógico (sin signo). Si el number en la expresión number >> x tiene un tipo con signo y un valor negativo, el valor resultante está definido por la implementación.

Si necesitamos el valor de ese bit directamente en el lugar, podríamos cambiar la máscara a la izquierda:

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

Cualquiera de los dos puede usarse como condicional, ya que todos los valores distintos de cero se consideran verdaderos.

Usando std :: bitset

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

Cambiando el nth bit a x

Manipulación de bits estilo C

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

Usando std :: bitset

set(n,val) - establece el bit n al valor val .

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

Establecer todos los bits

Manipulación de bits estilo C

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

^{(Vea aquí una explicación de por qué esto funciona y en realidad es el mejor enfoque).}

Usando std :: bitset

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

Eliminar el bit de ajuste más a la derecha

Manipulación de bits estilo 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);
}

Explicación

• si n es cero, tenemos 0 & 0xFF..FF que es cero
• de lo contrario n puede escribirse 0bxxxxxx10..00 y n - 1 es 0bxxxxxx011..11 , por lo que n & (n - 1) es 0bxxxxxx000..00 .

Set de bits de conteo

El recuento poblacional de una cadena de bits a menudo se necesita en criptografía y otras aplicaciones y el problema ha sido ampliamente estudiado.

La forma ingenua requiere una iteración por 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;

Un buen truco (basado en Eliminar el bit del conjunto más a la derecha ) es:

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

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

Pasa por tantas iteraciones como bits establecidos, por lo que es bueno cuando se espera que el value tenga pocos bits distintos de cero.

El método fue propuesto por primera vez por Peter Wegner (en CACM 3/322 - 1960) y es bien conocido ya que aparece en lenguaje de programación C por Brian W. Kernighan y Dennis M. Ritchie.

Esto requiere 12 operaciones aritméticas, una de las cuales es una combinación múltiple:

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) + ... 
}

Este tipo de implementación tiene el mejor comportamiento en el peor de los casos (ver el peso de Hamming para más detalles).

Muchas CPU tienen una instrucción específica (como el popcnt de x86) y el compilador podría ofrecer una función integrada específica ( no estándar ). Por ejemplo, con g ++ hay:

int __builtin_popcount (unsigned x);

Compruebe si un entero es una potencia de 2

El n & (n - 1) truco (ver Eliminar el bit del conjunto más a la derecha ) también es útil para determinar si un entero es una potencia de 2:

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

Tenga en cuenta que sin la primera parte de la comprobación ( n && ), 0 se considera incorrectamente una potencia de 2.

Aplicación de manipulación de bits: letra pequeña a mayúscula

Una de las varias aplicaciones de la manipulación de bits es convertir una letra de pequeña a mayúscula o viceversa al elegir una máscara y una operación de bit adecuada. Por ejemplo, la carta tiene esta representación binaria 01(1)00001 mientras que su contraparte capital tiene 01(0)00001 . Difieren únicamente en el bit entre paréntesis. En este caso, convertir una letra de pequeña a mayúscula es básicamente establecer el bit entre paréntesis en uno. Para ello, hacemos lo siguiente:

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

El código para convertir una letra a una letra es

#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;
}

El resultado es

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