Mã này hoạt động như thế nào để đảo ngược các bit theo số?

Question

unsigned reverse_bits(unsigned input) 
{ 
    //works on 32-bit machine 
    input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 
    input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2; 
    input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4; 
    input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8; 
    input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16; 

     return input; 
} 

cách thức hoạt động?

Answer 1

Giả sử tôi có một bàn tay của 8 thẻ:

7 8 9 10 J Q K A 

Làm thế nào chúng ta có thể đảo ngược họ? Một cách là để trao đổi cặp liền kề:

8 7 10 9 Q J A K 

nhóm Sau đó, trao đổi liền kề 2: trao đổi 8 7 và 10 9, vv:

10 9 8 7 A K Q J 

Cuối cùng, các nhóm trao đổi bốn, mà là một nửa kích thước của 8:

A K Q J 10 9 8 7 

Xong.

Bạn có thể thực hiện việc này theo các đơn đặt hàng khác nhau. Tại sao? Bởi vì các trao đổi là ổn định đối với nhau. Khi chúng ta trao đổi nửa trên của các thẻ với nửa dưới, ví dụ, các cặp vẫn giữ nguyên thứ tự. Hoặc khi chúng ta trao đổi các cặp, hai nửa vẫn giữ nguyên theo thứ tự.

Đây là những gì mã đang làm với các thao tác bit. Ví dụ để trao đổi cặp chúng ta có thể sử dụng mặt nạ 01010101 để chọn ra các bit chẵn, và 10101010 để chọn ra các bit lẻ, sử dụng phép toán AND hoạt động:

ABCDEFGH  ABCDEFGH 
& 01010101 & 10101010 
---------- ---------- 
= 0B0D0F0H  A0C0E0G0 

Hãy nhớ rằng, các quy tắc cho và là đưa ra một số bit value X, X & 1 = X và X & 0 = 0. 1 bit trong mặt nạ bảo toàn giá trị, và 0 bit trong mặt nạ tạo ra 0. Điều này được gọi là mặt nạ bởi vì nó trông giống như một mặt nạ được sử dụng trong phun -painting, vv Các 1 bit "bao gồm" những nơi bạn không muốn "vẽ" với số không.

Tiếp theo, kết quả bên trái được dịch chuyển sang trái một chút và kết quả phải dịch chuyển sang phải.Điều này mang lại sự hoán đổi:

B0D0F0H0  0A0C0E0G 

Cuối cùng, cả hai được kết hợp với logic HOẶC. Các quy tắc cho OR là X hoặc 0 là X. Hai phần từng có 0 nơi khác có khác không, và vì vậy các bit đơn giản là hợp nhất:

B0D0F0H0 
| 0A0C0E0G 
---------- 
= BADCFEHG 

Và bây giờ các cặp được hoán đổi.

Answer 2

Hãy để b[0], b[1], b[2], ..., b[31] là các bit của input bắt đầu từ bit ít quan trọng nhất. Sau đó b[1], b[0], b[3], b[2], ..., b[31], b[30] sẽ bit của

input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 

Về cơ bản, nó hoán đổi bit lân cận input. Tương tự, 4 dòng khác hoán đổi các cặp lân cận, nhóm 4, nhóm 8 và cuối cùng là 16 bit.

Answer 3

Nó có thể được hiểu bằng cảm ứng.

Bắt đầu với trường hợp cơ sở, một số hai chút

input = (input & 0x1) << 1 | (input & 0x2) >> 1; 

Bây giờ tiến tới một số bốn bit

input = (input & 0x5) << 1 | (input & 0xA) >> 1; // swap bits 
input = (input & 0x3) << 2 | (input & 0xc) >> 2; // swap bit pairs 

Tiến đến một số 8 bit

input = (input & 0x55) << 1 | (input & 0xAA) >> 1; // swap bits 
input = (input & 0x33) << 2 | (input & 0xCC) >> 2; // swap bit pairs 
input = (input & 0x0F) << 4 | (input & 0xF0) >> 4; // swap bit nibbles 

và do đó trên.

Answer 4

Mã đầu tiên hoán đổi các bit liền kề, sau đó các cặp bit lân cận, v.v., tăng gấp đôi kích thước của mỗi lần hoán đổi cho đến khi các nửa khối của số nguyên được hoán đổi ở cuối. Việc hoán đổi được thực hiện bằng cách che đi các bit được di chuyển với AND, dịch chuyển chúng và sau đó HOẶC kết quả lại với nhau.

Hoạt ảnh dưới đây hữu ích cho việc hình dung những gì đang diễn ra, hãy nhớ rằng trong khi kích thước trao đổi tăng liên tục, tất cả các hoán đổi ở mỗi kích thước diễn ra song song. nửa

Answer 5

unsigned reverse_bits(unsigned input) 
{ 
    //works on 32-bit machine 
    input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 
    input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2; 
    input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4; 
    input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8; 
    input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16; 
    printf("\nvalue = %x",input); 
    return input; 
} 

int _tmain() 
{ 
    // TODO: Please replace the sample code below with your own. 

    int value; 
    signed int res,bit; 
    signed int stPos, len; 
    value = 0x12345678; 

    reverse_bits(value); 
    printf("\nvalue = %x",value); 
    char buffer [33]; 
    itoa (value,buffer,2); 
    printf ("\nbinary: %s\n",buffer); 

    return 0; 
}