如何在16位機器上執行64位乘法？

Question

我有一個嵌入式的16位CPU。在這臺機器上，整數是16位寬，它支持32位寬的長整數。我需要做一些乘法運算，這些乘法運算需要存儲在64位中（例如，將一個32位數乘以16位數）。我怎麼能用給定的約束來做到這一點？我沒有一個數學圖書館來做到這一點。

Answer 1

C中的建議，請注意，這可能代碼會更容易與內聯彙編實現在C攜帶檢測似乎並不那麼容易

// Change the typedefs to what your compiler expects 
typedef unsigned __int16  uint16 ; 
typedef unsigned __int32  uint32 ; 

// The 64bit int 
typedef struct uint64__ 
{ 
    uint32  lower ; 
    uint32  upper ; 
} uint64; 

typedef int boolt; 

typedef struct addresult32__ 
{ 
    uint32  result ; 
    boolt  carry ; 
} addresult32; 

// Adds with carry. There doesn't seem to be 
// a real good way to do this is in C so I 
// cheated here. Typically in assembler one 
// would detect the carry after the add operation 
addresult32 add32(uint32 left, uint32 right) 
{ 
    unsigned __int64 res; 
    addresult32 result ; 

    res = left; 
    res += right; 


    result.result = res & 0xFFFFFFFF; 
    result.carry = (res - result.result) != 0; 

    return result; 
} 

// Multiplies two 32bit ints 
uint64 multiply32(uint32 left, uint32 right) 
{ 
    uint32 lleft, uleft, lright, uright, a, b, c, d; 
    addresult32 sr1, sr2; 
    uint64 result; 

    // Make 16 bit integers but keep them in 32 bit integer 
    // to retain the higher bits 

    lleft = left   & 0xFFFF; 
    lright = right   & 0xFFFF; 
    uleft = (left >> 16) ; 
    uright = (right >> 16) ; 

    a = lleft * lright; 
    b = lleft * uright; 
    c = uleft * lright; 
    d = uleft * uright; 

    sr1 = add32(a, (b << 16)); 
    sr2 = add32(sr1.result, (c << 16)); 

    result.lower = sr2.result; 
    result.upper = d + (b >> 16) + (c >> 16); 
    if (sr1.carry) 
    { 
     ++result.upper; 
    } 

    if (sr2.carry) 
    { 
     ++result.upper; 
    } 

    return result; 
} 

Answer 2

你可能想看看Hacker's Delight（這是一個書和網站）。它們具有來自The Art of Computer Programming Vol.2的Knuth的signed multiword multiplication和unsigned multiword multiplication的C實現。