有没有办法在没有模数/除法运算符的情况下编写"mod 31"？

Question

如果操作数是2的幂,则可以在没有模数运算符或除法的情况下容易地获得数字的模数.在这种情况下,下面的公式成立:x % y = (x & (y ? 1)).在许多架构中,这通常很有效.可以这样做mod 31吗？

int mod31(int a){ return a % 31; };

Answer 1

以下是解决此问题的两种方法.第一个使用常见的bit-twiddling技术,如果仔细优化可以击败硬件划分.另一个用乘法代替除数,类似于执行的优化gcc,并且是最快的.最重要的是,如果第二个参数是常数,那么试图避开%运算符的重点并不多,因为它已经覆盖了它.(也可能是其他编译器.)gcc

以下函数基于x与32的基数之和相同(mod 31)的事实x.这是真的,因为32是1 mod 31,因此任何力量32都是1 mod 31.因此,基数为32的数字中的每个"数字"位置将数字*1贡献给mod 31总和.并且很容易得到base-32表示:我们一次只取五位.

(就像这个答案中的其他函数一样,它只适用于非负数x).

unsigned mod31(unsigned x) {
  unsigned tmp;
  for (tmp = 0; x; x >>= 5) {
    tmp += x & 31;
  }
  // Here we assume that there are at most 160 bits in x
  tmp = (tmp >> 5) + (tmp & 31);
  return tmp >= 31 ? tmp - 31 : tmp;
}

