__div64_32函数，64位进制转换，取余得商，烧脑2小时

烧脑挑战，64位进制转换，取余得商，就这么个函数我烧脑了2小时，感觉我的数学敏感性还是不行啊，要搞算法还是有些难的感觉。如果你不看我注释多久能看理解透呢？

//64位进制转换，取余得商

//uint64_t *n为原本数值的指针

//uint32_t base为进制的基数

//返回rem，要返回的余数

//返回*n，除后的商

uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)

{

  uint64_t rem = *n;

  uint64_t b = base;

  uint64_t res, d = 1;

  uint32_t high = rem >> 32;

  res = 0;

  if (high >= base) {

    high /= base;

    res = (uint64_t) high << 32;

    rem -= (uint64_t) (high*base) << 32;

  }

  while ((int64_t)b > 0 && b < rem) {

    b = b+b;  

    d = d+d;  

  }

  do {

    if (rem >= b) { 

      rem -= b;

      res += d;

    }

    b >>= 1;

    d >>= 1; 

  } while (d);

  *n = res;

  return rem;

}

接下来贴上注释后的代码

//64位进制转换，取余得商

//先去除高位能被整除的一部分，来求余数

//剩余得余数每次尽可能减最大的base倍数，就能快速得到余数

//商可以化为二进制，那么每个位就是2的n次方

//每次减最大的2的n次方*base，就是尽可能减最大数

//只要是能减那么就说明商对应二进制位为1

uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)

{

  uint64_t rem = *n;

  uint64_t b = base;

  uint64_t res, d = 1;

  uint32_t high = rem >> 32;

  /* Reduce the thing a bit first */

  //先去除高位能被整除的一部分，来求余数

  //高位先除一次基数得res，rem等于高位剩下的余数+低位

  res = 0;

  if (high >= base) {

    high /= base;

    res = (uint64_t) high << 32;

    rem -= (uint64_t) (high*base) << 32;

  }

  //算出最大打能减的base*2的n次方

  while ((int64_t)b > 0 && b < rem) {

    b = b+b;   //=base*d，d=2的d二进制位数次方，例如b=0x1000000

    d = d+d;   //用于d >>= 1，相当于计次数

  }

  //取余得商

  do {

    if (rem >= b) { //不成立，相当于商的该二进制位为0

      rem -= b;   //减去商最高位最大base倍数

      res += d;   //加上当下进制的位值

    }

    b >>= 1; //=base*d，相当于跟着d的一起移位，能减的最大base数

    d >>= 1; //相当于除得的商的二进制最高位值

  } while (d);

  *n = res;

  return rem;

}