Computing Il bit alti di una moltiplicazione in C#

Question

Sto cercando di convertire una libreria open source da NET 4.0 a 3.5 e non posso facilmente convertire il codice seguente moltiplicazione lungo:

/// <summary> 
    /// Calculate the most significant 64 bits of the 128-bit 
     product x * y, where x and y are 64-bit integers. 
    /// </summary> 
    /// <returns>Returns the most significant 64 bits of the product x * y.</returns> 
    public static long mul64hi(long x, long y) 
    { 
#if !NET35 
     BigInteger product = BigInteger.Multiply(x, y); 
     product = product >> 64; 
     long l = (long)product; 
     return l; 
#else 
     throw new NotSupportedException(); //TODO! 
#endif 
    } 

Come si può vedere la l'autore non ha trovato un modo per farlo. BigInteger non esiste in .NET 3.5.

Come faccio a calcolare i bit di 64 bit di una moltiplicazione 64 * 64 su .NET 3.5?

Answer 1

È possibile costruire un moltiplicatore 2N bit da più moltiplicatori N-bit.

public static ulong mul64hi(ulong x, ulong y) 
{ 
    ulong accum = ((ulong)(uint)x) * ((ulong)(uint)y); 
    accum >>= 32; 
    accum += (x >> 32) * ((ulong)(uint)y); 
    accum += (y >> 32) * ((ulong)(uint)x); 
    accum >>= 32; 
    accum += (x >> 32) * (y >> 32); 
    return accum; 
} 

È solo una lunga moltiplicazione scuola elementare, davvero.

Con i numeri con segno, è un po 'più difficile, perché se i risultati intermedi portano nel segno bit tutto va storto. Un long non può tenere il risultato di una a 32 bit a 32 bit moltiplicare, senza che questo accada, quindi dobbiamo farlo in blocchi più piccoli:

public static long mul64hi(long x, long y) 
{ 
    const long thirtybitmask = 0x3FFFFFFF; 
    const long fourbitmask = 0x0F; 
    long accum = (x & thirtybitmask) * (y & thirtybitmask); 
    accum >>= 30; 
    accum += ((x >> 30) & thirtybitmask) * (y & thirtybitmask); 
    accum += ((y >> 30) & thirtybitmask) * (x & thirtybitmask); 
    accum >>= 30; 
    accum += ((x >> 30) & thirtybitmask) * ((y >> 30) & thirtybitmask); 
    accum += (x >> 60) * (y & fourbitmask); 
    accum += (y >> 60) * (x & fourbitmask); 
    accum >>= 4; 
    accum += (x >> 60) * (y >> 4); 
    accum += (y >> 60) * (x >> 4); 
    return accum; 
} 

Ispirato dal commento di Harold circa Delight di Hacker, la versione firmata può essere fatto altrettanto efficiente come l'altra, con attenzione controllando se i risultati intermedi sono o non sono firmati:

public static long mul64hi(long x, long y) 
{ 
    ulong u = ((ulong)(uint)x) * ((ulong)(uint)y); 
    long s = u >> 32; 
    s += (x >> 32) * ((long)(uint)y); 
    s += (y >> 32) * ((long)(uint)x); 
    s >>= 32; 
    s += (x >> 32) * (y >> 32); 
    return s; 
}