对于特定的整数大小,您可以展开循环并且很可能击败除法.(并且看到@ chux的回答是一种将循环转换为O(log bits)运算的方法而不是O(bits)它更难以击败gcc,这避免了当被除数是编译时已知的常数时的除法.

在使用无符号32位整数的非常快速的基准测试中,天真的展开循环花费了19秒,基于@ chux的答案的版本只花了13秒,但gcc的x%31花费了9.7秒.强制gcc使用硬件除法(通过使除法非常数)花费23.4秒,并且如上所示的代码花费25.6秒.这些数字应该用几粒盐.时间用于计算我笔记本电脑上i%31所有可能的值.i-O3 -march=native

gcc通过用基本上64位乘法乘以常数的倒数后跟右移来避免32位除以常数.(实际的算法做了一些工作以避免溢出.)该程序在20多年前实现gcc v2.6,并且描述该算法的论文可在gmp站点上获得.(GMP也使用这个技巧.)

这是一个简化版本:假设我们想要计算n // 31一些无符号的32位整数n(使用pythonic //来表示截断的整数除法).我们使用"魔法常数" ,即.现在很明显,对于任何:m = 232 // 31138547332n

m * n <= 232 * n/31 < m * n + n ⇒ m * n // 232 <= n//31 <= (m * n + n) // 232

(这里我们利用这个事实,如果a < b那么floor(a) <= floor(b).)

此外,因为,并且是相同的整数或两个连续的整数.因此,这两者中的一个(或两个)是实际值.n < 232m * n // 232(m * n + n) // 232n//31

现在,我们真的想要计算n%31.所以我们需要将(假定的)商乘以31,并从中减去n.如果我们使用两个可能的商中较小的一个,可能会发现计算的模数值太大,但它只能太大31.

或者,把它放在代码中:

static unsigned long long magic = 138547332;
unsigned mod31g(unsigned x) {
  unsigned q = (x * magic) >> 32;
  // To multiply by 31, we multiply by 32 and subtract
  unsigned mod = x - ((q << 5) - q);
  return mod < 31 ? mod : mod - 31;
}

gcc使用的实际算法通过使用基于乘以的稍微更准确的计算来避免最后的测试.这总是产生正确的商,但代价是一些额外的移位并增加以避免整数溢出.事实证明,上面的版本稍微快一些 - 在与上面相同的基准测试中,它只用了6.3秒.237//31 + 1

其他基准功能,完整性:

天真的展开循环

unsigned mod31b(unsigned x) {
  unsigned tmp = x & 31; x >>= 5;
  tmp += x & 31; x >>= 5;
  tmp += x & 31; x >>= 5;
  tmp += x & 31; x >>= 5;
  tmp += x & 31; x >>= 5;
  tmp += x & 31; x >>= 5;
  tmp += x & 31;

  tmp = (tmp >> 5) + (tmp & 31);
  return tmp >= 31 ? tmp - 31 : tmp;
}

@ chux的改进,略微优化

static const unsigned mask1 = (31U << 0) | (31U << 10) | (31U << 20) | (31U << 30);
static const unsigned mask2 = (31U << 5) | (31U << 15) | (31U << 25);
unsigned mod31c(unsigned x) {
  x = (x & mask1) + ((x & mask2) >> 5);
  x += x >> 20;
  x += x >> 10;

  x = (x & 31) + ((x >> 5) & 31);
  return x >= 31 ? x - 31: x;
}

Answer 2

下面的[Edit2]表示性能说明

只有1个if条件的尝试.

这种方法是O(log2(sizeof unsigned)).运行时间将增加1组ands/shifting/add,而不是代码使用循环方法的两倍uint64_t.

unsigned mod31(uint32_t x) {
  #define m31 (31lu)
  #define m3131 ((m31 << 5) | m31)
  #define m31313131 ((m3131 << 10) | m3131)

  static const uint32_t mask1 = (m31 << 0) | (m31 << 10) | (m31 << 20) | (m31 << 30);
  static const uint32_t mask2 = (m31 << 5) | (m31 << 15) | (m31 << 25);
  uint32_t a = x & mask1;
  uint32_t b = x & mask2;
  x = a + (b >> 5);
  // x = xx 0000x xxxxx 0000x xxxxx 0000x xxxxx

  a = x & m31313131;
  b = x & (m31313131 << 20);
  x = a + (b >> 20);
  // x = 00 00000 00000 000xx xxxxx 000xx xxxxx

  a = x & m3131;
  b = x & (m3131 << 10);
  x = a + (b >> 10);
  // x = 00 00000 00000 00000 00000 00xxx xxxxx

  a = x & m31;
  b = x & (m31 << 5);
  x = a + (b >> 5);
  // x = 00 00000 00000 00000 00000 0000x xxxxx

  return x >= 31 ? x-31 : x;
}

[编辑]

第一加法方法并行地对各个7组五位进行求和.随后的加法使7组进入4,然后是2,然后是1.最后的7位和然后继续将其上半部分(2位)加到其下半部分(5位).然后代码使用一个测试来执行最终的"mod".

此方法可扩展至更宽unsigned至至少uint165_tlog2(31 + 1)*(31 + 2).通过它,需要更多的代码.

请参阅@rici以获得一些很好的优化.仍然建议使用uint32_t与unsigned和31UL在像偏移31U << 15作为unsigned 31U可能仅16位长.(int2014年在嵌入式世界中流行16位).

[EDIT2]

除了让编译器使用其优化器之外,另外两种技术可以提高性能.这些是更小的客厅技巧,取得了适度的改善.请记住YMMV,这是一个32位unsigned.

使用表格查找最后modulo改进10-20%.使用unsigned t表而不是unsigned char t帮助一点.事实证明,表长度,首先预计需要2*31,只需要31 + 5.

使用局部变量而不是总是调用函数参数令人惊讶地帮助.可能是我的gcc编译器的一个弱点.

发现未分支的非分支解决方案,以替换x >= 31 ? x-31 : x.但是他们的编码复杂性更高,性能更慢.

总而言之,这是一项有趣的运动.

unsigned mod31quik(unsigned xx) {
  #define mask (31u | (31u << 10) | (31u << 20) | (31u << 30))
  unsigned x = (xx & mask) + ((xx >> 5) & mask);
  x += x >> 20;
  x += x >> 10;
  x = (x & 31u) + ((x >> 5) & 31u);

  static const unsigned char t[31 * 2 /* 36 */] = { 0, 1, 2, 3, 4, 5, 6,
      7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      25, 26, 27, 28, 29, 30, 0, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  return t[x];
}

Answer 3

您可以使用连续加法/减法。没有其他技巧，因为 31 是素数，要查看一个数N模 31 的模数，您必须除以求余数。

int mode(int number, int modulus) {
    int result = number;

    if (number >= 0) {
         while(result > modulus) { result = result - modulus;}
    } else {
         while (result < 0) { result = result + modulus;)
    }
}