在C/C++中有没有使用%(模数)的替代方法？

Question

我曾经在某处读到模运算符在小型嵌入式设备上效率低下，比如没有整数除法指令的8位微控制器。也许有人可以证实这一点，但我认为这一差异比整数除法运算慢5-10倍。

除了保留计数器变量并在mod点处手动溢出到0之外，还有其他方法可以做到这一点吗？

​

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

vs：

我目前使用的方法是：

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}

Answer 1

啊，按位运算的乐趣。许多除法例程的副作用是模数-所以在少数情况下，除法实际上应该比模数快。我很想看看你是从哪里得到这个消息的。带有乘法器的处理器使用乘法器有有趣的除法例程，但您可以通过另外两个步骤(乘法和减法)从除法结果到模数，因此它仍然是可比较的。如果处理器有一个内置的除法例程，您很可能会看到它还提供了剩余部分。

尽管如此，如果你真的想了解如何优化模运算，还有一小部分数论致力于Modular Arithmetic，这需要研究。例如，模算术对于生成magic squares非常方便。

因此，在这种情况下，这里有一个关于x的模数的数学very low level look，它应该会向您展示它与除法相比是多么简单：

也许考虑这个问题的更好方法是从数基和模运算的角度来考虑。例如，您的目标是计算DOW mod 7，其中DOW是一周中某天的16位表示。您可以将其编写为：

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

以这种方式表示，您可以分别计算高字节和低字节的模7结果。将高值的结果乘以4，然后将其与低值相加，最后计算出模7的结果。

计算8位数的mod 7结果可以以类似的方式执行。你可以像这样写一个八进制的8位数字：

  X = a*64 + b*8 + c

其中a、b和c是3位数字。

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

自64%7 = 8%7 = 1以来

当然，a、b和c是

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

a+b+c的最大可能值是7+7+3 = 17。所以，你还需要一个八进制的步长。完整的(未经测试的)C语言版本可以写成：

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

我花了一些时间写了一个PIC版本。实际的实现与上面描述的略有不同

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

下面是一个用来测试算法的小程序

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

最后，对于16位结果(我还没有测试过)，您可以这样写：

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

史考特

Answer 2

如果你正在计算一个2的幂的数，你可以使用逐位and运算符。只需从第二个数字减去1即可。例如：

x % 8 == x & 7
x % 256 == x & 255

以下是一些注意事项：

如果第二个数是2的幂，，

1. ，，，

，

1. ，它只有在模数始终为正的情况下才是等价的。当第一个数是负数时，C和C++标准没有指定模数的符号(直到C++11，这确实保证了它将是负数，这是大多数编译器已经在做的)。按位并去掉符号位，因此它将始终是正的(即它是一个真正的模数，而不是余数)。这听起来像是你想要的，不管怎样，though.
2. Your编译器可能已经做到了这一点，所以在大多数情况下，这样做是不值得的manually.

Answer 3

在大多数情况下，使用不是2的幂的模数会产生开销。这与处理器(AFAIK)无关，即使具有模运算符的处理器在除法运算时也比掩码运算慢几个周期。

对于大多数情况，这不是一个值得考虑的优化，当然也不值得计算你自己的快捷操作(特别是如果它仍然涉及除法或乘法)。

然而，一条经验法则是选择数组大小等为2的幂。

因此，如果要计算星期几，最好使用%7，无论是否设置了大约100个条目的循环缓冲区...为什么不让它变成128。然后，您可以编写% 128，大多数(所有)编译器将生成这个& 0x7F