Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
cpp-avanzado:operaciones-de-bits [2017/11/27 03:26] santo [Representación de Conjuntos (máscaras de bits)] |
cpp-avanzado:operaciones-de-bits [2018/01/02 02:51] (actual) guty [Desplazamiento de bits (Shift de bits)] |
||
---|---|---|---|
Línea 112: | Línea 112: | ||
$$ | $$ | ||
- | Una **aplicación muy común** de los shift de bits es **obtener el k-ésimo bit de un número**. Usando que ''1 << k'' nos da el número $2^k$, cuya representación tiene solamente el k-ésimo bit igual a $1$, podemos acceder al k-ésimo bit de un número $x$ en C++ haciendo '' x & (1 << k) ''. | + | Una **aplicación muy común** de los shift de bits es **obtener el k-ésimo bit de un número**. Usando que ''1 << k'' nos da el número $2^k$, cuya representación tiene solamente el k-ésimo bit igual a $1$, podemos acceder al k-ésimo bit de un número $x$ en C++ haciendo '' x & (1 << k) '' (si el k-ésimo bit es 1, nos devuelve $2^k$. Entonces si quisiéramos saber solo si es 1 o no, debemos escribir algo como: '' (x & (1 << k)) != 0 ''). |
Si estamos **trabajando con 64 bits** hay que tener cuidado y escribir ''1LL << k'' si queremos tener al número $2^k$ con $k \geq 31$ (el motivo de esto se explica [[curso-cpp:mas-tipos#tipo_de_un_literal_entero|aquí]]). | Si estamos **trabajando con 64 bits** hay que tener cuidado y escribir ''1LL << k'' si queremos tener al número $2^k$ con $k \geq 31$ (el motivo de esto se explica [[curso-cpp:mas-tipos#tipo_de_un_literal_entero|aquí]]). | ||
Línea 150: | Línea 150: | ||
$$ | $$ | ||
- | 00000000000000000000\overset{\cdots}{0}0\overset{9}{0}\overset{8}{1}\overset{7}{0}\overset{6}{0}\overset{5}{0}\overset{4}{1}\overset{3}{1}\overset{2}{0}\overset{1}{1}\overset{0}{0} | + | a = 00000000000000000000\overset{\cdots}{0}0\overset{9}{0}\overset{8}{1}\overset{7}{0}\overset{6}{0}\overset{5}{0}\overset{4}{1}\overset{3}{1}\overset{2}{0}\overset{1}{1}\overset{0}{0} = 282 |
$$ | $$ | ||
- | Entonces, utilizando las operaciones de bits que vimos más arriba podemos describir las operaciones entre conjuntos de manera práctica y compacta. Se pueden resumir en : ($a$ es la máscara de bits (así llamamos algunas veces cuando un entero represente un subconjunto) que representa al conjunto $\mathcal{A}$ y $b$ es la máscara que representa al conjunto $\mathcal{B}$) | + | Entonces, utilizando las operaciones de bits que vimos más arriba podemos describir las operaciones entre conjuntos de manera práctica y compacta. La siguiente tabla muestra un resumen de estas operaciones: $a$ es la //máscara de bits//((Se llama así a un entero que representa un conjunto mediante sus bits, de la forma ya explicada)) que representa al conjunto $\mathcal{A}$, y $b$ es la máscara que representa al conjunto $\mathcal{B}$. |
$$ | $$ | ||
\begin{matrix} | \begin{matrix} | ||
Línea 178: | Línea 178: | ||
<code cpp> | <code cpp> | ||
- | for (int i = 0; i < 32; i++) | + | for (int i = 0; i < n; i++) |
{ | { | ||
- | if (x & (1 << i) ) // Si el i-ésimo bit tiene un 1... | + | if ((x & (1 << i)) != 0 ) // Si el i-ésimo bit tiene un 1... |
{ | { | ||
// Hago lo que quiero con i (o A[i] si queremos usar los valores) ... | // Hago lo que quiero con i (o A[i] si queremos usar los valores) ... | ||
Línea 196: | Línea 196: | ||
</code> | </code> | ||
- | Si tenemos una máscara $x$ que ya representa a un subconjunto, podemos **iterar en todos los subconjuntos de los elementos de esa máscara $x$** de la siguiente forma | + | Si tenemos una máscara $x$ que ya representa a un conjunto $\mathcal{X}$, podemos **iterar en todos los subconjuntos de los elementos de esa máscara $x$** de la siguiente forma |
<code cpp> | <code cpp> | ||
Línea 207: | Línea 207: | ||
</code> | </code> | ||
+ | La versión anterior itera las máscaras correspondientes a todos los subconjuntos, de menor a mayor. La siguiente en cambio los recorre de mayor a menor, y no incluye ni la máscara $x$ ni la máscara $0$ (correspondientes a $\mathcal{X}$ y a $\varnothing$). | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | for (int b = (x-1)&x; b != 0 ; b=(b-1)&x) | ||
+ | { | ||
+ | // Hago lo que quiero con el subconjunto b, incluido en el subconjunto que representa x | ||
+ | } | ||
+ | </code> | ||