Extrayendo N bits de la derecha de un entero

Question

En la ronda de calificación de Atasco de código de ayer http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0, hubo un problema llamado cadena de pargo. A partir del análisis del concurso, llegué a saber que el problema requiere algo así como extraer los N bits más a la derecha de un entero y comprobar si son 1. Vi el código de un competidor (Eireksten) que realizaba dicha operación como a continuación:

(((K&(1<<N)-1))==(1<<N)-1) 

No pude entender cómo funciona esto. ¿Para qué sirve -1 en la comparación? Si alguien puede explicar esto, sería muy útil para nosotros novatos. Además, cualquier consejo para identificar este tipo de problemas sería muy apreciado. Utilicé un algoritmo ingenuo para resolver este problema y terminé resolviendo solo el conjunto de datos más pequeño. (Se tardó mucho tiempo en compilar el conjunto de datos más grande que se debe enviar en 8 minutos). Gracias por adelantado.

Answer 1

Usemos N = 3 como ejemplo. En binario, 1<<3 == 0b1000. Entonces 1<<3 - 1 == 0b111.

En general, 1<<N - 1 crea un número con N en forma binaria.

Deje R = 1<<N-1. Entonces la expresión se convierte en (K&R) == R. El K&R extraerá los últimos N bits, por ejemplo:

 101001010 
    &  111 
    ———————————— 
    000000010 

(Recordemos que el bit a bit-y volverá 1 en un dígito, si y sólo si ambos operandos tienen un 1 en ese dígito.)

La igualdad se cumple si y solo si los últimos N bits son todos 1. Por lo tanto, la expresión comprueba si K termina con N unos.

Answer 2

Por ejemplo: N = 3, K = 101010

1. (1<<N) = 001000 (shift function) 
2. (1<<N)-1 = 000111 (http://en.wikipedia.org/wiki/Two's_complement) 
3. K&(1<<N)-1 = 0000010 (Bitmask) 
4. K&(1<<N)-1 == (1<<N)-1) = (0000010 == 000111) = FALSE 

Answer 3

creo que podemos reconocer este tipo de problema mediante el cálculo de la respuesta con la mano en primer lugar, por alguna serie de N (por ejemplo, 1,2, 3, ...). Después de eso, reconoceremos el cambio de estado y luego escribiremos una función para automatizar el proceso (primera función). Ejecute el programa para algunas entradas y observe el patrón.

Cuando obtengamos el patrón, escriba la función que representa el patrón (segunda función), y compare la salida de la primera función y la segunda función.

Para el caso de Code Jam, podemos ejecutar ambas funciones contra el pequeño conjunto de datos y verificar la salida. Si es idéntico, tenemos una alta probabilidad de que la segunda función pueda resolver el gran conjunto de datos a tiempo.

Answer 4

Estaba trabajando en el problema de la Cadena de Snapper y vine a buscar una explicación sobre cómo funcionaba el algoritmo de bifurcación que encontré en las soluciones. Encontré una buena información, pero todavía me tomó un buen tiempo averiguarlo por mí mismo, siendo un novato bitwise.

Aquí está mi intento de explicar el algoritmo y cómo idearlo. Si enumeramos todos los posibles estados de encendido y apagado para cada pargo en una cadena, vemos un patrón. Dado el caso de prueba N = 3, K = 7 (3 snappers, 7 broches), mostramos la potencia y ON/OFF estados para cada pargo por cada k-ésimo encajen:

  1 2 3 
    0b:1 1 1.1 1.0 0.0 -> ON for n=1 
0b:10 2 1.0 0.1 0.0 
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2 
0b:100 4 1.0 0.0 1.0 
0b:101 5 1.1 1.0 1.0 -> ON for n=1 
0b:110 6 1.0 0.1 0.1 
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3 

La bombilla se enciende cuando todos snappers están encendidos y recibiendo potencia, o cuando tenemos un k-snap que da como resultado n 1s.Aún más simple, la bombilla está encendida cuando todos los pargos están ENCENDIDOS, ya que todos deben estar recibiendo energía para estar ENCENDIDOS (y por lo tanto, la bombilla). Esto significa que por cada K snaps, necesitamos n 1s.

Además, puede observar que k es todo 1s binarios no solo para k = 7 que satisface n = 3, sino para k = 3 que satisface n = 2 yk = 1 que satisface n = 1. Además, para n = 1 o 2 vemos que cada número de instantáneas que enciende la bombilla, los últimos n dígitos de k son siempre 1. Podemos intentar generalizar que todas las k que satisfagan n pargos sean un número binario que termina en n dígitos de 1.

podemos utilizar la expresión señalado por un cartel antes del 1 de < < n - 1 = 0b111 - 1 siempre nos n dígitos binarios de 1, o en este caso, 1 < < 3 da. Si tratamos nuestra cadena de n pargos como un número binario donde cada dígito representa encendido/apagado, y queremos n dígitos de uno, esto nos da nuestra representación.

Ahora queremos encontrar aquellos casos en los que 1 < < n - 1 es igual a algún k que termina en n dígitos binarios de 1, lo que hacemos mediante la realización de un bit a bit-y: k & (1 < < n - 1) para obtener los últimos n dígitos de k, y luego compararlo con 1 < < n - 1.

Supongo que este tipo de pensamiento es más natural después de trabajar mucho con estos tipos de problemas, pero sigue siendo intimidante para mí y dudo que alguna vez hubiera llegado a una solución de este tipo.

aquí está mi solución en Perl:

$tests = <>; 
for (1..$tests) { 
    ($n, $k) = split//, <>; 
    $m = 1 << $n - 1; 
    printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF'; 
}