模块化操作 (%) 提供错误输出

Question

使用函数 getNextIdx，我想接收一个数组的新索引，该索引取决于当前索引和该索引处的数组值。

我希望函数 return 通过将当前索引与数组在该索引处的值相加，对数组大小进行取模来 return 新索引。

#include<vector> 
using namespace std;

int getNextIdx(int currentIdx, vector<int> array) {
    int jump = array[currentIdx];
    int nextIdx = (currentIdx + jump) % array.size();
    
    return (nextIdx >= 0) ? nextIdx : nextIdx + array.size();
}
int main() {
    vector<int> test = {2, 3, 1, -4, -4, 2};
    int nextIdx = getNextIdx(3, test);    
}

示例：如果当前索引为3（第4个元素），数组中第4个元素的值为-4，数组大小为6，则函数应return 5.

问题是我的程序return上面例子中的3.

Answer 1

取模运算符向零舍入（即使是负数）。您的数学期望模数向负无穷大或正无穷大舍入。参见 Modulo operation with negative numbers

int getNextIdx(int currentIdx, vector<int> array){
  int jump = array[currentIdx];
  int nextIdx = currentIdx + jump;
  if (nextIdx < 0)
    nextIdx += array.size();
  if (nextIdx >= array.size())
    nextIdx -= array.size();
  return nextIdx;
}

Answer 2

关于示例代码应该考虑的另一个问题是发生了类型转换。由于 array.size()(6) 的类型是 size_t 而另一方面另一个数字是负数，因此编译器将负数转换为 size_t 然后对它们应用模运算符。例如 (-1)% 6 的输出是 (-1) 但 (-1) % array.size() 的输出是 (3) 因为 (-1) 转换为 size_t 并且变成了 (4294967295)（基于平台，输出应该不同）所以 (4294967295 % 6) 的模数是 (3).

Answer 3

在 % 运算符中使用否定参数是可以的。问题是您混合了整数类型：nextIdx 是一个有符号整数，而 array.size() returns 是一个无符号整数。所以你的问题可以归结为这行代码：

std::cout << -1 % 6u << std::endl; // returns 3

%操作在这里做的是将左侧的类型转换为右侧的类型，所以你的 -1 变成无符号的，这打乱了你的逻辑模块化操作。

你可以通过像这样改变你的函数来解决这个问题：

int nextIdx = (currentIdx + jump) % (int) array.size();

（未要求）代码审查：

如果您可以通过适当定义函数的输入来安排您的函数为您执行这些类型的类型转换，那就更好了。另外，让我们清理输入。

像这样：

#include <cassert>
#include <iostream>
#include <vector> 

int64_t PostiveModular (int64_t n, int64_t m)
{
    assert(m > 0);
    
    return n % m + (n < 0) * m;
}

uint64_t NextIndex (uint64_t i, const std::vector<int> & vec)
{
    assert(i < vec.size());
    
    return PostiveModular(i + vec[i], vec.size());
}

模块化操作 (%) 提供错误输出

Modular operation (%) provides false output

c++

modular-arithmetic