在32位机器上实现64位数的除法
概述
在32位机器上不能直接进行64位数据的除法，比如a或b是64位的数据的时候，要计算a/b，不能直接data = a/b;这样的计算，编译器会报错，缺少相关的指令。这就需要我们单独去实现64位数据的除法函数。
在32位机器上实现64位数据除法的方式有很多，主体思想就是分解成32位的数据去进行除法或者进行移位计算，一个数往右移一位等于该数除以2，往右移两位等于该数除以4，也就是移位n次等于除去2^(n-1)。
linux内核中32位机的64位除法函数实现
linux内核中实现了div64_u64_rem()和div64_u64()函数用于计算64位数据的除法运算。两个函数的区别是div64_u64_rem()函数会计算出余数，div64_u64()函数之会返回商。
下面一起看一下div64_u64_rem()函数的实现。
/*** div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder* @dividend: 64bit dividend 被除数* @divisor: 64bit divisor 除数* @remainder: 64bit remainder 余数** This implementation is a comparable to algorithm used by div64_u64.* But this operation, which includes math for calculating the remainder,* is kept distinct to avoid slowing down the div64_u64 operation on 32bit* systems.*/u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
{/* 除数右移32位，用于后续判断除数是否大于2^32 */u32 high = divisor >> 32;u64 quot;if (high == 0) {/* 假如除数小于2^32，直接使用64位数除以32位数的函数来计算 */u32 rem32;quot = div_u64_rem(dividend, divisor, &rem32); *remainder = rem32;} else {/* 假如除数大于等于2^32的情况 *//* 先计算除数除以2^(32-1)之后得到的商的最高有效位，假如除数是4*(2^32),那么这里的n就等于2(4=b`100) */int n = fls(high);/* 利用 a/b=2a/2b的定理，先将被除数除以2^(n-1),然后除数也除以2^(n-1),最后再调用64位数除以32位数的函数来计算，因为除数除以2^(n-1)就能保证得到小于2^32的数 */quot = div_u64(dividend >> n, divisor >> n);if (quot != 0)quot--;/* 得到商之后，用乘法来计算余数 */*remainder = dividend - quot * divisor;if (*remainder >= divisor) {quot++;*remainder -= divisor;}}return quot;
}
从过上面的分析可以看出，实现这个函数的依赖一个关键的函数div_u64_rem();这个函数允许被除数是64位的数据，除数是32位的数据，对于32位机器来说，(uint64_t)a/(uint32_t)b,这样的运算也是不被允许的，我们再继续看看div_u64_rem()是怎么实现的。
static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
{*remainder = do_div(dividend, divisor);return dividend;
}
可以看到div_u64_rem()在32位机器上的实现是一个内联函数，并且是通过调用do_div()函数来实现的，我们再看看do_div()是如何实现的。
/* The unnecessary pointer compare is there* to check for type safety (n must be 64bit)*/
# define do_div(n,base) ({ \uint32_t __base = (base); \uint32_t __rem; \(void)(((typeof((n)) *)0) == ((uint64_t *)0)); \if (__builtin_constant_p(__base) && \/* 判断除数是不是2的幂次方 */is_power_of_2(__base)) { \/* 通过乘法算余数 */__rem = (n) & (__base - 1); \/* 被除数右移位来计算商 */(n) >>= ilog2(__base); \} else if (__builtin_constant_p(__base)