C MSB到LSB解釋

Question

有人可以向我解釋一下這種算法在32位系統上如何將MSB轉換爲LSB或LSB爲MSB？

unsigned char b = x; 
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

我看過十六進制值以LU結尾，或者只是U代碼之前，它們是什麼意思？

謝謝！

Answer 1

假定char有8位，所以unsigned char b = x取x的低8位。

帶有0x22110的掩碼提取第4,8,13和17位（從最低有效位的0開始編號）。所以，乘以0x0802，我們只關心它在這些位上的位置。在0x802中，第1位和第11位開啓，因此該乘法將第1位到第8位中的b的八位副本與第11位至第18位中的另一副本相複製。沒有重疊，因此不會添加位在更一般的乘法中重疊。

從這個產品，我們把這些位：

• 位4，它是位的b 3。 （從位1開始複製的位4，所以位4-1 = 3的b）。
• 位8，它是b的位7。 （8-1 = 7）
• 位13，它是b的位2。 （13-11 = 2.）
• 位17，它是位於b的第6位。 （17-11 = 6）

類似地，掩模通過0x88440提取比特6，10，15，和19。乘以0x8020地方b以比特5至12的副本，並在比特另一個副本從這個產品，我們採取這些位：

• 位6，這是b的位1。
• 位10，它是位於b的第5位。
• 位15，位爲0的b。
• 位19，它是b的第4位。

然後我們OR那些一起，產生：

• 位4，這是b位3。
• 位6，它是b的位1。
• 位8，它是位於b的第7位。
• 位10，它是位於b的第5位。
• 位13，它是b的位2。
• 位15，位爲0的b。
• 位17，位於b的第6位。
• 位19，它是b的第4位。

致電此結果t。

我們將乘以0x10101，右移16，並分配給b。該分配轉換爲unsigned char，因此只保留低8位。移位後的低8位是位移前的24位至31位。所以我們只關心產品中的24位到31位。

乘法器0x10101的位爲0,8和16組。因此，結果中的位24是t中的位24,16和8的和，加上來自別處的任何進位。但是，沒有進位：請注意，t中的任何設置位都不相等，因爲乘法器中的位是。因此，他們中的任何一個都不能直接貢獻於產品中的相同位。產品中的每一位都是t中最多一位的結果。我們只需要弄清楚哪個位是。

位24必須來自位於t的位8,16或24。只有第8位可以設置，它是從b的第7位。推斷所有的位是這樣的：

• 位24是比特8 t，這是位7 b。
• 位25是位於t的位17，位於b的位6。
• 位26是位於t的位10，位於b的位5。
• 位27是位於t的位19，位於b的位4。
• 位28是位於t的位4，位於b的位3。
• 位29是位於t的位13，位於b的位2。
• 位30是位於t的位6，位於b的位1。
• 位31是位於t的位15，位於b的位0。

因此，位24至31中的產品是比特7到0在b，所以最後產生的八位是位7到0的b。

Answer 2

要回答你的第二個問題，u表示將十六進制常量作爲無符號（如果需要將其擴展爲更長的寬度），並且l意味着將其視爲long。

我正在處理您的第一個問題。

Answer 3

當你將它看作乘法和十六進制時，很難想象這個算法正在做什麼。當您將其轉換爲二進制數並用相當數量的移位操作替換乘法時，它變得更加清晰。本質上，它所做的是通過移位和掩蓋部分字節來擴展字節的部分內容，然後實現一個並行的半加器來重建零件，這恰好與它們開始的位置相反。

例如，對於b

b * 0x0802 = b << 11 | b << 1 

插件在某些值（二進制），並按照沿。

Answer 4

查看b爲8位值abcdefgh其中每個字母爲單個位（0或1），其中a爲最高位，h爲最低位。然後看看每個操作做那些位：

b * 0x0802LU    = 00000abcdefgh00abcdefgh0 
b * 0x0802LU & 0x22110LU = 000000b000f0000a000e0000 
b * 0x8020LU    = 0abcdefgh00abcdefgh00000 
b * 0x8020LU & 0x88440LU = 0000d000h0000c000g000000 
((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) 
         = 0000d0b0h0f00c0a0g0e0000 

所以在這一點上，它打亂了位，並蔓延出來。

(....) * 0x10101LU  =     d0b0h0f00c0a0g0e0000 
         +   d0b0h0f00c0a0g0e000000000000 
         + d0b0h0f00c0a0g0e00000000000000000000 
         = d0b0f0f0dcbahgfedcbahgfe0c0a0g0e0000 
(...) * 0x10101LU >> 16 = d0b0f0f0dcbahgfedcba 
b      = hgfedcba 

乘法相當於shift/add/add（常量中設置了3位），它將它們應該結束的位排成一行。然後最後的移位和減少到8位給你最後的位反轉結果。