Bitwise Hacks para la programación competitiva

Prerequisite: It is recommended to refer Interesting facts about Bitwise Operators 

Cómo poner un bit en el número ‘num’:

Si queremos establecer un bit en la posición n en el número ‘num’, se puede hacer usando el operador ‘OR’ ( | ).  

• Primero, dejamos el cambio ‘1’ a la posición n a través de (1<<n)
• Luego, use el operador ‘OR’ para establecer el bit en esa posición. Se utiliza el operador ‘OR’ porque establecerá el bit incluso si el bit no se ha establecido previamente en la representación binaria del número ‘num’.

Nota: Si el bit ya estuviera configurado, permanecería sin cambios.

#include<iostream>
using namespace std;
// num is the number and pos is the position
// at which we want to set the bit.
void set(int & num,int pos)
{
     // First step is shift '1', second
     // step is bitwise OR
     num |= (1 << pos);
}
int main()
{
     int num = 4, pos = 1;
     set(num, pos);
     cout << (int)(num) << endl;
     return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main (String[] args) {
        int num = 4, pos =1;
          num = set(num, pos);
          System.out.println(num);
    }
      public static int set(int num, int pos){
          // First step is shift '1', second
         // step is bitwise OR
          num |= (1 << pos);
          return num;
    }
}
 
// This code is contributed by geeky01adash.

# num = number, pos = position at which we want to set the bit
def set (num, pos):
  # First step = Shift '1'
  # Second step = Bitwise OR
  num |= (1 << pos)
  print(num)
   
num, pos = 4, 1
 
set(num, pos)
 
# This code is contributed by sarajadhav12052009

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 4, pos = 1;
      set(num, pos);
    }
   
    // num = number, pos = position at which we want to set the bit
    static public void set(int num, int pos)
    {
      // First Step: Shift '1'
      // Second Step: Bitwise OR
      num |= (1 << pos);
      Console.WriteLine(num);
    }
}
 
// This code is contributed by sarajadhav12052009

<script>
// num is the number and pos is the position
// at which we want to set the bit.
function set(num,pos)
{
     // First step is shift '1', second
     // step is bitwise OR
     num |= (1 << pos);
     console.log(parseInt(num));
}
 
let num = 4;
let pos = 1;
set(num, pos);
 
// This code is contributed by akashish__
 
</script>

6

Hemos pasado el parámetro por ‘llamada por referencia’ para hacer cambios permanentes en el número.

2. Cómo desactivar/borrar un bit en la posición n en el número ‘num’: 

Supongamos que queremos desactivar un bit en la posición n en el número ‘num’, entonces tenemos que hacer esto con la ayuda del operador ‘AND’ (&).

• Primero, dejamos el cambio ‘1’ a la posición n a través de (1<<n) y luego usamos el operador NOT bit a bit ‘~’ para desarmar este ‘1’ desplazado.
• Ahora, después de borrar este ‘1’ desplazado a la izquierda, es decir, convertirlo en ‘0’, haremos ‘Y’ (&) con el número ‘num’ que desactivará el bit en la posición n.

#include <iostream>
using namespace std;
// First step is to get a number that  has all 1's except the given position.
void unset(int &num,int pos)
{
    //Second step is to bitwise and this  number with given number
    num &= (~(1 << pos));
}
int main()
{
    int num = 7;
    int  pos = 1;
    unset(num, pos);
    cout << num << endl;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 7, pos = 1;
        num = unset(num, pos);
        System.out.println(num);
    }
    public static int unset(int num, int pos)
    {
        // Second step is to bitwise and this  number with
        // given number
        num = num & (~(1 << pos));
        return num;
    }
}

# First Step: Getting which have all '1's except the
# given position
 
 
def unset(num, pos):
    # Second Step: Bitwise AND this number with the given number
    num &= (~(1 << pos))
    print(num)
 
 
num, pos = 7, 1
 
unset(num, pos)

using System;
 
public class GFG {
 
    static public void Main()
    {
        // First Step: Getting a number which have all '1's
        // except the given position
        int num = 7, pos = 1;
        unset(num, pos);
    }
    static public void unset(int num, int pos)
    {
        // Second Step: Bitwise AND this number with the
        // given number
        num &= (~(1 << pos));
        Console.WriteLine(num);
    }
}

5

3. Cambiando un poco en la n-ésima posición:

Alternar significa activar el bit ‘on’ (1) si estaba ‘off’ (0) y ‘off’ (0) si estaba ‘on’ (1) anteriormente. Usaremos el operador ‘XOR’ aquí, que es este ‘^’. La razón detrás del operador ‘XOR’ es por sus propiedades. 

• Propiedades del operador ‘XOR’. 
  • 1^1 = 0
  • 0^0 = 0
  • 1^0 = 1
  • 0^1 = 1
• Si dos bits son diferentes, el operador ‘XOR’ devuelve un bit establecido (1), de lo contrario, devuelve un bit no establecido (0).

