Bitmask 1

Las mascaras de bits, se refieren a la forma binaria que tiene toda variable en vista del ordenador,  en este tema nos referiremos como podemos manipular sus atributos a beneficio nuestro.

Los ordenadores tienen una forma y 

heurística para manejar cada variable: el lenguaje binario y otras cosas más. Estos van desde cambiar un bit (Binary digit) de 0 a 1, o viceversa, hasta la comunicación que se realiza entre diferentes partes de este. 

Representación binaria de un entero

Un ordenador común, maneja ciertos estándares sobre el manejo de bits, pero el lenguaje de programación, en nuestro caso C/C++, fijara cuantos bits usa una variable y como manipularlos (dependiento del ordenador aunque no se alarme, esto no nos afectará), nosotros debemos saber que las variables enteras (short, int, long, long long) usan un bit para el signo, o sea si el bit esta en 1 el

número es negativo y en otro caso, es positivo; ya sabemos que una variable tipo int usa 4 bytes, por tanto usa 32 bits, como un bit es responsable del signo, nosotros tendremos que 31 bits serán destinados puramente a la representacion del número (en base 2).

A la derecha podemos observar la representación de un número con un solo byte y con el respectivo bit de signo. Como hemos dicho todos menos el bit de signo suman para la representación binaria del número. 

Aritmética de conjuntos

C/C++ nos permiten manejar a nuestro antojo la representación binaria de las variable, pero

antes de ello debemos saber un poco de la ya muy conocida aritmética de conjuntos.

1. Pertenencia: Si un elemento x está en A escribiremos: $$x \in A$$

y si x no está en A se escribirá: $$x \notin A$$

2. Subconjunto: Si todo elemento del conjunto A además está en B, diremos que A es un subconjunto de B y 

escribiremos: $$A \subseteq B$$ 

3. Complemento: Al conjunto de elementos que no pertenecen a A lo llamaremos complemento de A siendo este el conjunto: $$A^c = \lbrace x : x \notin A\rbrace$$

4. Unión: La unión de dos conjuntos A y B es el conjunto $$A \cup B = \lbrace x : x \in A~o~x \in B \rbrace $$

5. Intercección: La intersecón de dos conjuntos A y B es el conjunto: $$A \cap B = \lbrace x : x \in A~y~x \in B \rbrace $$

6. Complemento de B relativo a A: El complemento de B relativo a A es el conjunto: $$A \backslash B = \lbrace x : x \in A~y~x \notin B \rbrace $$

7. Diferencia simétrica: El conjunto difrencia simétria de A y B es: $$A \triangle B = \lbrace x: x~\in~ B \backslash A~y~x~\in~A \backslash B \rbrace$$.

El conjunto que no tiene elemento es llamando conjunto nulo y es denotado por el simbolo $\emptyset$. Dos conjuntos A y B se dicen disjuntos si no tienen elementos en común; esto puede ser expresado escribiendo $A \cap B = \emptyset$.

 De representación binaria a conjuntos

Podemos ver la repersentación binaria de una variable como un conjunto de etiquetas, asi tenemos 

un isomorfismo del conjunto $\lbrace 0, 1, 2, ..., n-1 \rbrace$ (indices en mi representación binaria) hacia el conjunto $ \lbrace x_0, x_1, x_2, x_{n-1} \rbrace $ de elementos arbitrarios. esta forma de pensar la representación binaria es muy útil como veremos ahora mismo.

1. Definición: Diremos que el elemento $x_i$ pertenece a nuestra máscara de bits A si el i-ésimo bit de A es 1.

Dado esta definición si A es el conjunto vacío, entonces A $=$ 0.

Aritmética de conjuntos en C/C++

Dado nuestra simple definición podemos usar los operadores de manejo de bits en C/C++ para

hacer nuestra aritmética de conjuntos.

1. universo (U): Debo tener mucho cuidado con este concepto ya que la cantidad de elementos o índices que tengo a mi disposición es muy reducido y depende también del tipo de variable que use para mí máscara de bits, en general este número es igual a la cantidad de bits que dispongo.

2. complemento:  El complemento siempre será relativo al universo asi $$A^c = \lbrace x : x \notin A ~y~ x \in U \rbrace$$

En C/C++ dada mi mascara de bits A, yo tendre $A^c = ~ \sim A$.

3. intersección: Dadas dos máscaras de bits A y B en el mismo universo (recuerde que en C\C++ si dos variables se están operando, entonces, la de menor prioridad tomará el tipo del de la mayor prioridad. Ejemplo: si un int con un long long se suman el int se volverá long long), la intersección se puede hallar con la siguiente operación: $$A \cap B = A \& B$$. 

