Resolución algorítmica de problemas: cómo calcular de manera eficiente la paridad de una secuencia de números

Programación

Planteamiento del problema:

Está obteniendo un flujo de números (digamos longnúmeros de tipo), calcule la paridad de los números. Hipotéticamente, tienes que servir una escala enorme, como 1 millón de números por minuto. Diseñe un algoritmo considerando dicha escala. La paridad de un número es 1 si el número total de bits establecidos en la representación binaria del número es impar, de lo contrario la paridad es 0.

Solución:

Enfoque 1 - Fuerza bruta:

El enunciado del problema establece claramente qué es la paridad. Podemos calcular el número total de bits establecidos en la representación binaria del número dado. Si el número total de bits establecidos es impar, la paridad es 1otra 0. Entonces, la forma ingenua es seguir haciendo un desplazamiento a la derecha bit a bit en el número dado y verificar el bit menos significativo actual (LSB) para realizar un seguimiento del resultado.

En el fragmento de código anterior, revisamos todos los bits del whilebucle uno por uno. Con la condición ((no & 1) == 1), comprobamos si el LSB actual es 1o 0, si 1lo hacemos result ^= 1. La variable resultse inicializa en 0. Entonces, cuando hacemos una xor (^)operación entre el valor actual de result& 1, resultse establecerá en 1si resultes actualmente 0, de lo contrario 1.

Si hay un número par de bits establecidos, eventualmente resultse convertirá en 0porque xorentre todos 1’sse cancelarán entre sí. Si hay un número impar de 1’s, el valor final de resultserá 1. no >>> 1 a la derecha desplaza los bits en 1.

>; >> es un operador lógico de desplazamiento a la derecha en Java que también desplaza el bit de signo (el bit más significativo en un número con signo). Hay otra opción de desplazamiento a la derecha er- >> que se llama operador aritmético de desplazamiento a la derecha [consulte la referencia 1 al final de la página]. No cambia el bit de signo en la representación binaria; el bit de signo permanece intacto en su ition. Finalresultado positivo y 0x1 devuelve 1 si ehay paridad o 0 en caso contrario.

Ventajas:

  1. La solución es muy fácil de entender e implementar.

Desventajas:

  1. Estamos procesando todos los bits manualmente, por lo que este enfoque apenas es eficiente a escala.

Complejidad de tiempo:O(n) donde nes el número total de bits en la representación binaria del número dado.

Método 2: borre todos los bits establecidos uno por uno:

Hay un cuello de botella en la solución anterior: el whilebucle en sí. Simplemente revisa todos los bits uno por uno, ¿realmente necesitamos hacer eso? Nuestra preocupación son los bits establecidos, por lo que no obtenemos ningún beneficio al pasar por bits o 0bits no establecidos. Si podemos repasar solo los bits establecidos, nuestra solución se optimiza un poco más. En el cálculo bit a bit, si se nos da un número n, podemos borrar el bit establecido más a la derecha con la siguiente operación:

n = n & (n-1)

Tomemos un ejemplo: decir n = 40, la representación binaria en formato de 8 bits es: 00101000.

n = 0010 1000 n - 1 = 0010 0111 n & (n - 1) = 0010 0000

Hemos borrado con éxito el bit establecido más bajo (cuarto bit desde el lado derecho). Si seguimos haciendo esto, el número nse convertirá 0en un determinado momento. Con base en esta lógica, si calculamos la paridad, no necesitamos escanear todos los bits. Más bien, escaneamos solo los kbits donde kestá el número total de bits establecidos en el número & k <= length of the binary representation. A continuación se muestra el código:

Ventajas:

  1. Simple de implementar.
  2. Más eficiente que la solución de fuerza bruta.

Desventajas:

  1. No es la solución más eficiente.

Complejidad del tiempo:

O(k)donde kes el número total de bits establecidos en el número.

Enfoque 3 - Almacenamiento en caché:

Mire la declaración del problema una vez más, definitivamente hay una preocupación sobre la escala. ¿Pueden nuestras soluciones anteriores escalar para atender millones de solicitudes o aún hay margen para mejorar?

