在C / C ++中获得正模的最快方法

通常在我的内部循环中,我需要以“环绕”方式对数组进行索引,以便如果数组大小为100,并且代码要求元素-2,则应该给出元素98.在许多高级语言中作为Python,可以简单地用my_array[index % array_size]来做到这一点,但由于某些原因,C的整数算术(通常)向零舍入,而不是一直向下舍入,因此,其模运算符在给定负的第一个参数时返回负结果。

通常我知道index不会小于-array_size ,在这种情况下,我只是做my_array[(index + array_size) % array_size] 。 但是,有时这是不能保证的,对于这些情况,我想知道实现总是正模的function的最快方法。 有几个“聪明”的方式来做到这一点没有分支,如

 inline int positive_modulo(int i, int n) { return (n + (i % n)) % n } 

要么

 inline int positive_modulo(int i, int n) { return (i % n) + (n * (i < 0)) } 

当然,我可以通过这些来找出哪些是我的系统中速度最快的,但是我不禁担心我可能错过了一个更好的,或者我的机器上的速度可能会变慢。

那么有没有一个标准的方法来做到这一点,或者我错过了一个聪明的把戏,这可能是最快的方法?

另外,我知道这可能是一厢情愿的想法,但是如果有这样一种可以自动vector化的方法,那将是惊人的。

我学到的标准方法是

 inline int positive_modulo(int i, int n) { return (i % n + n) % n; } 

这个函数本质上是你的第一个没有abs变体(实际上,它会返回错误的结果)。 如果一个优化编译器可以识别这个模式,并将其编译为计算“无符号模”的机器码,我不会感到惊讶。

编辑:

继续讨论你的第二个变体:首先,它也包含一个bug – n < 0应该是i < 0

这个变体可能看起来不像分支,但是在很多架构上, i < 0会编译成条件跳转。 在任何情况下,用i < 0? n: 0代替(n * (i < 0))至less是一样快的i < 0? n: 0 i < 0? n: 0 ,避免乘法; 此外,它是“更清洁”,因为它避免了重新解释布尔作为整数。

至于这两个变种中的哪一个变得更快,这可能取决于编译器和处理器架构 – 两个变种的时间和看到。 不过,我认为没有比这两种变种更快的方法。

模两个幂,下面的工作(假设两个补码表示):

 return i & (n-1); 

使用二进制补码符号位传播来获得可选加数的老派方法:

 int positive_mod(int i, int n) { /* constexpr */ int shift = CHAR_BIT*sizeof i - 1; int m = i%n; return m+ (m>>shift & n); } 

你可以做array[(i+array_size*N) % array_size] ,其中N是足够大的整数,以保证积极的参数,但足够小,不会溢出。

当array_size是常量时,有一些技术可以在不分割的情况下计算模量。 除了两种方法的功效之外,可以计算比特组的加权总和乘以2 ^ i%n,其中i是每组中的最低有效位:

例如32位整数0xaabbccdd%100 = dd + cc * [2] 56 + bb * 36 + aa * 16,其最大范围为(1 + 56 + 36 + 16)* 255 = 27795 。通过重复的应用和不同的细分,可以将操作减less到很less的条件减法。

通常的做法还包括将倒数近似为2 ^ 32 / n的倒数,这通常可以处理相当大范围的论据。

  i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...) 

你的第二个例子比第一个更好。 乘法是比if / else操作更复杂的操作,所以使用这个:

 inline int positive_modulo(int i, int n) { int tmp = i % n; return tmp ? i >= 0 ? tmp : tmp + n : 0; }