4. unión: Dadas dos máscaras de bits A y B en el mismo universo, la unión se puede hallar con la siguiente operación: $$A \cup B = A \mid B$$.

5. Subconjunto: Se puede saber si una máscara de bits A está incluida en otra máscara de bits B, de la siguiente forma: $$A \subset B  \text{ si y solo si,  } A \& B = A $$.

6. Complemento de B relativo a A: El conjunto complemento de la máscara de bits B relativo a la máscara de bits A se hallarán así: $$B \backslash A~ = ~ (\sim B) \& A$$.

5. Diferencia simétrica: El comjunto diferencia simétrica de las máscaras de bits A y B se hallarán así: $$A \triangle B = A \wedge B$$

nota: $\wedge$ también es conocdio como xor.

Aritmética adicional de conjuntos en C/C++

Además de la aritmética tradicional de conjuntos en C/C++ hay operadores y funciones adicionales para su mejor uso, veremos los más importantes:

1. Operación $+$: Esto se puede hacer con el no tan conocido corrimiento de bits, hay dos tipos de corrimiento de bits: corrimiento de bits a la izquierda y corrimiento de bits a la derecha, ellos nos permiten hacer lo siguiente: desplazar los indices de mi máscara de bits r posiciones, donde r puede ser cualquier entero, entonces la suma se define así: $$A + r = \lbrace x+r : x \in A \rbrace $$ $$= A<<r \text{, si r es no negativo }$$ $$ = A>>r \text{, si r es no positivo}$$. 

nota: hay un límite para correr bits, tanto a la izquierda como a la derecha, esto quiere decir que si los bits salen de mi capacidad tanto si es menor a 0 o mayor igual a la máxima cantitdadde bits, entonces estos bits se perderán.

2.  Cardinalidad de un conjunto: Existe una función de compilador en C/C++ que permite hacer  esto muy simple y en un tiempo de ejecución O(1): $$ \mid A \mid ~= \_\_builtin\_popcount(A) $$.

De conjuntos a números:

Ahora que y conocemos la aritmética de conjuntos en C/C++ usted habrá notado que cada entero tiene una dualidad entre conjunto y valor con el cual trabajamos, esta dualidad nos permitirá hacer ciertas cosas adicionales:

1. Conjunto unitario: Es de observar que un conjunto unitario es una potencia de dos (sin considerar el bit de signo), esto quiere decir que: $2^r = \lbrace r \rbrace.$ además sabemos  que $\lbrace r \rbrace = \lbrace 0 \rbrace + r$ por tanto: $$2^r = 2^0 << r = (1 << r)$$.

2. Multiplicación por una potencia de dos: Dado lo anterior el calculo de x.$2^r$ es sencillo ya que: $$x.2^r = x*(1<<r)$$ pero, es más eficiente: $$(x<<r)$$.

3. Paridad:  Sabemos que un número es impar si en su representación binaria el coeficiente de $2^0$ es 1, esto quiere decir que si vemos a un número A en su dualidad conjunto-valor diremos que es par si $$A \cap \lbrace 0 \rbrace =  \emptyset \text{, que es los mismo a } A \& 1 = 0$$


4. Conjuntos LR: Llamaremos así a los conjuntos de la forma $LR~=~\lbrace l,~l+1,~\dots,~r \rbrace$. Estos conjuntos son muy útiles y fáciles de formar, comenzando que el conjunto: $$\lbrace  0, 1,~2,~\dots,~r - l\rbrace~=~2^0~+~2^1~+~\dots~+2^{r-l}~=~2^{r-l+1}~-~1~=~(1<<r-l+1) - 1$$.

nota: el corrimiento de bits es un operador con muy poca prioridad por ello $(1<<r-l+1)$ será igual a $(1<<(r-l+1))$. 

Ahora formar el conjunto LR es muy sencillo, será: $$LR = \lbrace 0,~1,~\dots~r-l \rbrace~+~l~=~(((1<<r-l+1) - 1)<<l) $$.

5. Negación: Para negar un entero x en C/C++ se usa el llamado complemento a 2, eso no es más que la negación de la variable más 1, así: $$ -n~=~\sim n~+~1$$

nota: sea a10$\dots$0 la repersentación binaria de n, entonces $n-1$ es de la forma a01$\dots$1.

6. Test de potencia de 2: Este es un test para saber si $n \geq 1$ es igual a $2^k$, para algún $k \in \aleph \cup \lbrace 0 \rbrace$.

