首页 / 知识

除了在C / C中使用％(模数)之外，还有其他选择吗？

2023-04-14 11:06:00

Is there any alternative to using % (modulus) in C/C++?

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

除了保持计数器变量并在mod点手动溢出为0之外，还有其他方法吗？

1
2
3
4
5
6

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

vs：

我目前的操作方式：

1
2
3
4
5
6
7
8
9
10
11

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

啊，按位运算的乐趣。许多除法例程的副作用是模数-因此在少数情况下，除法运算实际上应快于模数。我很想知道您从中获得此信息的来源。带有乘法器的处理器使用乘法器具有有趣的除法例程，但是您只需再进行两步(乘和减)就可以将除法结果转换为模数，因此仍具有可比性。如果处理器具有内置的除法例程，您可能会看到它还提供了余数。

仍然，有一小部分数论致力于模块化算术，如果您真的想了解如何优化模数运算，则需要进行研究。例如，模块化算术对于生成魔术方块非常方便。

因此，就x的示例而言，这是一个非常低级的模数数学运算，它应向您显示与除法相比它有多简单：

考虑问题的更好方法可能是数字
基和模运算。例如，您的目标是计算DOW
mod 7，其中DOW是当前日期的16位表示
周。您可以这样写：

1
2
3
4
5
6

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位数字：

1	X = a64 + b8 + c

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

1
2
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是

1
2
3

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版本可能是
像这样写：

1
2
3
4
5
6
7

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版本。实际执行
与上述内容略有不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

这是测试算法的常规程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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位结果(我尚未测试)，您可以
写：

1
2
3
4

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

斯科特

如果您要计算一个数模的2的幂，可以使用按位和运算符。只需从第二个数字中减去一个即可。例如：

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

一些警告：

仅当第二个数字是2的幂时才有效。

仅当模数始终为正时才等效。当第一个数字为负数时，C和C标准没有指定模数的符号(直到C 11才保证它为负数，这是大多数编译器已经在做的事情)。按位并摆脱符号位，因此它将始终为正(即，它是真实的模数，而不是余数)。听起来这仍然是您想要的。

您的编译器可能在可能的时候已经这样做了，因此在大多数情况下，不值得手动进行此操作。

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

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

但是，经验法则是将数组大小等选择为2的幂。

因此，如果要计算星期几，则无论如何都可以使用％7
如果设置了约100个条目的循环缓冲区...为什么不将其设置为128。则可以编写％128，大多数(所有)编译器都将这样做

除非您确实确实需要在多个嵌入式平台上实现高性能，否则在您进行概要介绍之前，请勿出于性能原因而更改编码方式！

为优化性能而笨拙地编写的代码很难调试和维护。编写一个测试用例，然后将其配置在目标上。一旦知道模数的实际成本，然后确定替代解决方案是否值得编码。

@Matthew是正确的。试试这个：

1
2
3
4
5
6
7
8
9

int main() {
int i;
for(i = 0; i<=1024; i++) {
if (!(i & 0xFF)) printf("& i = %d\
", i);
if (!(i % 0x100)) printf("mod i = %d\
", i);
}
}

您应该真正检查所需的嵌入式设备。我见过的所有汇编语言(x86，68000)都使用除法实现模数。

实际上，除法汇编操作将除法结果和余数返回到两个不同的寄存器中。

您可以访问嵌入式设备上的任何可编程硬件吗？喜欢柜台等吗？如果是这样，您也许可以编写基于硬件的mod单元，而不用使用模拟的％。 (我曾在VHDL中这样做一次。不确定是否仍然有代码。)

请记住，您确实说过分裂快了5到10倍。您是否考虑过进行除法，乘法和减法来模拟mod？ (编辑：误解了原始帖子。我确实认为除法比mod快是奇怪的，它们是相同的操作。)

但是，在您的特定情况下，您正在检查的mod是6。6 = 2 * 3。因此，如果您首先检查最低有效位是否为0，则可能会获得一些小的收益。

1
2
3
4
5

if((!(x & 1)) && (x % 3))
{
print("Fizz\
");
}

不过，如果您这样做，我建议您确认自己有任何收获，对分析人员来说是这样。并做一些评论。我为下一个不得不看代码的家伙感到难过。

在嵌入式世界中，您需要执行的"模数"运算通常可以很好地分解为可以用&，|有时甚至是>>进行的位运算。 >

@Jeff V：我发现有问题！ (除了您的原始代码正在寻找mod 6，现在您实质上正在寻找mod 8)。您继续做额外的1！希望您的编译器对此进行了优化，但是为什么不只是从2开始测试并转到MAXCOUNT(含)？最后，每次(x 1)不被8整除时，您将返回true。这是您想要的吗？ (我想是的，但只是想确认。)

这不一定更好，但是您可以有一个内部循环，该循环始终上升到FIZZ，而有一个外部循环将其重复一定次数。如果MAXCOUNT不能被FIZZ整除，则可能需要特殊的最后几个步骤。

那是说，我建议在您打算使用的平台上进行一些研究和性能分析，以明确了解您所面临的性能约束。可能还有更多生产力的地方可以投入优化工作。

与最慢的模数运算符实现相比，打印语句所花费的时间要长几个数量级。因此基本上，注释"在某些系统上缓慢"应该是"在所有系统上缓慢"。

此外，提供的两个代码段执行的操作不同。在第二行中，

行