Probablemente podamos hacer que la solución sea más rápida si podemos almacenar el resultado en la memoria caché. De esta forma podemos ahorrar algunos ciclos de CPU para calcular el mismo resultado. Entonces, si el número total de bits es 64, ¿cuánta memoria necesitamos para guardar todos los números posibles? 64Los bits nos llevarán a tener Math.pow(2, 64)posibles números con signo (el bit más significativo se usa para almacenar solo el signo). El tamaño de un longnúmero de tipo es 64bits o 8bytes, por lo que el tamaño total de memoria requerido es: 64 * Math.pow(2, 64)bits o 134217728 TeraBytes. Esto es demasiado y no vale la pena almacenar una cantidad tan enorme de datos. ¿Podemos hacerlo mejor?

Podemos dividir el 64número de bits en un grupo de 16bits, obtener la paridad de esos grupos individuales de bits de la caché y combinarlos. Esta solución funciona porque se 16divide 64en 4partes iguales y nos preocupa el número total de bits establecidos. En la medida en que obtengamos paridad de esos grupos individuales de bits, podemos xorsus resultados entre sí, ya que xores asociativo y conmutativo. El orden en el que extraemos ese grupo de bits y operamos en ellos ni siquiera importa.

Si almacenamos los 16números de bits como un número entero, se requiere memoria total es: Math.pow(2, 16) * 32 bits = 256 Kilo Bytes.

En el fragmento anterior, cambiamos un grupo de 16bits por i * WORD_SIZEdonde

0 ≤ i ≤ 3y hacemos la ANDoperación bit a bit ( &) con un mask = 0xFFFF( 0xFFFF = 1111111111111111 ) para que podamos extraer los 16bits más a la derecha como variables enteras como masked1, masked2, etc., pasamos estas variables a un método checkAndSetInCacheque calcula la paridad de este número en caso de que no esté disponible en la caché. Al final, simplemente operamos xorsobre el resultado de este grupo de números que determina la paridad final del número dado.

Ventajas:

  1. A costa de una memoria relativamente pequeña para la caché, obtenemos una mayor eficiencia ya que estamos reutilizando un grupo de números de 16 bits en las entradas.
  2. Esta solución puede escalar bien ya que estamos sirviendo a millones de números.

Desventajas:

  1. Si este algoritmo debe implementarse en un dispositivo de memoria ultrabaja, la complejidad del espacio debe pensarse bien de antemano para decidir si vale la pena acomodar tal cantidad de espacio.

Complejidad del tiempo:

O(n / WORD_SIZE)donde nes el número total de bits en la representación binaria. Todas las &, |, ~operaciones de desplazamiento a la derecha / izquierda y bit a bit, etc.son operaciones a nivel de palabra que la CPU realiza de manera extremadamente eficiente. De ahí que se suponga que sea su complejidad temporal O(1).

Método 4: uso de XOR y operaciones de cambio:

Vamos a considerar esta representación binaria de 8 bits: 1010 0100. La paridad de este número es 1. ¿Qué sucede cuando hacemos un desplazamiento a la derecha en este número con 4& xo con el número mismo?

n = 1010 0100 n >>> 4 = 0000 1010 n ^ (n >> 4) = 1010 1110 n = n ^ (n >>> 4) = 1010 1110 (n is just assigned to the result)

En los 4bits de la derecha , se establecen todos los bits que son diferentes en n& n >&gt;> 4. Ahora concentrémonos en esto 4 veces más a la derecha ts o: 1110, olvidémonos de otros ipuntos. Now n is 1010 1110 y solo estamos concentrados en el e4 b más bajo, its es decir; 1110. Hagamos un sdesplazamiento a la derecha bit a bit en n por 2.

n = 1010 1110 n >>> 2 = 0010 1011 n ^ (n >>> 2) = 1000 0101 n = n ^ (n >>> 2) = 1000 0101 (n is just assigned to the result)

Simplemente concéntrese en los 2bits más a la derecha ahora y olvídese de los 6bits más a la izquierda . Cambiemos el número a la derecha por 1:

n = 1000 0101 n >>> 1 = 0100 0010 n ^ (n >>> 1) = 1100 0111 n = n ^ (n >>> 1) = 1100 0111 (n is just assigned to the result)

