Trucos de bits para la programación competitiva

En programación competitiva o en general, algunos problemas parecen difíciles pero se pueden resolver muy fácilmente con pequeños conceptos de magia de bits. Hemos discutido algunos trucos a continuación en la publicación anterior.
Bitwise Hacks para la programación competitiva
Hemos considerado los siguientes hechos en este artículo: 
 

• 0 basado en la indexación de bits de derecha a izquierda.
• Establecer el bit i-ésimo significa cambiar el bit i-ésimo a 1
• Limpiar el bit i-ésimo significa cambiar el bit i-ésimo a 0

1) Borrar todos los bits desde LSB hasta i-ésimo bit 
 

mask = ~((1 << i+1 ) - 1);
x &= mask;

Lógica: Para borrar todos los bits del LSB al i-ésimo bit, tenemos que Y x con máscara que tiene LSB al i-ésimo bit 0. Para obtener dicha máscara, primero se desplaza a la izquierda 1 i veces. Ahora, si restamos 1 de eso, todos los bits de 0 a i-1 se convierten en 1 y los bits restantes se convierten en 0. Ahora podemos simplemente tomar el complemento de la máscara para obtener todos los primeros bits i en 0 y los restantes en 1. 
Ejemplo: 
x = 29 (00011101) y queremos borrar LSB al 3er bit, 
máscara total de 4 bits -> 1 << 4 -> 16 (00010000) 
máscara -> 16 – 1 -> 15 (00001111) 
máscara -> ~ máscara -> 11110000 
x & mask -> 16 (00010000)
2) Borrado de todos los bits desde MSB hasta i-ésimo bit 
 

mask = (1 << i) - 1;
x &= mask;

Lógica: Para borrar todos los bits desde el MSB hasta el i-ésimo bit, tenemos que hacer AND x con una máscara que tenga el MSB hasta el i-ésimo bit 0. Para obtener dicha máscara, primero desplácese a la izquierda 1i veces. Ahora, si restamos 1 de eso, todos los bits de 0 a i-1 se convierten en 1 y los bits restantes se convierten en 0.  Ejemplo: x = 215 (
11010111 
) y queremos borrar MSB al 4.º bit, 
máscara total de 4 bits -> 1 << 4 -> 16(00010000) 
máscara -> 16 – 1 -> 15(00001111) 
x & máscara -> 7(00000111)
3) Dividir por 2 
 

x >>= 1;

Lógica: cuando hacemos un desplazamiento aritmético a la derecha, cada bit se desplaza a la derecha y la posición en blanco se sustituye por un bit de signo de número, 0 en caso de número positivo y 1 en caso de número negativo. Dado que cada bit es una potencia de 2, con cada cambio estamos reduciendo el valor de cada bit por un factor de 2, lo que equivale a la división de x por 2.  Ejemplo : x = 18 (00010010) 
x  >> 1 = 9 (00001001 ) 4) Multiplicando por 2

 
 

x <<= 1;

Lógica: cuando hacemos un desplazamiento aritmético a la izquierda, cada bit se desplaza a la izquierda y la posición en blanco se sustituye por 0. Dado que cada bit es una potencia de 2, con cada desplazamiento aumentamos el valor de cada bit por un factor de 2, lo que equivale a la multiplicación de x por 2.  Ejemplo : x = 18(00010010) 
x  << 1 = 36 ( 00100100) 5) Alfabeto inglés en mayúsculas a minúsculas

 
 

ch |= ' ';

Lógica: la representación de bits de los alfabetos ingleses en mayúsculas y minúsculas es: 
 

A -> 01000001          a -> 01100001
B -> 01000010          b -> 01100010
C -> 01000011          c -> 01100011
  .                               .
  .                               .
Z -> 01011010          z -> 01111010

Como podemos ver, si configuramos el quinto bit de caracteres en mayúsculas, se convertirá en caracteres en minúsculas. Tenemos que preparar una máscara que tenga un 5to bit 1 y otro 0 (00100000). Esta máscara es una representación de bits del carácter de espacio (‘ ‘). Luego, el carácter ‘ch’ se redujo con OR con máscara.
Ejemplo- 
ch = ‘A’ (01000001) 
mask = ‘ ‘ (00100000) 
ch | mask = ‘a’ (01100001) 
Consulte Conversión de mayúsculas y minúsculas (de inferior a superior y viceversa) para obtener más detalles.
6) Alfabeto inglés en minúsculas a mayúsculas 
 

ch &= '_’ ;

Lógica: la representación de bits de los alfabetos ingleses en mayúsculas y minúsculas es: 
 

A -> 01000001                a -> 01100001
B -> 01000010                b -> 01100010
C -> 01000011                c -> 01100011
.                               .
.                               .
Z -> 01011010                z -> 01111010

Como podemos ver, si borramos el quinto bit de caracteres en minúsculas, se convertirá en carácter en mayúsculas. Tenemos que preparar una máscara que tenga un 5º bit 0 y otro 1 (11011111). Esta máscara es una representación de bits del carácter de subrayado (‘_’). El carácter ‘ch’ luego AND con máscara. 
Ejemplo 
: ch = ‘a’ (01100001) 
mask = ‘_ ‘ (11011111) 
ch & mask = ‘A’ (01000001) 
Consulte Conversión de mayúsculas y minúsculas (de menor a mayor y viceversa) para obtener más detalles.
7) Contar bits establecidos en entero 

int countSetBits(int x)
{
    int count = 0;
    while (x)
    {
        x &= (x-1);
        count++;
    }
    return count;
}

Lógica: Este es el algoritmo de Brian Kernighan .

8) Encuentre la base logarítmica 2 de un entero de 32 bits 
 

int log2(int x)
{
    int res = 0;
    while (x >>= 1)
        res++;
    return res;
}

Lógica: desplazamos x a la derecha repetidamente hasta que se convierte en 0, mientras tanto seguimos contando la operación de desplazamiento. Este valor de conteo es log2(x).
9) Comprobando si dado un entero de 32 bits es potencia de 2 
 

int isPowerof2(int x)
{
    return (x && !(x & x-1));
}

Lógica: toda la potencia de 2 tiene un solo bit configurado, por ejemplo, 16 (00010000). Si restamos 1 de esto, todos los bits desde LSB hasta el bit establecido se alternan, es decir, 16-1 = 15 (00001111). Ahora, si hacemos AND x con (x-1) y el resultado es 0, entonces podemos decir que x es potencia de 2; de lo contrario, no. Tenemos que tener mucho cuidado cuando x = 0.
Ejemplo 
x = 16(00010000) 
x – 1 = 15(00001111) 
x & (x-1) = 0 
entonces 16 es potencia de 2

10) Encuentra el último bit establecido

int lastSetBit(int n){
    return log2(n & -n)+1;
}

El valor logarítmico de AND de x y -x en base 2 da el índice del último bit establecido (para indexación basada en 0).

Consulte este artículo para obtener más trucos.
Este artículo es una contribución de Atul Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.