#include <iostream>
using namespace std;
// First step is to shift 1,Second step is to XOR with given
// number
void toggle(int& num, int pos) { num ^= (1 << pos); }
int main()
{
    int num = 4;
    int pos = 1;
    toggle(num, pos);
    cout << num << endl;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main (String[] args) {
        int num = 4, pos =1;
          num = toggle(num, pos);
          System.out.println(num);
    }
      public static int toggle(int num, int pos){
          // First step is to shift 1,Second step is to XOR with given number
        num ^= (1 << pos);
          return num;
    }
}
 
// This code is contributed by geeky01adash.

def toggle(num, pos):
  # First Step: Shifts '1'
  # Second Step: XOR num
  num ^= (1 << pos)
  print(num)
   
   
num, pos = 4, 1
 
toggle(num, pos)
 
# This code is contributed by sarajadhav12052009

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 4, pos = 1;
      toggle(num, pos);
    }
    static public void toggle(int num, int pos)
    {
      // First Step: Shift '1'
      // Second Step: XOR num
      num ^= (1 << pos);
      Console.WriteLine(num);
    }
}
 
// This code is contributed by sarajadhav12052009

6

4. Comprobar si el bit en la posición n está activado o desactivado: 

Es bastante fácil de hacer usando el operador ‘Y’.

• Cambio a la izquierda ‘1’ a la posición dada y luego ‘Y’ (‘&’).

#include <iostream>
using namespace std;
 
bool at_position(int num, int pos)
{
    bool bit = num & (1 << pos);
    return bit;
}
 
int main()
{
    int num = 5;
    int pos = 0;
    bool bit = at_position(num, pos);
    cout << bit << endl;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 5;
        int pos = 0;
        int bit = at_position(num, pos);
        System.out.println(bit);
    }
    public static int at_position(int num, int pos)
    {
        int bit = num & (1 << pos);
        return bit;
    }
}

# code
def at_position(num,pos):
    bit = num & (1<<pos)
    return bit
   
num = 5
pos = 0
bit = at_position(num, pos)
print(bit)

<script>
function at_position(num,pos)
{
 return num & (1<<pos);
}
let num = 5;
let pos = 0;
console.log(at_position(num, pos));
// contributed by akashish__
</script>

1

Observe que primero hemos desplazado a la izquierda ‘1’ y luego usamos el operador ‘Y’ para obtener un bit en esa posición. Entonces, si hay ‘1’ en la posición ‘pos’ en ‘num’, luego de ‘AND’, nuestra variable ‘bit’ almacenará ‘1’; de lo contrario, si hay ‘0’ en la posición ‘pos’ en el número ‘num’ que después de ‘Y’ nuestro bit variable almacenará ‘0’.

Algunos trucos más rápidos: 

• Invertir cada bit del complemento de un número/1:  si queremos invertir cada bit de un número, es decir, cambiar el bit ‘0’ a ‘1’ y el bit ‘1’ a ‘0’. Podemos hacer esto con la ayuda de ‘~ ‘ operador. Por ejemplo: si el número es num=00101100 (representación binaria), entonces ‘~num’ será ‘11010011’.

Este es también el ‘complemento a 1 del número’.

#include <iostream>
using namespace std;
int main()
{
    int num = 4;
 
    // Inverting every bit of number num
    cout << (~num);
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main (String[] args) {
        int num = 4;
       
          // Inverting every bit of number num
          num = (~num);
          System.out.println(num);
    }
}

num = 4
 
# Inverting every bit of number num
print(~num)

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 4;
       
      // Inverting every bit of number num
      Console.WriteLine(~num);
    }
}

<script>
let num = 4;
 
    // Inverting every bit of number num
    console.log(~num);
     
    
</script>

-5

• Complemento a dos del número:  El complemento a 2 de un número es el complemento a 1 + 1.

Entonces, formalmente, podemos tener el complemento a 2 al encontrar el complemento a 1 y agregar 1 al resultado, es decir, (~ num + 1) o qué más podemos hacer es usar el operador ‘-‘.

#include <iostream>
using namespace std;
int main()
{
    int num = 4;
    int twos_complement = -num;
    cout << "This is two's complement " << twos_complement << endl;
    cout << "This is also two's complement " << (~num+1) << endl;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 4;
        int twos_complement = -num;
        System.out.println("This is two's complement "
             + twos_complement);
        System.out.println("This is also two's complement "
             + (~num + 1));
    }
}
 
// This code is contributed by geeky01adash.

num = 4
twos_complement = -num
 
print(f"This is two's complement {twos_complement}")
print(f"This is also two's complement {~num + 1}")
 
# This code is contributed by sarajadhav12052009

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 4;
      int twos_complement = -num;
       
      Console.WriteLine("This is two's complement " + twos_complement);
      Console.WriteLine("This is also two's complement " + (~num+1));
    }
}
 
// This code is contributed by sarajadhav12052009

<script>
let num = 4;
let twos_complement = -num;
console.log("This is two's complement " + twos_complement);
console.log("This is also two's complement " + (~num+1));
 
