C++ 二进制转十进制优化 除法软件仿真算法及代码
本文所涉及的代码和技术，主要是用于cpu硬件设计中除法器算法的验证，可能与大多数软件工程师无关，但也正是因为非常底层，可以从更底层的角度去考虑除法运算优化。
本文重点展示在intel 九代之前的cpu上是如何实现除十算法的加速五倍性能的，另外，文章中还附带了其它两个高性能除法器的技术验证代码，算法的循环次数远小于bit数，即32bit下平均16次循环比较即可计算出正确的除法结果，即硬件下16+2个时钟周期即可实现32bit除法算法。
C/C++ 二进制转十进制是一种常见的功能，主要的优化点是：
一）除10算法的优化：
二进制转十进制的基础算法就是：不断的除十求余的计算过程，因此，除法的开销是主要开销之一。除十加速的主要原理是：可以将除法转换为＂乘法＋移位＂，而过去Intel CPU的除法比乘法慢很多倍，因此，将除法转换为乘法，就可以大幅度的提升除十算法的速度。
在Intel的老款CPU上，此项目的优化，大约可以提供５倍的性能提升．在目前新款Intel CPU(九代十代)上，此项优化已经毫无意义了，具体除法指令的性能提升，可以参考刘雨培的回答：
除法转乘法的相关的技术有很多类似的讨论，很多做硬件的工程师都知道，一个参考：
现在 Intel 终于不挤牙膏了，因此，很多除法的优化技术都过时了。正是因为这个原因，所以今天整个高性能除法库的代码才能够对外发布，才能够让大家了解到一些只在软件公司内部流传的先进除法算法的真实面貌，了解到比intel 旧款cpu硬件除十算法快5倍的除法算法是如何实现的。
除十优化的库函数代码如下：
数学上的原理非常简单，就是先除数 被除数10的上下两边同时乘以一个大数字，这个大数字是2的N次方的表示，最终得到一个magic number乘以除数 再移位的算法。以32bit除10算法为例子:
x / 10= ( x * 2的35次方代表的数字)/ (10 * 2的35次方代表的数字 ) = x * ( 2的35次方代表的数字 / 10 ) / ( 2的35次方代表的数字 ) = ( x * 0xCCCCCCCD ) >> 35 。这里0xCCCCCCCD是一个魔术数字magic number, 来自于( 2的35次方代表的数字 / 10 )的计算结果．
这里取2的35次方，是因为取到 大于等于 这个值，即算法的推导过程中使用的数字要高于32bit数字8倍以上，才能够保证任意32bit除数计算的精度，过去有很多算法论文中给出的 magic number 并不能保证32bit任意数字除十都是完全正确的，是工程中的大坑。
unsigned char div_10( const unsigned char uchar_in ) noexcept
#ifdef HAISQL_USE_FAST_DIV
unsigned short ushort_out = 0xCD;
ushort_out *= uchar_in;
ushort_out = ushort_out >> 11;
unsigned char uchar_out = ushort_out;
return uchar_out;
#else
return uchar_in/10;
#endif // HAISQL_USE_FAST_DIV
unsigned short div_10( const unsigned short ushort_in ) noexcept
#ifdef HAISQL_USE_FAST_DIV
unsigned int uint_out = 0xCCCD;
uint_out *= ushort_in;
uint_out = uint_out >> 19;
unsigned short ushort_out = uint_out;
return ushort_out;
#else
return ushort_in/10;
#endif // HAISQL_USE_FAST_DIV
unsigned int div_10( const unsigned int uint_in ) noexcept
#ifdef HAISQL_USE_FAST_DIV
unsigned long long ulong_out = 0xCCCCCCCD;
ulong_out *= uint_in;
ulong_out = ulong_out >> 35;
return ulong_out;
#else
return uint_in/10;
#endif // HAISQL_USE_FAST_DIV
}二）在一些场合下，使用 to_chars 代替 sprintf 和 to-string, 可以提供更快的速度
sprintf 其中涉及格式的匹配等复杂的算法，有不必须要的开销，降低了处理速度．
to-string 函数中，由于输出是一/string的对象，对象的创建开销不小，也降低了处理速度．
自研的 to_chars 函数中(是类似char* to_chars( const unsigned int uint_in, char* chars_out ) )，由于不涉及对象的创建和内存的分配，比std C++17的定义更简单，只有两个参数，一个是需要转换的二进制数字，一个是输出字符串临时存放的空间（建议是char charstmp[24], 这样就有足够的空间来输出任意二进制数字了），因此，性能更高．
可以看到 haisql::to_chars 比 std::to-string 快了近10倍, C++17 开始提供to-chars, 很多公司内部库早就有类似的函数，有更好的性能表现．
下面是二进制转十进制算法的性能比对测试代码:
unsigned long long test_std_to_string( void )
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
std::string str_tmp;
for( unsigned int i=0; i<100000000; ++i )
str_tmp = std::to_string( i );
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "std to_string use=" << ulong_return << ", str_tmp=" << str_tmp << std::endl;
return ulong_return;
unsigned long long test_haisql_to_string( void )
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
haisql::string str_tmp;
for( unsigned int i=0; i<100000000; ++i )
str_tmp = haisql::to_string( i );
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "haisql to_string use=" << ulong_return << ", str_tmp=" << str_tmp << std::endl;
return ulong_return;
unsigned long long test_std_sprintf( void )
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
char chars_tmp[24];
for( unsigned int i=0; i<100000000; ++i )
sprintf( chars_tmp, "%u", i );
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "std sprintf use=" << ulong_return << ", chars_tmp=" << chars_tmp << std::endl;
return ulong_return;
unsigned long long test_haisql_to_chars( void )
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
char chars_tmp[24];
for( unsigned int i=0; i<100000000; ++i )
haisql::to_chars( i, chars_tmp );
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "haisql to_chars use=" << ulong_return << ", chars_tmp=" << chars_tmp << std::endl;
return ulong_return;
unsigned long long test_std_div_10_ushort( void )
unsigned long long ulong_out = 0;
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
for( unsigned short i=0; i<65535; ++i )
ulong_out += i /10;
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "std div 10 ushort use=" << ulong_return << ", ulong_out=" << ulong_out << std::endl;
return ulong_return;
unsigned long long test_haisql_div_10_ushort( void )
unsigned long long ulong_out = 0;
unsigned long long ulong1 = haisql::now_steady_nanoseconds();
for( unsigned short i=0; i<65535; ++i )
ulong_out += haisql::div_10( i );
continue;
unsigned long long ulong2 = haisql::now_steady_nanoseconds();
unsigned long long ulong_return = ulong2 - ulong1;
std::cout << "haisql div 10 ushort use=" << ulong_return << ", ulong_out=" << ulong_out << std::endl;
return ulong_return;
int main()
test_haisql_div_10_ushort();
test_std_div_10_ushort();
test_haisql_to_chars();
test_haisql_to_string();
test_std_sprintf();
test_std_to_string();
return 0;
｝今天测试的CPU是Intel 新款CPU 9400F, 可以看到测试结果中除法指令已经与乘法指令一样快了，可以看到 haisql::to_chars 最快，比最慢的算法 std: to_string 快了大约十倍。
haisql div 10 ushort use=57307, ulong_out=214709045
std div 10 ushort use=55000, ulong_out=214709045
haisql to_chars use=690220837, chars_tmp=99999999
haisql to_string use=1997057466, str_tmp=99999999
std sprintf use=5059943777, chars_tmp=99999999
std to_string use=6122841289, str_tmp=99999999早期数年前测试，由于当时Intel CPU除法比乘法慢很多倍，加上当时C++标准库也没有to-chars, 在一些特定场合中对比haisql::to-chars 与 std::to-string 有大约数十倍的性能提升．
附录：下面是我自己写的高性能除法算法的技术验证代码，主要是两种高性能除法器的技术验证代码．算法的平均复杂度大约是bit数/2，即32bit下平均16次循环。
算法１是：用简单的加减法＋移位，可以实现除法：
算法１：主要思路是: 先进行最高比特位对齐，对齐之后进行比较，即可得到输出商的最高bit对应的数字，然后，依次右移，每次右移后比较就得到输出商的的下一位bit对应的数字，依次把每位bit对应的数值加起来，就是输出商的值。因此算法是非常精简的，硬件做32bit除法运算，大约只需要16+2个时钟周期即可。
unsigned int uint_div( const unsigned int uint_number_in, const unsigned int uint_denom_in )
if( uint_denom_in > 1 )
// 先找到最高位
unsigned int uint_number = uint_number_in;
unsigned int uint_multi_denom = uint_denom_in;
unsigned int uint_result_high_bit = 1;
unsigned int uint_result_out = 0;
const unsigned int uint_high_bit_denom = _bit_scan_reverse( uint_denom_in );
const unsigned int uint_high_bit_number = _bit_scan_reverse( uint_number_in );
if( uint_high_bit_number > uint_high_bit_denom )
const unsigned int uint_shift_count = uint_high_bit_number - uint_high_bit_denom;
uint_multi_denom = uint_multi_denom << uint_shift_count;
uint_result_high_bit = uint_result_high_bit << uint_shift_count;
while( uint_result_high_bit > 0 )
if( uint_number >= uint_multi_denom )
uint_result_out += uint_result_high_bit;
uint_number -= uint_multi_denom;
uint_result_high_bit = uint_result_high_bit >> 1;
uint_multi_denom = uint_multi_denom >> 1;
continue;
return uint_result_out;
if( uint_number_in >= uint_denom_in )
return 1;
return 0;
if( 1 == uint_denom_in )
return uint_number_in;
std::cerr << "Error: uint_div() div zero. uint_number_in=" << uint_number_in << ", uint_denom_in=" << uint_denom_in << std::endl;
abort();
return 0;
}算法２：用乘法＋移位，实现除法，即本文的一些思路
算法３：这个主要是算法１的改进，不需要intel cpu 的特殊指令_bit_scan_reverse， 适应范围更广，但是也更慢一点．主要是最高位bit对齐，需要额外的循环周期。
注意下面这行代码实现了防止位溢出的作用，否则在处理大于INTMAX的值时，会出错。
if( uint_multi_denom < uint_multi_denom_new )这行
unsigned int uint_div( const unsigned int uint_number_in, const unsigned int uint_denom_in )
if( uint_denom_in > 1 )
// 先找到最高位
unsigned int uint_number = uint_number_in;
unsigned int uint_multi_denom = uint_denom_in;
unsigned int uint_result_high_bit = 1;
unsigned int uint_result_out = 0;
while( 1 )
if( uint_number > uint_multi_denom )
const unsigned int uint_multi_denom_new = uint_multi_denom << 1;
if( uint_multi_denom < uint_multi_denom_new )
uint_multi_denom = uint_multi_denom_new;
uint_result_high_bit = uint_result_high_bit << 1;
continue;
break;
while( uint_result_high_bit > 0 )
if( uint_number >= uint_multi_denom )
uint_result_out += uint_result_high_bit;
uint_number -= uint_multi_denom;
uint_result_high_bit = uint_result_high_bit >> 1;
uint_multi_denom = uint_multi_denom >> 1;
continue;
return uint_result_out;
if( 1 == uint_denom_in )