Introducción a los operadores bit a bit

Recursos
Fuente	Recurso	Notas
CPH	10.2 - Bit Operations
CF	Bitwise operations for beginners	Excelente explicación de Errichto
GFG	Bitwise Operators in C/C++	Los mismos operadores se usan en Java y Python

A esta altura ya deberíamos estar familiarizados con los tres operadores bit a bit principales (AND, OR y XOR). Veamos algunos ejemplos para entenderlos mejor.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	Take a Guess	Normal	Bitwise	en el módulo

Solución - Take a Guess

De hecho, podemos obtener la suma de dos números usando solo sus valores de AND, OR y XOR. Si conocemos sus valores de XOR, podemos usar la siguiente propiedad:

a + b = 2 \cdot (a \& b) + a \oplus b

La demostración es la siguiente:

$a \oplus b$ es esencialmente $a + b$ en base $2$ pero nunca llevamos al siguiente bit. Recordemos que un bit en $a \oplus b$ es $1$ solo si el bit en $a$ es distinto del bit en $b$ , así que uno de ellos debe ser un $1$ . Sin embargo, al sumar dos bits $1$ obtenemos un $0$ , pero no llevamos ese $1$ al siguiente bit. Ahí es donde entra $a \& b$ .

$a \& b$ son justamente los bits de acarreo, ya que un bit es $1$ solo si es $1$ tanto en $a$ como en $b$ , que es exactamente lo que necesitamos. Multiplicamos esto por $2$ para desplazar todos los bits una posición a la izquierda, de modo que cada valor se lleva al siguiente bit.

Para obtener los valores de XOR de los dos números, podemos usar lo siguiente:

a \oplus b = \lnot(a \& b) \& (a | b)

La demostración es la siguiente:

Recordemos que un bit en $a \oplus b$ es $1$ solo si el bit en $a$ es distinto del bit en $b$ . Al negar $a \& b$ , los bits que quedan encendidos tienen el siguiente formato:

Si es $1$ en $a$ y $0$ en $b$
Si es $0$ en $a$ y $1$ en $b$
Si es $0$ en $a$ y $0$ en $b$

Esto se ve bastante bien, pero hay que eliminar el tercer caso. Al tomar el AND bit a bit con $a | b$ , los que quedan encendidos son solo aquellos en los que hay un $1$ en $a$ o en $b$ . Obviamente, el tercer caso no está incluido en $a | b$ porque ambos bits están apagados, y así eliminamos ese caso.

Ahora que podemos obtener la suma de cualquier par de números en dos consultas, podemos resolver el problema con facilidad. Hallamos los valores de los tres primeros números del arreglo usando un sistema de ecuaciones con sus sumas (notemos que $n \geq 3$ ). Una vez que tenemos sus valores independientes, recorremos el resto del arreglo.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int ask(string s, int a, int b) {
	cout << s << ' ' << a << ' ' << b << endl;
	int res;
	cin >> res;
	return res;
}
 
/** @return the sum of the elements at a and b (0-indexed) */
int sum(int a, int b) {
	int and_ = ask("and", ++a, ++b);
	int or_ = ask("or", a, b);
 
	int xor_ = ~and_ & or_;  // a ^ b = ~(a & b) & (a | b)
 
	return 2 * and_ + xor_;  // a + b = 2(a & b) + a ^ b
}
 
int main() {
	int n, k;
	cin >> n >> k;
 
	// Acquire the first 3 elements
	int a_plus_b = sum(0, 1);
	int a_plus_c = sum(0, 2);
	int b_plus_c = sum(1, 2);
 
	// Get the actual values by solving the equations
	vector<int> arr{(a_plus_b + a_plus_c - b_plus_c) / 2};
	arr.push_back(a_plus_b - arr[0]);
	arr.push_back(a_plus_c - arr[0]);
 
	// Get the rest of the array
	for (int i = 3; i < n; i++) { arr.push_back(sum(i - 1, i) - arr.back()); }
 
	sort(arr.begin(), arr.end());
	cout << "finish " << arr[k - 1] << endl;
}


import java.io.*;
import java.util.*;
 
public class TakeAGuess {
	private static BufferedReader br =
	    new BufferedReader(new InputStreamReader(System.in));
 
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		// Acquire the first 3 elements
		int aPlusB = sum(0, 1);
		int aPlusC = sum(0, 2);
		int bPlusC = sum(1, 2);
 
		// Get the actual values by solving the equations
		List<Integer> arr = new ArrayList<>();
		arr.add((aPlusB + aPlusC - bPlusC) / 2);
		arr.add(aPlusB - arr.get(0));
		arr.add(aPlusC - arr.get(0));
 
