Mis disculpas si esto se ha preguntado / respondido antes, pero honestamente, ni siquiera estoy seguro de cómo formular esto como una pregunta correctamente. Tengo el siguiente patrón de bits:

0110110110110110110110110110110110110110110110110110110110110110

Estoy tratando de realizar un cambio que conserve mi patrón subyacente; mi primer instinto fue usar la rotación correcta ((x >> count) | (x << (-count & 63))) pero la asimetría en mi patrón de bits resulta en:

0011011011011011011011011011011011011011011011011011011011011011 <--- incorrecto

El problema es que el bit más significativo (extremo izquierdo) termina siendo 0 en lugar del 1 deseado:

1011011011011011011011011011011011011011011011011011011011011011 <--- derecha

¿Hay un nombre coloquial para esta función que estoy buscando? Si no es así, ¿cómo podría implementar esta idea?

Información adicional:

  • Si bien la pregunta es independiente del lenguaje, actualmente estoy tratando de resolver esto usando C #.
  • Los patrones de bits que estoy usando son completamente predecibles y siempre tienen la misma estructura; el patrón comienza con un solo cero seguido de n - 1 unos (donde n es un número impar) y luego se repite infinitamente.
  • Me gustaría lograr esto sin operaciones condicionales, ya que derrotarían el propósito de utilizar la manipulación bit a bit en primer lugar, pero tal vez no tengo otra opción ...
2
Kittoes0124 9 ago. 2017 a las 22:31

3 respuestas

La mejor respuesta

Tienes un número estructurado así:

B16  B15  B14  B13  B12  B11  B10  B09  B08  B07  B06  B05  B04  B03  B02  B01  B00

  ?    0    1    1    0    1    1    0    1    1    0    1    1    0    1    1    0

El ? debe aparecer en el MSB (B15, o B63, o lo que sea) después del turno. ¿De dónde viene? Bueno, la copia más cercana se encuentra n lugares a la derecha:

B13    0    1    1    0    1    1    0    1    1    0    1    1    0    1    1    0
 ^--------------/

Si su palabra tiene un ancho w, este es 1 << (w-n)

                 *

Entonces puedes hacer:

var selector = 1 << (w-n);
var rotated = (val >> 1) | ((val & selector) << (n-1));

Pero es posible que desee un turno múltiple. Entonces necesitamos construir una máscara más ancha:

  ?    0    1    1    0    1    1    0    1    1    0    1    1    0    1    1    0
            *    *    *    *    *

Aquí he elegido fingir n = 6, solo tiene que ser un múltiplo del n básico y más grande que shift. Ahora:

var selector = ((1UL << shift) - 1) << (w - n);
var rotated = (val >> shift) | ((val & selector) << (n - shift));

Demostración de trabajo utilizando su patrón: http://rextester.com/UWYSW47054

Es fácil ver que la salida tiene el período 3, según sea necesario:

  1:B6DB6DB6DB6DB6DB
  2:DB6DB6DB6DB6DB6D
  3:6DB6DB6DB6DB6DB6
  4:B6DB6DB6DB6DB6DB
  5:DB6DB6DB6DB6DB6D
  6:6DB6DB6DB6DB6DB6
  7:B6DB6DB6DB6DB6DB
  8:DB6DB6DB6DB6DB6D
  9:6DB6DB6DB6DB6DB6
 10:B6DB6DB6DB6DB6DB
 11:DB6DB6DB6DB6DB6D
2
Ben Voigt 9 ago. 2017 a las 21:56

El problema cambió un poco a través de los comentarios.

Para todos los n razonables, el siguiente problema se puede resolver de manera eficiente después de un cálculo previo mínimo:

Dado un desplazamiento k, obtenga 64 bits comenzando en esa posición en la secuencia de bits que sigue el patrón de repetición (cero, n-1 unos).

Claramente, el patrón se repite con un período de n, por lo que solo se deben generar n diferentes ulong s para cada valor dado de n. Eso podría hacerse explícitamente, construyéndolos todos en el preprocesamiento (podrían construirse de cualquier manera obvia, en realidad no importa, ya que eso solo sucede una vez), o dejarlos más implícitamente almacenando solo dos ulongs por valor para n (esto funciona bajo el supuesto de que n < 64, ver más abajo) y luego extraer un rango de ellos con algunos cambios / OR. De cualquier manera, use offset % n para calcular qué patrón recuperar (dado que el desplazamiento aumenta de manera predecible, no se requiere ninguna operación de módulo real [1] ).

Incluso con el primer método, el consumo de memoria será razonable ya que esta optimización es solo una optimización para n baja: en particular para n > 64 habrá menos de 1 cero por palabra en promedio, por lo que el "viejo forma "de visitar cada múltiplo de n y restablecer ese bit comienza a omitir el trabajo, mientras que el truco anterior aún visitaría cada palabra y ya no podría restablecer varios bits a la vez.

[1]: si hay varios n en juego al mismo tiempo, una posible estrategia es mantener una matriz offsets donde offsets[n] = offset % n, que podría actualizarse de acuerdo con: (no probado)

int next = offsets[n] + _64modn[n]; // 64 % n precomputed
offsets[n] = next - (((n - next - 1) >> 31) & n);

La idea es que n se resta siempre que next >= n. Solo se necesita una resta, ya que el desplazamiento y la cosa añadida al desplazamiento ya están reducidos en el módulo n.

Este incremento de desplazamiento se puede hacer con System.Numerics.Vectors, que tiene muy pocas características en comparación con el hardware real, pero es casi capaz de hacerlo. No puede hacer el cambio (sí, es extraño) pero puede implementar una comparación sin ramificaciones.

Hacer una pasada por valor de n es más fácil, pero toca mucha memoria de manera poco amigable con la caché. Hacer muchas cosas diferentes n al mismo tiempo tampoco puede ser genial. Supongo que tendrías que marcar eso ...

También podría considerar codificarlo para algunos números bajos, algo como offset % 3 es bastante eficiente (a diferencia de offset % variable). Esto requiere un desenrollado manual de bucles, lo cual es un poco molesto, pero en realidad es más simple, solo grande en términos de líneas de código.

1
harold 9 ago. 2017 a las 22:17

En lugar de almacenar muchas repeticiones de un patrón, solo almacene una recurrencia y aplique operaciones de módulo en los índices

byte[] pattern = new byte[] { 0, 1, 1 };

// Get a "bit" at index "i", shifted right by "shift"
byte bit = pattern[(i - shift + 1000000 * byte.Length) % byte.Length];

El + 1000000 * byte.Length debe ser mayor que el mayor cambio esperado y garantiza que obtengamos una suma positiva.

Esto le permite almacenar patrones de prácticamente cualquier longitud.

Una optimización sería almacenar una versión reflejada del patrón. Entonces podría desplazarse a la izquierda en lugar de a la derecha. Esto simplificaría el cálculo del índice

byte bit = pattern[(i + shift) % byte.Length];
1
Olivier Jacot-Descombes 9 ago. 2017 a las 21:40