División que no cruza sobre bytes

Question

Estoy tratando de hacer la división en un uint128_t que se compone de 2 uint64_t s. Curiosamente, la función funciona para uint64_t s con solo el valor inferior establecido y el valor superior = 0. No entiendo por qué.

Aquí está el código para la división y poco cambio

class uint128_t{ 
    private: 
     uint64_t UPPER, LOWER; 
    public: 
     // lots of stuff 

    uint128_t operator<<(int shift){ 
     uint128_t out; 
     if (shift >= 128) 
      out = uint128_t(0, 0); 
     else if ((128 > shift) && (shift >= 64)) 
      out = uint128_t(LOWER << (64 - shift), 0); 
     else if (shift < 64) 
      out = uint128_t((UPPER << shift) + (LOWER >> (64 - shift)), LOWER << shift); 
     return out; 
    } 

    uint128_t operator<<=(int shift){ 
     *this = *this << shift; 
     return *this; 
    } 

    uint128_t operator/(uint128_t rhs){ 
      // copy of numerator = copyn 
      uint128_t copyn(*this), quotient = 0;// constructor: uint128_t(T), uint128_t(S, T), uint128_t(uint128_t), etc 
      while (copyn >= rhs){ 
       // copy of denomiator = copyd 
       // temp is the current quotient bit being worked with 
       uint128_t copyd(rhs), temp(1); 
       // shift the divosr to the highest bit 
       while (copyn > (copyd << 1)){ 
        copyd <<= 1; 
        temp <<= 1; 
       } 
       copyn -= copyd; 
       quotient += temp; 
      } 
      return quotient; 
     } 
// more stuff 
}; 

favor ignorar mi indiferencia evidente para la gestión de la memoria.

Answer 1

out = uint128_t(LOWER << (64 - shift), 0); es incorrecto - debería ser shift - 64 en su lugar.

Como nota de estilo, ALL_CAPITALS por lo general se reservan solo para las constantes. Las variables y los miembros deben usarse principalmente en minúsculas.

Answer 2

probar esto:

// some bit operations stuff 
const unsigned char de_brujin_bit_map_64 [] = 
{ 
    0,1,2,7,3,13,8,19,4,25,14,28,9,34,20,40,5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57, 
    63,6,12,18,24,27,33,39,16,37,45,47,30,53,49,56,62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58 
}; 
inline uint8_t trailing_zero_count(uint64_t x) { return x?de_brujin_bit_map_64[(lower_bit(x)*0x0218A392CD3D5DBFL) >> 58]:64; } 
inline uint8_t leading_zero_count(uint64_t x) { return x?(63-de_brujin_bit_map_64[(upper_bit(x)*0x0218A392CD3D5DBFL) >> 58]):64; } 
inline uint64_t lower_bit(uint64_t x) { return x & -(int64_t&)x; } 
inline uint64_t upper_bit(uint64_t x) 
{ 
    if(!x) return 0; 
    x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; 
    return (x >> 1) + 1; 
} 
inline uint128_t upper_bit(const uint128_t x) 
{ 
    if(x.upper()) return uint128_t(upper_bit(x.upper()), 0); 
    else return uint128_t(0, upper_bit(x.lower())); 
} 
inline uint128_t lower_bit(const uint128_t x) 
{ 
    if(x.lower()) return uint128_t(0, lower_bit(x.lower())); 
    else return uint128_t(lower_bit(x.upper()), 0); 
} 
inline uint8_t trailing_zero_count(const uint128_t& x) { return x.lower()?trailing_zero_count(x.lower()):(64+trailing_zero_count(x.upper())); } 
inline uint8_t leading_zero_count(const uint128_t& x) { return x.upper()?leading_zero_count(x.upper()):(64+leading_zero_count(x.lower())); } 

// division operator 
uint128_t uint128_t::operator/(const uint128_t& rhs) const 
{ 
    if(rhs == 0) return uint128_t(0); // !!!! zero division 
    if(rhs == rhs) return uint128_t(1); 
    if(rhs > *this) return uint128_t(0); 
    if(rhs == 1) return *this; 
    if(!upper_ && !rhs.upper_) return uint128_t(0, lower_/rhs.lower_); 
    if(lower_bit(rhs) == rhs) return *this >> trailing_zero_count(rhs); 
    uint128_t result; 
    uint128_t bit_mask = upper_bit(); 
    uint128_t denom = 1; 
    do 
    { 
     bit_mask >>= 1; 
     denom <<= 1; 
     if(*this & bit_mask) denom |= 1; 
     result <<= 1; 
     if(denom >= rhs) { denom -= rhs; result |= 1; } 
    } 
    while (bit_mask.lower_ != 1); 
    return result; 
} 

Answer 3

todos modos, esta versión es un poco más rápido :)

asegurar, 4000 iteraciones contra 127:

uint128_t divident = uint128_t(0xffffffffffffffffULL, 0xffffffffffffffffULL); 
uint128_t divisor = 10; 
{ 
    uint32_t iter_count = 0; 
    uint128_t copyn(divident), quotient = 0; 
    while (copyn >= divisor) 
    { 
     ++iter_count; 
     uint128_t copyd(divisor), temp(1); 
     while ((copyn >> 1) > copyd) { ++iter_count; copyd <<= 1; temp <<= 1; } 
     copyn -= copyd; 
     quotient += temp; 
    } 
    std::cout << "iterations: " << std::dec << iter_count << std::endl; 
} 
{ 
    uint32_t iter_count = 0; 
    uint128_t bit_pos = dtl::bits::upper_bit(divident); 
    uint128_t tmp = 1, quotient = 0; 
    do 
    { 
     ++iter_count; 
     bit_pos >>= 1; 
     tmp <<= 1; 
     if(divident & bit_pos) tmp |= 1; 
     quotient <<= 1; 
     if(tmp >= divisor) { tmp -= divisor; quotient |= 1; } 
    } 
    while (bit_pos != 1); 
    std::cout << "iterations: " << std::dec << iter_count << std::endl; 
}