		// Get the rest of the array
		for (int i = 3; i < n; i++) {
			arr.add(sum(i - 1, i) - arr.get(arr.size() - 1));
		}
 
		arr.sort(Comparator.comparingInt(i -> i));
		System.out.printf("finish %d%n", arr.get(k - 1));
	}
 
	/** @return the sum of the elements at a and b (0-indexed) */
	private static int sum(int a, int b) throws IOException {
		int and = ask("and", ++a, ++b);
		int or = ask("or", a, b);
 
		int xor = ~and & or;  // a ^ b = ~(a & b) & (a | b)
 
		return 2 * and + xor;  // a + b = 2(a & b) + a ^ b
	}
 
	private static int ask(String s, int a, int b) throws IOException {
		System.out.printf("%s %d %d%n", s, a, b);
		System.out.flush();
		return Integer.parseInt(br.readLine());
	}
}


def ask(s: str, a: int, b: int) -> int:
	print(f"{s} {a} {b}", flush=True)
	return int(input())
 
 
def sum(a: int, b: int) -> int:
	""":return: the sum of the elements at a and b (0-indexed)"""
	a += 1
	b += 1
	and_ = ask("and", a, b)
	or_ = ask("or", a, b)
 
	xor = ~and_ & or_  # a ^ b = ~(a & b) & (a | b)
 
	return 2 * and_ + xor  # a + b = 2(a & b) + a ^ b
 
 
n, k = [int(i) for i in input().split()]
 
# Acquire the first 3 elements
a_plus_b = sum(0, 1)
a_plus_c = sum(0, 2)
b_plus_c = sum(1, 2)
 
