Как сделать 64-битное умножение на 16-битной машине?

Question

У меня встроенный 16-битный процессор. На этой машине ints имеет ширину 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 (это книга и веб-сайт). Они имеют C-реализации Knuth's signed multiword multiplication и unsigned multiword multiplication от The Art of Computer Programming Vol.2.