无符号整型除法的快速算法

众所周知，即使是现在最新的CPU整数除法指令依然是相当慢的，在某些情况下耗时和几十次位运算差不多。而整数乘法指令则相当快，耗时和两三次位运算相当。

各种主流编译器很早就明白了这个道理，它们会对除数为常量的整数除法进行优化，优化成整数乘法和移位运算。

下面我们来看一些编译器优化的例子。

可以看到编译器把x/5优化成了(unsigned int)((x*3435973837ULL)>>34)。那么问题来了，编译器都干了些什么，乘以3435973837和右移34是怎么算出来的？

下面我只说这2个数怎么算出来的，具体数学原理可以在文章末尾的链接参考某大佬的文章。

在32位无符号整型范围内，将x/y变成(x*a)>>b等价形式，那么：

当然，这么直接有缺点的，超出32位范围了，如何继续优化参考大佬文章吧！

参考：http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html