# Get the actual values by solving the equations
arr = [(a_plus_b + a_plus_c - b_plus_c) // 2]
arr.append(a_plus_b - arr[0])
arr.append(a_plus_c - arr[0])
 
# Get the rest of the array
for i in range(3, n):
	arr.append(sum(i - 1, i) - arr[-1])
 
arr.sort()
print(f"finish {arr[k - 1]}")

Ejemplo - Addition

Ahora veamos cómo implementar la suma y la multiplicación usando solo operadores bit a bit. Antes de hacerlo, ¡intentemos implementar la suma usando operadores bit a bit por nuestra cuenta! Podemos probar la implementación aquí .

Solución - Addition

Si sumamos sin llevar, estamos simplemente aplicando el operador XOR (^). Luego, los bits que llevamos son aquellos equivalentes a $1$ en ambos números: $a\&b$ .

C++JavaPython


int add(int a, int b) {
	while (b > 0) {
		int carry = a & b;
		a ^= b;
		b = carry << 1;
	}
	return a;
}


public static int add(int a, int b) {
	while (b > 0) {
		int carry = a & b;
		a ^= b;
		b = carry << 1;
	}
	return a;
}


def add(a: int, b: int) -> int:
	while b > 0:
		carry = a & b
		a ^= b
		b = carry << 1
	return a

Ejemplo - Multiplication

¡Ahora intentemos implementar la multiplicación usando operadores bit a bit! Si queremos probar nuestra implementación de la multiplicación, podemos hacerlo aquí .

Solución - Multiplication

Para simplificar, usaremos las funciones sum definidas arriba. Si descomponemos $b$ en $2^{b_1}+2^{b_2}+\dots+2^{b_n}$ , obtenemos lo siguiente:

\begin{align*} &a \times b \\ &= a \times (2^{b_1}+2^{b_2}+\dots+2^{b_n}) \\ &= a2^{b_1}+a2^{b_2}+\dots+a2^{b_n} \\ &= \sum_{\text{bits in b}} {a\texttt{<<}b_i} \end{align*}

(¡Esta misma idea se usa en la exponenciación binaria!)

C++JavaPython


int prod(int a, int b) {
	int c = 0;
	while (b > 0) {
		if ((b & 1) == 1) {
			c = add(c, a);  // Use the addition function we coded previously
		}
		a <<= 1;
		b >>= 1;
	}
	return c;
}


public static int prod(int a, int b) {
	int c = 0;
	while (b > 0) {
		if ((b & 1) == 1) {
			c = add(c, a);  // Use the addition function we coded previously
		}
		a <<= 1;
		b >>= 1;
	}
	return c;
}


def prod(a: int, b: int) -> int:
	c = 0
	while b > 0:
		if b & 1:
			c = add(c, a)  # Use the addition function we coded previously
		a <<= 1
		b >>= 1
	return c

Operación XOR

Quizá una de las operaciones binarias más comunes en la práctica es el XOR bit a bit . La propiedad especial que lo diferencia de las demás operaciones bit a bit es que el XOR es su propio inverso, es decir, $x \oplus x = 0$ .

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Xor Sigma Problem	Normal	Bitwise, Prefix Sums	en el módulo

Explicación

Analicemos los bits de cada xor-suma de forma independiente. En este caso, comprobaremos para cada posición de bit, es decir, para cada potencia de dos, si está activada o no en la xor-suma de cada subsecuencia contigua. De este modo, transformamos el problema en contar la cantidad de subsecuencias con xor-suma distinta de cero; esto se aplicará sobre el arreglo formado por los bits en la misma posición de todos los valores.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <iostream>
#include <numeric>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for (int &a : v) { cin >> a; }
 
	long long ans = -accumulate(v.begin(), v.end(), 0LL);
 
	// For every bit position,
	// check if it's set on in the xor-sum of every subsequence
	for (int i = 0; i < 30; i++) {
		int s = 0;
		// Count the prefix sums
		// The # of 0 xor-sum prefxises starts from 1 to count the prefixes with
		// xor-sum 1
		vector<int> pref = {1, 0};
		for (int a : v) {
			s ^= (a >> i) & 1;
			/*
			 * Count the # of sequences ending at this position with xor-sum
			 * non-zero by counting the prefixes of the inversed bit, i.e.
			 * pref[i] ^ pref[j] = 1. Update the answer by adding the # of such
			 * sequences multiplied by the respective power of two.
			 */
			ans += pref[s ^ 1] * 1LL << i;
			// Update the prexies
			pref[s]++;
		}
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(read.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int[] v = new int[n];
 
		st = new StringTokenizer(read.readLine());
 
		long ans = 0;
		for (int i = 0; i < n; i++) {
			v[i] = Integer.parseInt(st.nextToken());
			ans -= v[i];
		}
 
		// For every bit position,
		// check if it's set on in the xor-sum of every subsequence
		for (int i = 0; i < 30; i++) {
			int s = 0;
			// Count the prefix sums
			//  The # of 0 xor-sum prefixes start from 1 to count the prefixes with
			//  xor-sum 1
			int[] pref = {1, 0};
			for (int a : v) {
				s ^= (a >> i) & 1;
				/*
				 * Count the # of sequences ending at this position with xor-sum
				 * non-zero by counting the prefixes of the inversed bit, i.e.
				 * pref[i] ^ pref[j] = 1. Update the answer by adding the # of such
				 * sequences multiplied by the respective power of two.
				 */
				ans += (long)pref[s ^ 1] << i;
				// Update the prefixes
				pref[s]++;
			}
		}
 
		System.out.println(ans);
	}
}


n = int(input())
v = list(map(int, input().split()))
 
res = 0
"""
For every bit position
check if it's set on in the xor-sum of every subsequence
"""
for i in range(30):
	s = 0
	"""
	Count the prefix sums
	The # of 0 xor-sum prefxises starts from 1 to count the prefixes with
	xor-sum 1
	"""
	pref = [1, 0]
	for a in v:
		s ^= (a >> i) & 1
		"""
		Count the # of sequences ending at this position with xor-sum
		non-zero by counting the prefixes of the inversed bit, i.e.
		pref[i] ^ pref[j] = 1. Update the answer by adding the # of such
		sequences multiplied by the respective power of two.
		"""
		res += pref[s ^ 1] * (1 << i)
		# update the prexies
		pref[s] += 1
 
print(res - sum(v))

Fuente	Nombre	Dificultad	Tags	Solución
CF	Powered Addition	Fácil	Bitwise, Greedy	Solución
CF	Data Structures Fan	Fácil	Bitwise	Solución
CF	The Wu	Fácil	Bitwise, Complete Search, Binary Search	Solución
AC	★ Three Days Ago	Fácil	Bitwise	Solución
CF	Lisa and the Martians	Fácil	Bitwise, Sorting, Trie	Solución
Silver	Searching For Soulmates	Fácil	Bitwise, Complete Search	Solución
Silver	Field Day	Normal	Bitwise, Graphs	Solución
CF	Sheikh (Easy version)	Normal	Bitwise, Prefix Sums, Binary Search	Solución
CF	Sum of XOR Functions	Normal	Bitwise, Prefix Sums	Solución
CSES	★ Prime Multiples	Normal	Bitwise, PIE	Solución
CF	AND, OR, and square sum	Normal	Math, Greedy	Solución
Silver	Sequence Construction	Normal	Bitwise	—
Silver	Sliding Window Summation	Normal	Bitwise, Prefix Sums	Solución
CF	Ehab and another another xor problem	Difícil	Math, Interactive	Solución

Quiz

Pregunta 1/3

¿Cuál de las siguientes pone a verdadero el k-ésimo bit de int x? Supongamos que no sabemos cuál es el valor actual del k-ésimo bit.