整数位操作比除法/取余快多少？

72 阅读 0 评论 48 点赞

我是靠谱客的博主炙热蚂蚁，最近开发中收集的这篇文章主要介绍整数位操作比除法/取余快多少？，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

最近在写代码的时候，在CSDN论坛上看到一段测试代码，发现位操作求余比mod快了不是一点啊。所以借别人的代码小小总结一下。

代码块

用时测试代码，例如：


#include <iostream>
#include <string>
#include <ctime>
#include <sys/timeb.h>
#include <boost/scoped_array.hpp>
using namespace std;
#define TIMES 100000000
time_t getms()
{
timeb tb;
ftime(&tb);
return (int)(tb.time*1000 + tb.millitm);
}
int main()
{
boost::scoped_array<int> data(new int[TIMES]);
boost::scoped_array<int> result1(new int[TIMES]);
boost::scoped_array<int> result2(new int[TIMES]);
boost::scoped_array<int> result3(new int[TIMES]);
for (int i = 0; i < TIMES; ++ i)
{
data[i] = i;
}
{
time_t oldtime = getms();
for (int i = 0; i < TIMES; ++ i)
{
result1[i] = (data[i] & 0x0F);
}
time_t newtime = getms();
cout << (newtime - oldtime) << endl;
}
{
time_t oldtime = getms();
for (int i = 0; i < TIMES; ++ i)
{
result2[i] = data[i];
result2[i] %= 16;
}
time_t newtime = getms();
cout << (newtime - oldtime) << endl;
}
{
time_t oldtime = getms();
for (int i = 0; i < TIMES; ++ i)
{
result2[i] = data[i];
result2[i] %= 15;
}
time_t newtime = getms();
cout << (newtime - oldtime) << endl;
}
while (true)
{
int j;
cin >> j;
if (j == 0)
{
return 0;
}
{
time_t oldtime = getms();
for (int i = 0; i < TIMES; ++ i)
{
result3[i] = data[i];
result3[i] %= j;
}
time_t newtime = getms();
cout << (newtime - oldtime) << endl;
}
}
}

测试结果

==========================================

结果（运行次数1亿次）：
219 // 使用位操作
234 // 用取模操作%，但是被编译器优化成位操作，看汇编代码很明显
500 // mod 15，无法优化，乖乖用除法去
13 // 我的输入，接下来做一亿次的mod 13
496 // 时间
15 // 我的输入，接下来做一亿次的mod 15
495 // 时间
16 // 我的输入，接下来做一亿次的mod 16
485 // 哈哈，现在没法优化了吧~乖乖做除法
17 // mod 17
484 // 时间

============================================

分析

整数位操作比除、模快一些，用上述数据大概2倍多（我也测试了256和65536作为除数）。对于常量来说，编译器会优化，试图用位操作替换。不过如果不是2的整数倍，也只能乖乖做除法去。如果想看有没有优化，查看汇编代码即可。
大部分时候这种方法带来的性能提升并不明显，不过如果是关键路径的话，可能还是有用武之地。

总结

只用位操作来实现，左移相对于乘法，右移相当于除法

用位操作求余数，如果模数M是2的整数次方的话，应该是相当简单的。
假定一个数X，求其对于M的余数的公式：
1： MOD(X, M) = X - (X >> LOG(M)) << LOG(M)
2： MOD(X, M) = X&(M-1)