Bitmask 2

Operacion Xor

La operacion xor para un solo bit se puede ver como la suma usual en $Z_2$, así si nosotros tenemos
dos bits a y b al hacer a xor b esto sera igual a (a+b)(mod 2), pero que importancia tiene verlo así? pues de esta forma es más sencillo darnos cuenta que el xor cumple las propiedades de la suma en el cuerpo de $Z_2$, veamos esto.

1. a xob b $\in$ $Z_2$ (Clausura)

2. a xor b = b xor a para todo a y b $\in$ $Z_2$ (Commutatividad)

3. (a xor b) xor c = a xor (b xor c) para todo a , b y c $\in$ $Z_2$ (Asociatividad)

4. existe un único e $\in$ $Z_2$ tal que a xor e = a, para todo a $\in$ $Z_2$ (elemento neutro)

5. para todo a $\in$ $Z_2$, existe b $\in$ $Z_2$, tal que a xor b = e (inverso aditivo)

ya que esto se cumple, por tanto es mucho más sencillo trabajar con xor, primero veamos que e = 0 y el inverso aditivo de a $\in$ $Z_2$ es a. como sirve esto si es que nosotros no trabajamos con elemento con un solo bit unicamente? pues 1a teoría es muy clara, sea el espacio $Z_2^n$ y heredemos la suma y el producto usual de $Z_2$ de la manera natural, sea x = ($x_1, x_2, \dots, x_n$), y = ($y_1, y_2, \dots, y_n$) $\in$ $Z_2^n$, luego, x xor y = ($x_1$ xor $y_1$, $x_2$ xor $y_2$, $\dots$, $x_n$ xor $y_n$) y por tanto la suma definida de esta forma cierra bajo las condiciones de cuerpo.

 ahora usted puede ver que para todo A, B $\in$ $Z_2^n$, A xor A = 0 y A xor 0 = A.

Problema 1: Sea la sucesiön $a_1$, $a_2$, $\dots$, $a_n$ con $-10^{18}  \leq a_i \leq 10^{18} $ de tal forma que hay uno y solo un elemento que se repite un número impar de veces, haga un programa que halle este número.

Problema 2:  Sea L y R ($1 \leq L \leq R \leq 10^{18}$), haga un programa que halle $max_{L \leq a, b \leq R}$(a xor b).

Más utilidades para las mascaras de bits

En ocasiones nosotros queremos asignar a todos los elementos de un array un valor específico, para ello usaremos una función llamada memset de la librería "cstring" que nos permite que en un array de caracteres cambie todos sus elemento a un caracter específico. pero como funciona esto? para responder esto recordemos que un caracter ocupa un byte de información, y así la función se encarga de cambiar todos los bytes de un vector a una mascara de bits específica (esto se debe a que los arrays ocupan memoria continua), ahora si nosotros queremos hacer un vector de enteros a 0, entonces como sabemos que 0 en los enteros tiene 4 bytes y cada de esos bytes es un 0 (puede ver esto?) podemos hacer memset(array, 0, sizeof array), aun más si nosotros recordamos que -1 en su representación binaria es puros 1s, quiere decir que esta compuesto de cuatro -1 de un byte, por tanto de la misma manera memset(array, -1, sizeof array) hará que se setee todos los elementos de nuestro array a -1, podemos hacer muchas cosas con esta función y una pregunta es que produce memset(array, 1, sizeof array)? 

La clase Bitset en C++

Como hemos visto hasta ahora una limitación esta en el tamaño de nuestra máscara de bits, para salvar esto C++ agrega la clase bitset en la cual solo tienes que especificar el tamaño para poder usarla, y además esta bien optimizada, veamos esto en clases: bitset.