afirmación: $n = 2^k$ para algún $k \in \aleph \cup \lbrace 0 \rbrace$ si y solo si $n \cap (n-1) = \emptyset$

prueba: Si prestamos atención a la nota anterior, podremos darnos cuenta que $n \& (n-1) = a$, esta es la parte que sigue al primer bit, entonces, $a = 0$, si y solo si,  $n = 0\dots 010\dots 0$ que termina la prueba.

nota: Podemos usar también la funcion $\_\_builtin\_popcount()$, pero está es menos eficiente por una constante.

7. Menor potencia prendida (lso()): El menor bit significativo de un entero n es la potencia con menor exponente en el desarrollo en base 2 de n que tiene coeficiente 0. Este es relativamente fácil de hallar en O(1): $$ lso(n) = n\&-n$$ Esto se debe a que si el desarrollo en base 2 de n es $$a10\dots0$$, entonces, $$-n~=~\sim n~+~1~=~(\sim a)01\dots 1~+~1~=~(\sim a)10\dots 0$$ por tanto $$n\&-n~=~0\dots 010\dots 0$$.

8. Mayor bit significativo: No existe una función en C/C++ que pueda hacer esto por si sola, pero existe una función de compilador llamada $\_\_builtin\_clz()$ que permite hallar la cantidad de 0s después del mayor bit prendido en una variable, entonces si trabajamos con enteros y ellos tienen 32 bits, entonces el calculo sería: $$gb(n)~=~31~-~\_\_builtin\_clz(n)$$ tenga en cuenta que se pone 31 ya que los bits son enumeramos desde 0 al 31.

9. Recorriendo todos los subconjuntos de $\lbrace 0,~1~,~\dots,~n-1 \rbrace$: Dado este punto esto resulta muy sencillo, usted debera probar que todos los subconjuntos $\lbrace 0,~1~,~\dots,~n-1 \rbrace$ pertenecen a las máscaras $\lbrace 0,~1~,~\dots,~2^n-1 \rbrace$, tenga muy claro que este nuevo conjunto es un conjunto con máscaras de bits como elementos, así es fácil recorrer todos ellos con un simple for.

10. Recorriendo todos los subconjuntos de un conjunto dado:



Máscara de bits como un conjunto dinámico:

Para conseguir que nuestra máscara de bits trabaje como un conjunto dinámico necesitamos tres cosas principalmente, en buen tiempo de ejcución: buscar un elemento, agregar un elemento y eliminar un elemento.

1. buscar (find): es fácil implementar la función find en nuestra máscara de bits,  esto se debe lograr por el hecho que  si $x \in A$, entonces $x \cap A \neq \emptyset$

2. insertar (insert): La función insert será $A = A \cup \lbrace x \rbrace$ para insertar x en nuestro conjunto.

3. Eliminar (erase):  Esta función tampoco es complicada y debe usted poder probar si mayor complicación que es igual a la siguiente operación: $A = A \cap \lbrace x \rbrace^c$.

Aquí les dejo un link a mi github con una pequeña implementación:  

Operación flip:

Para esta parte nosotros pensaremos las máscaras de bits como focos que tienen dos estados: encendido y apagado. Entonces yo tengo algunas operaciones importantes: apagar un foco, encender un foco, cambiar el estado de un foco (de apagado a encendido, de encendido a apagado), Apagar, encender y cambiar el estado de un subconjunto específico de focos.

Como es de apreciar las primeras dos operaciones para un elemento y las primeras dos operaciones para un subconjunto de elementos lo podemos hacer con nuestras operaciones de insertar y eliminar.

La tercera operación para cada caso será la que discutiremos.

A este punto nosotros quizás nos hemos dado cuenta que esta operación es la diferencia simétrica, se hablará más de la diferencia simétrica en otra clase, pero usted puede comprobar que efectivamente, aplicar diferencia simétrica prende los focos que estabas apagados y apaga los que estaban prendidos.

Ejercicios:

1. hacer una función que bote -1 en caso que un entero sea negativo y 0 en otro caso.

2. intercambie dos enteros x e y, se entiende que ahora x sera y e y tendra el valor inicial de x.

3. hacer una función que reciba dos enteros que te evalue la siguiente sentencia: "x e y tienen el mismo signo".

4. Encuentra el minimo de dos enteros.

5. Encuentra el máximo de dos enteros.

6. Haga una función que determine si un número es una potencia de 2.

soluciones: 

Problemas: