Rotar un mapa de bits 90 grados

Question

Tengo un entero de 64 bits, que necesito girar 90 grados en un área de 8 x 8 (preferiblemente con manipulación directa de bits). No puedo encontrar ningún algoritmo útil para eso. Por ejemplo, esto:

// 0xD000000000000000 = 1101000000000000000000000000000000000000000000000000000000000000 

1 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

después de la rotación se convierte en esto:

// 0x101000100000000 = 0000000100000001000000000000000100000000000000000000000000000000 

0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

Me pregunto si hay alguna solución sin necesidad de utilizar ninguna tabla hash (s) calculada de antemano?

Answer 1

 
v = (v & 0x000000000f0f0f0fUL) << 004 | (v & 0x00000000f0f0f0f0UL) << 040 | 
    (v & 0xf0f0f0f000000000UL) >> 004 | (v & 0x0f0f0f0f00000000UL) >> 040; 
v = (v & 0x0000333300003333UL) << 002 | (v & 0x0000cccc0000ccccUL) << 020 | 
    (v & 0xcccc0000cccc0000UL) >> 002 | (v & 0x3333000033330000UL) >> 020; 
v = (v & 0x0055005500550055UL) << 001 | (v & 0x00aa00aa00aa00aaUL) << 010 | 
    (v & 0xaa00aa00aa00aa00UL) >> 001 | (v & 0x5500550055005500UL) >> 010; 

Answer 2

Si ve esto como una matriz bidimensional, entonces tiene la solución no? Simplemente haga que las filas sean nuevas columnas. La primera fila es la última columna, la segunda es la anterior al último y así sucesivamente.

Al menos visualmente, parece que es su solución.

Answer 3

probablemente algo así

for(int i = 0; i < 8; i++) 
{ 
    for(int j = 0; j < 8; j++) 
    { 
     new_image[j*8+8-i] = image[i*8+j]; 
    } 
} 

Answer 4

sin utilizar ningún tablas de consulta, no se puede ver mucho mejor que el tratamiento de cada bit individual:

unsigned long r = 0; 
for (int i = 0; i < 64; ++i) { 
    r += ((x >> i) & 1) << (((i % 8) * 8) + (7 - i/8)); 
} 

Answer 5

Si un bucle si es alimentado aceptable, la fórmula para los bits es bastante simple:

8>>Column - Row - 1 

La columna y la fila tienen 0 indexados.

Esto le da este mapeo:

7 15 23 31 39 47 55 63 
6 14 22 ... 
5 ... 
4 ... 
3 ... 
2 ... 
1 ... 
0 8 16 24 32 40 48 54 

Answer 6

Si vas a hacer esto rápido, no debe oponerse a las operaciones de búsqueda tablas.

Rompería los enteros de 64 bits en trozos de N bits, y buscaría los N bits en una tabla de valores de transposición seleccionados por posición. Si elige N = 1, necesita 64 búsquedas en tablas de dos espacios, lo que es relativamente lento. Si elige N = 64, necesita una tabla y una búsqueda, pero la tabla es enorme: -}

N = 8 parece un buen compromiso. Necesitarías 8 tablas de 256 entradas. El código debe ser algo como esto:

// value to transpose is in v, a long 
long r; // result 
r != byte0transpose[(v>>56)&0xFF]; 
r != byte1transpose[(v>>48)&0xFF]; 
r != byte2transpose[(v>>40)&0xFF]; 
r != byte3transpose[(v>>32)&0xFF]; 
r != byte4transpose[(v>>24)&0xFF]; 
r != byte5transpose[(v>>16)&0xFF]; 
r != byte6transpose[(v>>08)&0xFF]; 
r != byte7transpose[(v>>00)&0xFF]; 

Cada tabla contiene los valores precalculados que "extienden" los bits contiguos en la entrada a través del resultado de la transposición de 64 bits. Lo ideal es que calcule este valor fuera de línea y simplemente inicialice las entradas de la tabla.

Si no le importa la velocidad, entonces la matriz estándar transponer algoritmos funcionará; simplemente indexe los 64 bits como si fuera una matriz de bits.

Tengo la sospecha de que se podría calcular la transposición usando bits de tipo twiddling.

Answer 7

Para ampliar mi comentario a la respuesta de Ira, puede utilizar:

#define ROT_BIT_0(X) X, (X)|0x1UL 
#define ROT_BIT_1(X) ROT_BIT_0(X), ROT_BIT_0((X) | 0x100UL) 
#define ROT_BIT_2(X) ROT_BIT_1(X), ROT_BIT_1((X) | 0x10000UL) 
#define ROT_BIT_3(X) ROT_BIT_2(X), ROT_BIT_2((X) | 0x1000000UL) 
#define ROT_BIT_4(X) ROT_BIT_3(X), ROT_BIT_3((X) | 0x100000000UL) 
#define ROT_BIT_5(X) ROT_BIT_4(X), ROT_BIT_4((X) | 0x10000000000UL) 
#define ROT_BIT_6(X) ROT_BIT_5(X), ROT_BIT_5((X) | 0x1000000000000UL) 
#define ROT_BIT_7(X) ROT_BIT_6(X), ROT_BIT_6((X) | 0x100000000000000UL) 

