Làm cách nào (i << 48) | ((i & 0xffff0000L) << 16) | ((i > >> 16) & 0xffff0000L) | (i >>> 48) làm việc?

Question

Đây là việc thực hiện ngược lại tại Long:

public static long reverse(long i) { 
     // HD, Figure 7-1 
    i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;//1 
    i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;//2 
    i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;//3 
    i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;//4 
    i = (i << 48) | ((i & 0xffff0000L) << 16) | 
     ((i >>> 16) & 0xffff0000L) | (i >>> 48);//5 
    return i; 
} 

tôi có thể hiểu dòng 1,2,3,4, nhưng không phải 5! Làm thế nào nó hoạt động?

Tôi nhóm 64 bit thành 8 nhóm, đó là 1 là 8 bit đầu tiên, 2 là 8 bit thứ hai, v.v.

Sau đó, sau khi dòng 4, trình tự như 4,3,2,1,8,7,6,5

và tôi nghĩ rằng dòng 5 làm việc như dưới đây trước khi phẫu thuật |:

6,5,0,0,0,0,0,0-->(i << 48) 
8,7,0,0,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,2,1-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Nhưng, tôi không biết nơi liều nó sai hay nó là sai! Suy nghĩ về nó gần như cả một ngày!

Ai đó có thể giúp tôi !! Cảm ơn.

oh, tôi đã phạm sai lầm như thế này:

6,5,0,0,0,0,0,0-->(i << 48) 
0,0,8,7,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,2,1,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,4,3-->(i >>> 48) 

nhưng tôi alse nghĩ rằng đó là sai! tôi nghĩ rằng trình tự đúng là 8,7,6,5,4,3,2,1

tôi rất xin lỗi vì tôi đã phạm một số sai lầm! nó hoạt động đúng như sau:

sau dòng 4, mô hình bên phải là: 2,1,4,3,6,5,8,7

8,7,0,0,0,0,0,0-->(i << 48) 
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Answer 1

Line 1 giao dịch hoán đổi bit duy nhất liền kề theo cặp (0 <-> 1; 2 <-> 3, vv). Các dòng 2-4 hoán đổi các chuỗi lân cận gồm hai bit, 4 bit và 8 bit. Tại thời điểm đó, giá trị ban đầu đã được chuyển đổi thành bốn khối 16 bit với mỗi khối ngược lại với những gì nó đã có lúc bắt đầu. Dòng 5 sau đó sắp xếp lại 4 khối. Về cơ bản, dòng 5 kết hợp hai bước thành một: hoán đổi hai cặp khối 16 bit và hoán đổi một cặp khối 32 bit. Logic là:

• (i << 48) di chuyển các khối 16-bit ngoài cùng bên phải đến vị trí bên trái, để lại tất cả các bit khác zero
• ((i & 0xffff0000L) << 16) di chuyển các khối thứ hai từ bên phải là khối thứ hai từ bên trái (tất cả khác bit zero)
• ((i >>> 16) & 0xffff0000L) di chuyển các khối thứ hai từ trái sang được khối thứ hai từ bên phải (tất cả các bit khác zero)
• (i >>> 48) di chuyển các khối tận cùng bên trái đến đúng vị trí (tất cả các bit khác zero)

Sau đó, bốn giá trị này là | được kết hợp với nhau để tạo ra sự đảo ngược cuối cùng. Nếu nó đã được thực hiện trong hai bước, nó sẽ là hai phát biểu trông giống như bốn câu lệnh đầu tiên, nhưng với các mẫu mặt nạ khác nhau.

Tôi nghĩ rằng sau dòng 4, mẫu là 2,1,4,3,6,5,8,7, không phải là 4,3,2,1,8,7,6,5 như bạn đã giả định.Bốn phần của dòng 5 sau đó là:

8,7,0,0,0,0,0,0-->(i << 48) 
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Answer 2

Nỗ lực của bạn không hoàn toàn chính xác. Dưới đây là phiên bản chỉnh:

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
8,7,0,0,0,0,0,0 --> (i << 48) 
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1 --> (i >>> 48) 

Dưới đây là hai bước trung gian chia tay:

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
0,0,0,0,6,5,0,0 --> (i & 0xffff0000L) 
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16) 

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
0,0,2,1,4,3,6,5 --> (i >>> 16) 
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L) 

---

Mặc dù tôi hơi ngạc nhiên tại sao nó không được thực hiện như sau:

i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; // 1 
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; // 2 
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; // 3 
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; // 4 
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL; // 5 
i = (i & 0x00000000ffffffffL) << 32 | (i >>> 32) & 0x00000000ffffffffL; // 6 

Nó giữ mẫu phù hợp. Và tôi nghĩ nó cũng làm giảm # hoạt động.

EDIT: Tôi hiểu lý do tại sao nó được triển khai theo đúng cách. Phiên bản trong câu hỏi chỉ sử dụng các hoạt động cho hai lần đảo ngược cuối cùng. Phiên bản ở đây (dòng 5 và 6) cần 10 hoạt động.

Hừ ... nói về vi-tối ưu hóa đến cùng cực ...

---

EDIT 2: Tại sao tôi không nghĩ về điều này? Tại sao không sử dụng số java.lang.Long?

i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; // 1 
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; // 2 
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; // 3 
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; // 4 
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL; // 5 
i = (i << 32) | (i >>> 32)            // 6