// This code is contributed by akashish__
</script>

This is two's complement -4
This is also two's complement -4

 Eliminando el bit establecido más bajo:

En muchas situaciones, queremos eliminar el bit establecido más bajo, por ejemplo, en la estructura de datos de árbol indexado binario, contando el número de bits establecidos en un número. Hacemos algo como esto:  

X = X & (X-1)

Pero, ¿cómo funciona? Veamos esto tomando un ejemplo, sea X = 1100.

• (X-1) invierte todos los bits hasta que encuentra el conjunto más bajo ‘1’ y también invierte ese conjunto más bajo ‘1’.
• X-1 se convierte en 1011. Después de ‘Ying’ X con X-1, obtenemos el bit de conjunto más bajo eliminado. 

#include <iostream>
using namespace std;
void strip_last_set_bit(int &num)
{
    num = num & (num-1);
}
int main()
{
    int num = 7;
    strip_last_set_bit(num);
    cout << num << endl;
    return 0;
}

import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 7;
        num = strip_last_set_bit(num);
        System.out.println(num);
    }
    public static int strip_last_set_bit(int num)
    {
        return num & (num - 1);
    }
}

def strip_last_set_bit(num):
    num &= (num - 1)
    print(num)
 
 
num = 7
 
strip_last_set_bit(num)

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 7;
      strip_last_set_bit(num);
    }
    static public void strip_last_set_bit(int num)
    {
      num &= (num - 1);
      Console.WriteLine(num);
    }
}

<script>
function strip_last_set_bit(num)
{
    return num & (num-1);
}
 
let num = 7;
 
console.log(strip_last_set_bit(num));
</script>

6

Obtener el conjunto de bits más bajo de un número:

Esto se hace usando la expresión ‘X &(-X)’ Veamos esto tomando un ejemplo: Sea X = 00101100. Entonces ~X(complemento a 1) será ‘11010011’ y el complemento a 2 será (~X+ 1 o -X), es decir, ‘11010100’. Entonces, si hacemos ‘Y’ el número original ‘X’ con su complemento a dos, que es ‘-X’, obtenemos el bit establecido más bajo. 

  00101100
& 11010100
-----------
  00000100

#include <iostream>
using namespace std;
int lowest_set_bit(int num)
{
    int ret = num & (-num);
    return ret;
}
int main()
{
    int num = 10;
    int ans = lowest_set_bit(num);
    cout << ans << endl;
    return 0;
}

import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 10;
        int ans = lowest_set_bit(num);
        System.out.println(ans);
    }
    public static int lowest_set_bit(int num)
    {
        int ret = num & (-num);
        return ret;
    }
}

def lowest_set_bit(num):
    num &= (-num)
    print(num)
 
 
num = 10
 
lowest_set_bit(num)

using System;
 
public class GFG {
 
    static public void Main()
    {
        int num = 10;
        lowest_set_bit(num);
    }
    static public void lowest_set_bit(int num)
    {
        num &= (~num + 1);
        Console.WriteLine(num);
    }
}

2

La división por 2 y la multiplicación por 2 también son muy frecuentes en los bucles de la programación competitiva, por lo que el uso de operadores bit a bit puede ayudar a acelerar el código.

Divida por 2 usando el operador de desplazamiento a la derecha:

00001100 >> 1 (00001100 is 12)
------------
00000110 (00000110 is 6)

#include <iostream>
using namespace std;
int main()
{
    int num = 12;
    int ans = num>>1;
    cout << ans << endl;
    return 0;
}

import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int num = 12;
        int ans = num >> 1;
        System.out.println(ans);
    }
}

num = 12
print(num >> 1)

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 12;
      Console.WriteLine(num >> 1);
    }
}

<script>
var num = 12;
var ans = num>>1;
console.log(ans);
</script>

6

Multiplique por 2 usando el operador de desplazamiento a la izquierda:

00001100 << 1 (00001100 is 12)
------------
00011000 (00000110 is 24)

#include <iostream>
using namespace std;
int main()
{
    int num = 12;
    int ans = num<<1;
    cout << ans << endl;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static void main (String[] args) {
          int num = 12;
        int ans = num<<1;
        System.out.println(ans);
    }
}
 
// This code is contributed by geeky01adash.

using System;
 
public class GFG{
 
    static public void Main ()
    {
      int num = 12;
      Console.WriteLine(num << 1);
    }
}
 
// This code is contributed by sarajadhav12052009

# Python program for the above approach
 
num = 12
ans = num<<1
print(ans)
 
# This code is contributed by Shubham Singh

<script>
// Javascript program for the above approach
 
var num = 12;
var ans = num<<1;
document.write(ans);
 
//This code is contributed by Shubham Singh
</script>

24

Bit Tricks para la programación competitiva
Consulte los artículos de operadores de BitWise para obtener más artículos sobre Bit Hacks.

Este artículo es una contribución de Pankaj Mishra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.