Manipulación de bits (tácticas importantes)

Prerrequisitos: operadores bit a bit en C , trucos bit a bit para programación competitiva , trucos bit a bit para programación competitiva
 

1. Calcule XOR de 1 a n (método directo): 
 

// Direct XOR of all numbers from 1 to n
int computeXOR(int n)
{
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}

# Direct XOR of all numbers from 1 to n
def computeXOR(n):
    if (n % 4 is 0):
        return n
    if (n % 4 is 1):
        return 1
    if (n % 4 is 2):
        return n + 1
    else:
        return 0
 
       
# This code is contributed by akashish__

using System;
public class GFG
{
 
  // Direct XOR of all numbers from 1 to n
  public static int computeXOR(int n)
  {
 
    if (n % 4 == 0)
 
      return n;
 
    if (n % 4 == 1)
 
      return 1;
 
    if (n % 4 == 2)
 
      return n + 1;
 
    else
 
      return 0;
 
  }
  public static void Main(){}
 
 
}
 
// This code is contributed by akashish__

<script>
 
// Direct XOR of all numbers from 1 to n
function computeXOR(n)
{
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}
 
// This code is contributed by Shubham Singh
 
</script>

Input: 6
Output: 7

1. Consulte Calcular XOR de 1 a n para obtener más información.
2. Podemos calcular rápidamente el número total de combinaciones con números menores o iguales a un número cuya suma y XOR son iguales. En lugar de usar bucles (método de fuerza bruta), podemos encontrarlo directamente mediante un truco matemático, es decir 
    

// Refer Equal Sum and XOR for details.
Answer = pow(2, count of zero bits)

2. ¿Cómo saber si un número es potencia de 2? 
 

//  Function to check if x is power of 2
bool isPowerOfTwo(int x)
{
     // First x in the below expression is
     // for  the case when x is 0
     return x && (!(x & (x - 1)));
}

Consulte comprobar si un número es potencia de dos para obtener más información.

3. Encuentra XOR de todos los subconjuntos de un conjunto

Podemos hacerlo en tiempo O(1). La respuesta siempre es 0 si el conjunto dado tiene más de un elemento. Para conjuntos con un solo elemento, la respuesta es el valor de un solo elemento. 

Consulte XOR de los XOR de todos los subconjuntos para obtener más detalles.

4. Encuentre el número de ceros iniciales y finales y el número de 1

Podemos encontrar rápidamente el número de ceros iniciales y finales y el número de 1 en un código binario de un número entero en C++ usando GCC. Se puede hacer usando la función incorporada, es decir

  Number of leading zeroes: __builtin_clz(x)
  Number of trailing zeroes : __builtin_ctz(x)
  Number of 1-bits: __builtin_popcount(x) 

Consulte las funciones integradas de GCC para obtener más información.

5. Convierta el código binario directamente en un número entero en C++.  

// Conversion into Binary code//
#include <iostream>
using namespace std;
 
int main()
{
    auto number = 0b011;
    cout << number;
    return 0;
}

Output: 3

6. La forma más rápida de intercambiar dos números:  

a ^= b;
b ^= a; 
a ^= b;

Consulte intercambio de dos números para obtener más detalles.  

7. Enfoque simple para voltear los bits de un número: 

Se puede hacer de una manera sencilla, basta con restar el número del valor obtenido cuando todos los bits son iguales a 1. 
Por ejemplo:  

Number : Given Number
Value  : A number with all bits set in given number.
Flipped number = Value – Number.

Example : 
Number = 23,
Binary form: 10111;
After flipping digits number will be: 01000;
Value: 11111 = 31;

8. Encontrar el bit establecido más significativo

Podemos encontrar el bit establecido más significativo en el tiempo O(1) para un número entero de tamaño fijo. Por ejemplo, el siguiente código es para enteros de 32 bits.  

int setBitNumber(int n)
{     
    // Below steps set bits after
    // MSB (including MSB)
 
    // Suppose n is 273 (binary
    // is 100010001). It does following
    // 100010001 | 010001000 = 110011001
    n |= n>>1;
 
    // This makes sure 4 bits
    // (From MSB and including MSB)
    // are set. It does following
    // 110011001 | 001100110 = 111111111
    n |= n>>2;  
 
    n |= n>>4; 
    n |= n>>8;
    n |= n>>16;
     
    // Increment n by 1 so that
    // there is only one set bit
    // which is just before original
    // MSB. n now becomes 1000000000
    n = n + 1;
 
    // Return original MSB after shifting.
    // n now becomes 100000000
    return (n >> 1);
}

Consulte Encontrar el conjunto de bits más significativo de un número para obtener más información. 

9.Comprueba si un número tiene bits en un patrón alternativo

Podemos comprobar rápidamente si los bits de un número están en un patrón alternativo (como 101010). Calculamos n ^ (n >> 1). Si n tiene un patrón alternativo, entonces la operación n ^ (n >> 1) producirá un número que solo tiene bits establecidos. ‘^’ es una operación XOR bit a bit. 

// function to check if a number has bits in alternate
// pattern
bool bitsAreInAltOrder(unsigned int n)
{
    unsigned int num = n ^ (n >> 1);
    // to check if all bits are set in 'num'
    return allBitsAreSet(num);
}

Consulte comprobar si un número tiene bits en patrón alternativo para obtener más información.

Este artículo es una contribución de Sanchit Garg 1 . 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.