No necesitamos a desplazamiento a la derecha, ahora nos acaba de extraer el bit LSB, que es 1en el caso anterior y devolver el resultado: result = (short) n & 1.

At a glance, the solution might look a little confusing, but it works. How? We know that 0 xor 1 or 1 xor 0 is 1, otherwise 0. So when we divide the binary representation of a number into two equal halves by length & we do xor between them, all different pair of bits result into set bits in the xor-ed number.

Since parity occurs when an odd number of set bits are there in the binary representation, we can use xor operation to check if an odd number of 1 exists there. Hence we right shift the number by half of the total number of digits, we xor that shifted number with the original number, we assign the xor-ed result to the original number & we concentrate only on the rightmost half of the number now. So we are just xoring half of the numbers at a time & reduce our scope of xor. For 64 bit numbers, we start xoring with 32 bit halves, then 16 bit halves, then 8, 4, 2, 1 respectively.

Essentially, parity of a number means parity of xor of equal halves of the binary representation of that number. The crux of the algorithm is to concentrate on rightmost 32 bits first, then 16, 8, 4 , 2 , 1 bits & ignore other left side bits. Following is the code:

Advantages:

  1. No extra space uses word-level operations to compute the result.

Disadvantages:

  1. Might be little difficult to understand for developers.

Time Complexity:

O(log n) where n is the total number of bits in the binary representation.

Following is the full working code:

import java.util.Arrays; public class ParityOfNumber { private static short computeParityBruteForce(long no) { int result = 0; while(no != 0) { if((no & 1) == 1) { result ^= 1; } no >>>= 1; } return (short) (result & 0x1); } private static short computeParityBasedOnClearingSetBit(long no) { int result = 0; while (no != 0) { no = no & (no - 1); result ^= 1; } return (short) (result & 0x1); } private static short computeParityWithCaching(long no) { int[] cache = new int[(int) Math.pow(2, 16)]; Arrays.fill(cache, -1); int WORD_SIZE = 16; int mask = 0xFFFF; int masked1 = (int) ((no >>> (3 * WORD_SIZE)) & mask); checkAndSetInCache(masked1, cache); int masked2 = (int) ((no >>> (2 * WORD_SIZE)) & mask); checkAndSetInCache(masked2, cache); int masked3 = (int) ((no >>> WORD_SIZE) & mask); checkAndSetInCache(masked3, cache); int masked4 = (int) (no & mask); checkAndSetInCache(masked4, cache); int result = (cache[masked1] ^ cache[masked2] ^ cache[masked3] ^ cache[masked4]); return (short) (result & 0x1); } private static void checkAndSetInCache(int val, int[] cache) { if(cache[val] >> 32); no ^= (no >>> 16); no ^= (no >>> 8); no ^= (no >>> 4); no ^= (no >>> 2); no ^= (no >>> 1); return (short) (no & 1); } public static void main(String[] args) { long no = 1274849; System.out.println("Binary representation of the number: " + Long.toBinaryString(no)); System.out.println("Is Parity [computeParityBruteForce]: " + computeParityBruteForce(no)); System.out.println("Is Parity [computeParityBasedOnClearingSetBit]: " + computeParityBasedOnClearingSetBit(no)); System.out.println("Is Parity [computeParityMostEfficient]: " + computeParityMostEfficient(no)); System.out.println("Is Parity [computeParityWithCaching]: " + computeParityWithCaching(no)); } }

Learning from this exercise:

  1. Although it’s basic knowledge, I want to mention that word level bitwise operations is constant in time.
  2. At a scale, we can apply caching by breaking down the binary representation into equal halves of suitable word size like 16 in our case so that we can accommodate all possible numbers in memory. Since we are supposed to handle millions of numbers, we will end up reusing 16 bit groups from cache across numbers. The word size does not necessarily need to be 16, it depends on your requirement & experiments.
  3. You don’t need to store the binary representation of a number in the separate array to operate on it, rather clever use of bitwise operations can help you achieve your target.

References:

[1]. //stackoverflow.com/questions/2811319/difference-between-and

[2]. //gist.github.com/kousiknath/b0f5cd204369c5cd1669535cc9a58a53