乘以兩個32位數字......這個代碼有什麼問題

我想乘兩個32位數字a和b應該給出一個64位結果。與a和b的無符號32位整數，我提出了這樣的：乘以兩個32位數字......這個代碼有什麼問題

r = a * b 

r = ((ah << 16) + al) * ((bh << 16) + bl) 
    = ((ah * 2^16) + al) * ((bh * 2^16) + bl) 
    = (ah * 2^16) * (bh * 2^16) + (ah * 2^16) * bl + al * (bh * 2^16) + al * bl 
    = (ah * bh * 2^32) + (ah * bl * 2^16) + (al * bh * 2^16) + (al * bl) 
    = ((ah * bh) << 32) + ((ah * bl) << 16) + ((al * bh) << 16) + (al * bl) 
    = ((ah * bh) << 32) + ((ah * bl + al * bh) << 16) + (al * bl)

我然後翻譯到c如下

static void _mul64(unsigned int a, unsigned int b, unsigned int *hi, unsigned int *lo) { 
    unsigned int ah = (a >> 16), al = a & 0xffff, 
        bh = (b >> 16), bl = b & 0xffff, 
        rh = (ah * bh), rl = (al * bl), 

        rm1 = ah * bl,   rm2 = al * bh, 
        rm1h = rm1 >> 16,  rm2h = rm2 >> 16, 
        rm1l = rm1 & 0xffff, rm2l = rm2 & 0xffff, 
        rmh = rm1h + rm2h,  rml = rm1l + rm2l; 

    rl = rl + (rml << 16); 
    rh = rh + rmh; 
    if(rml & 0xffff0000) 
     rh = rh + 1; 
    *lo = rl; 
    *hi = rh; 
}

然而，當我運行該小測試其乘以= 0xFFFFFFFF與b = 0xFFFFFFFF並應產生0xFFFFFFFE00000001，我得到0xFFFFFFFD00000001而不是。我做錯了嗎？

int main(int argc, char **argv) { 
    unsigned int a, b, rl, rh; 
    unsigned long long r; 
    unsigned long long r1, r2, r3; 

    a = 0xffffffff; 
    b = 0xffffffff; 
    mul64(a, b, &rh, &rl); 
    r1 = ((unsigned long long) rh << 32) + rl; 
    r2 = (unsigned long long) a * b; 

    _mul64(a, b, &rh, &rl); 
    r3 = ((unsigned long long) rh << 32) + rl; 
    printf("a = 0x%08x, b = 0x%08x\n", (unsigned) a, (unsigned) b); 
    printf("_mul64: 0x%16llx\n", (unsigned long long) r3); 
    printf("a * b = 0x%16llx\n", (unsigned long long) r2); 
    return 0; 
}

來源

2012-07-11 PaulK

您應該打印出所有中間值的值，以確定出錯的地方。 – 2012-07-11 17:44:52

@OliCharlesworth說過，調試是掌握的重要技能。 – TheZ 2012-07-11 17:45:29

你有沒有想過當'rl = rl +（rml << 16）;會溢出？你是否在所有適當的地方檢測/補償進位？ – 2012-07-11 17:51:02

你在這裏加入16位數量

rm1l = rm1 & 0xffff, rm2l = rm2 & 0xffff, 
rmh = rm1h + rm2h,  rml = rm1l + rm2l;

，並添加rml移16位留給rl，

rl = rl + (rml << 16);

，當兩個16位數量的總和成爲一個17位數的丟棄進位。

此外，後者的總和可能超過32位範圍，在這種情況下，您將失去另一個進位位。

來源

2012-07-11 19:19:37

啊你是對的！它現在有效，謝謝！ :) – PaulK 2012-07-11 20:02:12

隨着初始化程序中的所有算術操作，調試將變得困難。將所有這些計算移出初始化程序，然後在禁用優化的情況下編譯您的代碼。在調試器中逐步完成，並確保每個步驟都生成您期望生成的值。當您按照您手動解決的算法執行代碼時，應該很容易發現代碼和算法偏離的地方。

來源

2012-07-11 17:52:36 bta

這是一個很好的建議謝謝 – PaulK 2012-07-11 20:02:39

乘以兩個32位數字......這個代碼有什麼問題

回答

相關問題