你真的了解模运算吗?

梦里梦外; 2022-06-12 03:57 255阅读 0赞

## 问题 ##

假设我们需要编写一个字母表*右移*映射的程序(可能用于实现某种加密算法),说起来似乎有些抽象,举个例子便清晰了:

譬如字母表为 \{ ‘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

## 总结 ##

模运算看似简单,但其实大家不一定真正了解,[这里][Link 1]有一段Python中关于模运算怎么实现(同Lua一样,也使用了Floor取整)的讨论,有兴趣的朋友可以看下~

OK,下次再见吧~

[Link 1]: http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html?m=1