你真的了解模运算吗?
你真的了解模运算吗?
问题
假设我们需要编写一个字母表右移映射的程序(可能用于实现某种加密算法),说起来似乎有些抽象,举个例子便清晰了:
譬如字母表为 { ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ }, 右移3位的话, 字母表便被映射为 { ‘d’, ‘e’, ‘a’, ‘b’, ‘c’ }
使用Lua,我们简单编写了以下代码
local code_table = { "a", "b", "c", "d", "e" }
local function get_map_code(code_index, shift_count)
local code_table_count = #code_table
local map_index = (code_index + shift_count - 1) % code_table_count + 1
return code_table[map_index]
end
for i = 1, #code_table do
print(get_map_code(i, 3))
end现在我们需要扩展程序以支持字母表左移映射的需求,考虑到左移仅是右移的逆操作,我们只要改变shift_count的符号即可~
for i = 1, #code_table do
print(get_map_code(i, -3))
end运行测试目测没有问题,nice~
现在我们为了某些考虑(譬如性能),需要将代码移植至C/C++,移植完成后的代码如下:
const char codeTable[] = { 'a', 'b', 'c', 'd', 'e' };
const int codeTableCount = sizeof(codeTable) / sizeof(char);
auto getMapCode =
[&codeTable, codeTableCount](int codeIndex, int shiftCount)
{
auto mapIndex = (codeIndex + shiftCount) % codeTableCount;
return codeTable[mapIndex];
};
for (auto i = 0; i < codeTableCount; ++i)
{
cout << getMapCode(i, 3) << "\n";
}程序的运行结果与Lua是一致的,但是当我们简单的移植左移的时候,程序的结果却出错了……
for (auto i = 0; i < codeTableCount; ++i)
{
// error !!!
cout << getMapCode(i, -3) << "\n";
}问题其实就出在模运算(%)上:
左移操作由于使用了负数的偏移,导致了负数取模运算,而对于负数取模,Lua和C/C++的结果是不一致的,进而导致了结果的偏差……
那么到底Lua和C/C++中的负数取模有什么不一样呢?我们先从模运算的定义说起~
r = a - I(a / b) * b
其中a为除数,b为被除数,r即为模运算的结果,即余数,而I(…)代表的是取整函数,取整函数不同,取模结果自然也就不同
对于Lua,I(…)使用的是向下取整(Floor)的方式,所以如果我们在Lua中计算-1 % 5 的话, 有:
r = -1 - Floor(-1 / 5) * 5 = -1 - (-1) * 5 = 4
而对于C/C++而言,I(…)使用的是截断(Truncate)的方式,所以如果我们在C/C++中计算-1 % 5 的话, 有:
r = -1 - Truncate(-1 / 5) * 5 = -1 - (0) * 5 = -1
由于模运算的结果为负导致索引出界,自然程序的结果也就不会正常了~
知道了程序出错的原因,“修复”起来也就有了对策,方法很简单,自己实现一个使用Floor的取模运算即可~
const char codeTable[] = { 'a', 'b', 'c', 'd', 'e' };
const int codeTableCount = sizeof(codeTable) / sizeof(char);
auto module =
[](int dividend, int divisor) -> int
{
return dividend - floor((float)dividend / (float)divisor) * divisor;
};
auto getMapCode =
[&codeTable, codeTableCount, &module](int codeIndex, int shiftCount)
{
auto mapIndex = module(codeIndex + shiftCount, codeTableCount);
return codeTable[mapIndex];
};
for (auto i = 0; i < codeTableCount; ++i)
{
cout << getMapCode(i, -3) << "\n";
}值得一提的是如果你使用Lua中math.fmod来计算 -1 % 5 的话,结果和C/C++中是一致的,为 -1
总结
模运算看似简单,但其实大家不一定真正了解,这里有一段Python中关于模运算怎么实现(同Lua一样,也使用了Floor取整)的讨论,有兴趣的朋友可以看下~
OK,下次再见吧~