Xoay bitmap 90 độ

Question

Tôi có một số nguyên 64 bit, mà tôi cần xoay 90 độ trong khu vực 8 x 8 (tốt nhất là với thao tác bit thẳng). Tôi không thể tìm ra bất kỳ thuật toán tiện dụng nào cho điều đó. Ví dụ, điều này:

// 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 

sau khi xoay trở này:

// 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 

Tôi tự hỏi nếu có bất kỳ giải pháp mà không cần phải sử dụng bất kỳ bảng băm tính trước (s)?

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

Nếu bạn nhìn vào mảng này dưới dạng mảng 2 chiều thì bạn có giải pháp không? Chỉ cần tạo các hàng các cột mới. Hàng đầu tiên là cột cuối cùng, thứ 2 là cột trước và sau cùng.

Trực quan ít nhất, có vẻ như giải pháp của bạn.

Answer 3

lẽ một cái gì đó như thế

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

Nếu không sử dụng bất kỳ bảng nhìn lên, tôi không thể nhìn thấy tốt hơn nhiều so với điều trị mỗi bit riêng lẻ:

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

Answer 5

Nếu một vòng lặp if-powered là chấp nhận được, công thức cho các bit đủ đơn giản:

8>>Column - Row - 1 

Cột và hàng được đánh chỉ mục 0.

này cung cấp cho bạn bản đồ này:

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

Nếu bạn đang đi để làm điều này nhanh chóng, bạn không nên phản đối việc tra cứu bảng.

Tôi muốn chia số nguyên 64 bit thành các khối N bit và tra tìm các khối bit N trong bảng giá trị chuyển vị trí đã chọn vị trí. Nếu bạn chọn N = 1, bạn cần 64 tra cứu trong các bảng của hai khe, tương đối chậm. Nếu bạn chọn N = 64, bạn cần một bảng và một tra cứu nhưng bảng rất lớn: -}

N = 8 có vẻ như là một sự thỏa hiệp tốt. Bạn sẽ cần 8 bảng gồm 256 mục. Mã phải trông giống như sau:

// 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]; 

Mỗi bảng chứa các giá trị precomputed "trải rộng" các bit kề nhau trong đầu vào qua kết quả chuyển bit 64 bit. Lý tưởng nhất là bạn tính toán giá trị này ngoại tuyến và chỉ cần khởi tạo các mục nhập bảng.

Nếu bạn không quan tâm đến tốc độ, khi đó các mảng tiêu chuẩn chuyển đổi sẽ hoạt động; chỉ cần chỉ số 64 bit như thể nó là một mảng bit.

Tôi có một sự nghi ngờ lén lút rằng người ta có thể tính toán chuyển vị bằng cách sử dụng hacks kiểu twiddling bit.

Answer 7

Mở rộng trên bình luận của tôi để trả lời Ira, bạn có thể sử dụng:

#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; 
} 

này phụ thuộc vào 'unsigned long' được 64 bit, tất nhiên, và hiện xoay giả các bit là trong row- thứ tự chính với msb là phía trên bên phải, có vẻ như là trường hợp trong câu hỏi này ....

Answer 8

Điều này khá dễ dàng bằng cách sử dụng SIM32 IA32, có một opcode tiện dụng để trích xuất mọi bit thứ tám từ một giá trị 64 bit (điều này được viết bằng 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 
} 

Nó quay dữ liệu ba lần (-270 độ) từ năm 90 là một chút phức tạp hơn (cần thêm một chút suy nghĩ)

Answer 9

Có một cách hiệu quả để thực hiện sự đảo ngược bit, sử dụng O (log n) sự thay đổi hoạt động. Nếu bạn giải thích UINT 64 bit dưới dạng mảng 8 x 8 bit, thì đảo ngược bit tương ứng với xoay 180 độ.

Một nửa trong số những thay đổi này có hiệu quả thực hiện phản xạ ngang; nửa còn lại thực hiện một phản xạ thẳng đứng. Để có được phép quay 90 và 270 độ, một sự phản xạ trực giao (tức là dọc hoặc ngang) có thể được kết hợp với một phản xạ chéo, nhưng sau này vẫn là một chút khó xử.

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)); 
} 

Trong mã trên, hàm reflect_diag() vẫn yêu cầu nhiều ca. Tôi nghi ngờ rằng có thể thực hiện chức năng này với ít thay đổi hơn, nhưng tôi vẫn chưa tìm được cách để làm điều đó.