¿Cómo aplicar operaciones de bits en la búsqueda?
En realidad, sólo es cuestión de representar cada elemento en el registro de búsqueda como una cadena de bits.
Por ejemplo, el registro de búsqueda consta de todos los subconjuntos del conjunto {a,b,c,d,e,f,g,h}.
{a,b,c}, {a,b,d}, {a,c,d}......
Se puede utilizar cada subconjunto Cadena de bits representación
{a,b,c} => 11100000
{a,b,d} => 11010000
{a,c, d} = > 10110000
La búsqueda es el proceso de comparar si cada elemento en el registro buscado es igual a un valor determinado. Aquí, simplemente comparar dos conjuntos es más molesto.
Por ejemplo, para comparar {a, e, f} y {a, c, d}, debemos asegurarnos de que ambos conjuntos contienen todos los elementos del otro.
Sin embargo, si lo representas como una cadena de bits, puedes usar directamente el operador XOR ^.
{a,e,f}=>10001100
Por lo tanto, debido al uso de la operación XOR, el resultado de la comparación se simplifica a 10001100^10110000, es decir, el resultado de la misma comparación es 0 y la comparación de diferentes resultados es 1.
Aquí, para cada subconjunto, podemos utilizar caracteres sin signo para representarlo.
Operador de comparación sobrecargado
operador bool== (unsigned char chPrimero, unsigned char chSegundo)const
{
¡retorno! (chFirst^chSecond);
}
Esto le permite comparar dos conjuntos cuando busca igualdad.
//////////////////////////////////////////// // ///////////////////////////////////////////////// ///// ///////////////////
Una vez leí un libro llamado "Programming Pearls", y el primer capítulo hablaba de esto.
Supongamos que quiero ordenar 10 números y decir que están en el intervalo [0, 20]. Hay muchas formas de lograr esto a través de estructuras de datos, como clasificación por inserción, clasificación rápida, etc. Pero si miramos de cerca, vemos que estos 10 números son todos números en el intervalo [0, 20]. Por tanto, podemos utilizar 20 bits para representar cada número en el intervalo. El número de secuencia de cada bit representa el número correspondiente. Por ejemplo, el dígito 10 representa el número 10.
Primero establezca los 20 bits en 0, luego lea cada uno de los 10 números y establezca el bit correspondiente en 1.
Por ejemplo, los 10 números son 3, 7, 5, 4, 2...
Establece el 3.º, 7.º, 5.º, 4.º y 2.º dígitos en 1.
p>
0111101...
Finalmente, solo necesita escanear el 1 en la cadena de bits y generar el número de serie de este 1 para obtener el orden de los resultados.
No sé si puedes entender esto.
Este artículo entra en más detalles.
/king821221/article/details/2054353
En aplicaciones prácticas, como en el sistema de archivos del sistema operativo, la tabla de asignación de archivos utiliza un mapa de bits, en el que cada bloque está representado por un bit. 0 significa no asignado, 1 significa asignado. Esto le permite encontrar rápidamente bloques no asignados y calcular la cantidad de espacio restante.