Come posso implementare un'operazione modulo su unsigned con hardware limitato in C

Question

Ho una macchina che supporta solo operazioni a 32 bit, lunga non funziona su questa macchina. Ho una quantità a 64 bit rappresentata da due 32 int senza segno. La domanda è come posso eseguire un mod su quella quantità a 64 bit con un divisore a 32 bit.

r = a mod b

dove:

a è il valore e B a 64 bit è valore a 32 bit

pensavo che avrei potuto rappresentare la parte mod facendo: a = a1 * (2^32) + a2 (dove a1 è il bit superiore e a2 è il bit inferiore)

(a1 * (2^32) + a2) mod b = ((a1 * 2^32) mod b + a2 mod b) mod b

((a1 * 2^32) mod b + a2 mod b) mod b = (a1 mod b * 2^32 mod b + a2 mod b) mod b

ma il problema è che 2^32 mod b può talvolta essere uguale a 2^32 e quindi la moltiplicazione traboccherà. Ho cercato di convertire la moltiplicazione in un'aggiunta, ma ciò richiede anche che io usi 2^32 che se mod mi darà ancora 2^32 :) quindi non sono sicuro di come eseguire una mod unsigned di 64 bit valore con uno a 32 bit.

immagino una semplice soluzione a questo sarebbe quella di eseguire le seguenti operazioni:

1. a/b = c

2. a = a - piano (c) * b

3. eseguire 1 finché c è uguale a 0 e utilizzare a come risposta.

ma non sono sicuro come combinare questi due interi insieme per formare il valore di 64 bit

Giusto per essere completo qui sono alcuni link per divisione binaria e sottrazioni: http://www.exploringbinary.com/binary-division/

e una descrizione dell'algoritmo della divisione binaria: http://en.wikipedia.org/wiki/Division_algorithm

Answer 1

Works: testato con 1000M combinazioni casuali contro un 64 bit %.

Come divisione scuola elementare a/b (ma nella base 2), sottrarre b da a se possibile, quindi spostare, in loop 64 volte. Restituisce il resto.

#define MSBit 0x80000000L 
uint32_t mod32(uint32_t a1 /* MSHalf */, uint32_t a2 /* LSHalf */, uint32_t b) { 
    uint32_t a = 0; 
    for (int i = 31+32; i >= 0; i--) { 
    if (a & MSBit) { // Note 1 
     a <<= 1; 
     a -= b; 
    } else { 
     a <<= 1; 
    } 
    if (a1 & MSBit) a++; 
    a1 <<= 1; 
    if (a2 & MSBit) a1++; 
    a2 <<= 1; 
    if (a >= b) 
     a -= b; 
    } 
    return a; 
} 

Nota 1: Questa è la parte subdolo per fare un 33-bit sottrazione. Poiché il codice conosce n ha il set MSBit, 2*n sarà maggiore di , quindi n = 2*n - b. Ciò conta su wrap-around non firmato.

---

[Edit]

Ecco un generico modu() che funziona con qualsiasi dimensione dell'array a e qualunque formato intero senza segno.

#include <stdint.h> 
#include <limits.h> 

// Use any unpadded unsigned integer type 
#define UINT uint32_t 
#define BitSize (sizeof(UINT) * CHAR_BIT) 
#define MSBit ((UINT)1 << (BitSize - 1)) 

UINT modu(const UINT *aarray, size_t alen, UINT b) { 
    UINT r = 0; 
    while (alen-- > 0) { 
    UINT a = aarray[alen]; 
    for (int i = BitSize; i > 0; i--) { 
     UINT previous = r; 
     r <<= 1; 
     if (a & MSBit) { 
     r++; 
     } 
     a <<= 1; 
     if ((previous & MSBit) || (r >= b)) { 
     r -= b; 
     } 
    } 
    } 
    return r; 
} 

UINT modu2(UINT a1 /* MSHalf */, UINT a2 /* LSHalf */, UINT b) { 
    UINT a[] = { a2, a1 }; // Least significant at index 0 
    return modu(a, sizeof a/sizeof a[0], b); 
} 

Answer 2

Fai come farebbe una lunga divisione con carta e penna.

#include <stdio.h> 

unsigned int numh = 0x12345678; 
unsigned int numl = 0x456789AB; 
unsigned int denom = 0x17234591; 

int main() { 
    unsigned int numer, quotient, remain; 

    numer = numh >> 16; 
    quotient = numer/denom; 
    remain = numer - quotient * denom; 

    numer = (remain << 16) | (numh & 0xffff); 
    quotient = numer/denom; 
    remain = numer - quotient * denom; 

    numer = (remain << 16) | (numl >> 16); 
    quotient = numer/denom; 
    remain = numer - quotient * denom; 

    numer = (remain << 16) | (numl & 0xffff); 
    quotient = numer/denom; 
    remain = numer - quotient * denom; 

    printf("%X\n", remain); 
    return 0; 
}