在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

啊,按位算术的乐趣.许多除法程序的副作用是模数 - 因此在少数情况下,除法实际上应该比模数更快.我很有兴趣看到您从中获取此信息的来源.具有乘数的处理器使用乘法器具有有趣的除法例程,但是您可以通过另外两个步骤(乘法和减法)从除法结果到模数,因此它仍然具有可比性.如果处理器有一个内置的分区例程,你可能会看到它还提供了余数.

尽管如此,还是有一个专门用于模数算术的数论的小分支,如果你真的想要了解如何优化模运算,就需要研究.例如,模块化算术对于生成魔术方块非常方便.

因此,在这种情况下,对于x的示例,这里的模数的数学是非常低级别的,这应该向您展示它与分区相比有多简单:

也许更好的思考问题的方法是数字基数和模运算.例如,你的目标是计算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

这是测试算法的liitle例程

       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

如果你正在计算一个数字mod一些2的幂,你可以使用逐位和运算符.只需从第二个数字中减去一个.例如:

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

一些警告:

1. 这仅在第二个数字是2的幂时才有效.
2. 如果模数总是正的,它只是等价的.C和C++标准时,第一个数字为负(直到C++ 11,不指定模数的符号并保证它会是负的,这是大多数编译器已经在做的).一点一点地摆脱符号位,所以它总是正的(即它是真模数,而不是余数).听起来这就是你想要的东西.
3. 您的编译器可能已经可以执行此操作,因此在大多数情况下,不值得手动执行此操作.

Answer 3

大多数时候使用modulo的开销不是2的幂.这与处理器无关(AFAIK),即使是具有模数运算符的处理器,除了掩码运算之外,对于除法的处理速度要慢几个周期.

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

但是,一条经验法则是选择数组大小等为2的幂.

因此,如果计算星期几,也可以使用%7,无论是否设置大约100个条目的循环缓冲区...为什么不将它设为128.然后你可以编写%128而大多数(所有)编译器将使这个和0x7F