static unsigned long rot90[256] = { ROT_BIT_7(0) }; 

unsigned long rotate90(unsigned long v) 
{ 
    unsigned long r = 0; 
    r |= rot90[(v>>56) & 0xff]; 
    r |= rot90[(v>>48) & 0xff] << 1; 
    r |= rot90[(v>>40) & 0xff] << 2; 
    r |= rot90[(v>>32) & 0xff] << 3; 
    r |= rot90[(v>>24) & 0xff] << 4; 
    r |= rot90[(v>>16) & 0xff] << 5; 
    r |= rot90[(v>>8) & 0xff] << 6; 
    r |= rot90[v & 0xff] << 7; 
    return r; 
} 

Esto depende de 'unsigned long' ser de 64 bits, por supuesto, y lo hace girar el supuesto de los bits están en fila- orden principal con el msb siendo la parte superior derecha, que parece ser el caso en esta pregunta ...

Answer 8

Esto es bastante fácil usando IA32 SIMD, hay un práctico código de operación para extraer cada octavo bit de un valor de 64 bits (esto fue escrito utilizando DevStudio 2005):

char 
    source [8] = {0, 0, 0, 0, 0, 0, 0, 0xd0}, 
    dest [8]; 

__asm 
{ 
    mov ch,3 
    movq xmm0,qword ptr [source] 
Rotate2: 
    lea edi,dest 
    mov cl,8 
Rotate1: 
    pmovmskb eax,xmm0 
    psllq xmm0,1 
    stosb 
    dec cl 
    jnz Rotate1 
    movq xmm0,qword ptr [dest] 
    dec ch 
    jnz Rotate2 
} 

gira los datos tres veces (-270 grados) desde el 90 es un poco más complicado (necesita un poco más de pensamiento)

Answer 9

No es una forma eficiente para llevar a cabo la inversión de bits, utilizando O (log n) Desplazamiento operaciones. Si interpreta un UINT de 64 bits como una matriz de bits de 8x8, la inversión de bit corresponde a una rotación de 180 grados.

La mitad de estos cambios realizan efectivamente una reflexión horizontal; la otra mitad realiza una reflexión vertical. Para obtener rotaciones de 90 y 270 grados, se podría combinar una reflexión ortogonal (es decir, vertical u horizontal) con una reflexión diagonal, pero esta última sigue siendo un poco incómodo.

typedef unsigned long long uint64; 

uint64 reflect_vert (uint64 value) 
{ 
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16); 
    value = ((value & 0xFF00FF00FF00FF00ull) >> 8) | ((value & 0x00FF00FF00FF00FFull) << 8); 
    return value; 
} 

uint64 reflect_horiz (uint64 value) 
{ 
    value = ((value & 0xF0F0F0F0F0F0F0F0ull) >> 4) | ((value & 0x0F0F0F0F0F0F0F0Full) << 4); 
    value = ((value & 0xCCCCCCCCCCCCCCCCull) >> 2) | ((value & 0x3333333333333333ull) << 2); 
    value = ((value & 0xAAAAAAAAAAAAAAAAull) >> 1) | ((value & 0x5555555555555555ull) << 1); 
    return value; 
} 

uint64 reflect_diag (uint64 value) 
{ 
    uint64 new_value = value & 0x8040201008040201ull; // stationary bits 
    new_value |= (value & 0x0100000000000000ull) >> 49; 
    new_value |= (value & 0x0201000000000000ull) >> 42; 
    new_value |= (value & 0x0402010000000000ull) >> 35; 
    new_value |= (value & 0x0804020100000000ull) >> 28; 
    new_value |= (value & 0x1008040201000000ull) >> 21; 
    new_value |= (value & 0x2010080402010000ull) >> 14; 
    new_value |= (value & 0x4020100804020100ull) >> 7; 
    new_value |= (value & 0x0080402010080402ull) << 7; 
    new_value |= (value & 0x0000804020100804ull) << 14; 
    new_value |= (value & 0x0000008040201008ull) << 21; 
    new_value |= (value & 0x0000000080402010ull) << 28; 
    new_value |= (value & 0x0000000000804020ull) << 35; 
    new_value |= (value & 0x0000000000008040ull) << 42; 
    new_value |= (value & 0x0000000000000080ull) << 49; 
    return new_value; 
} 

uint64 rotate_90 (uint64 value) 
{ 
    return reflect_diag (reflect_vert (value)); 
} 

uint64 rotate_180 (uint64 value) 
{ 
    return reflect_horiz (reflect_vert (value)); 
} 

uint64 rotate_270 (uint64 value) 
{ 
    return reflect_diag (reflect_horiz (value)); 
} 

En el código anterior, la función reflect_diag() aún requiere muchos cambios. Sospecho que es posible implementar esta función con menos cambios, pero aún no he encontrado la manera de hacerlo.