有没有在C / C ++使用％（模数）的方法吗？ [英] Is there an alternative to using % (modulus) in C/C++?
问题描述
我读一次的地方，取模运算符是在小型嵌入式设备，例如8位万分之一没有整数除法运算符效率低下。也许有人可以证实这一点，但我觉得不同的是5-10的时间比整数除法运算速度较慢。
有另一种方式比保持计数器变量并手动溢出到0的MOD点要做到这一点其他？
const int的FIZZ = 6;
对于（INT X = 0; X＆LT; MAXCOUNT; X ++）
{
如果打印（菲斯\\ n）（（X％FIZZ）！）; //慢在某些系统上
}
VS
我目前在做它的方式：
const int的FIZZ = 6;
INT fizzcount = 1;
对于（INT X = 1; X＆LT; MAXCOUNT; X ++）
{
如果（fizzcount＆GT; = FIZZ）
{
打印（菲斯\\ n）;
fizzcount = 0;
}
}
嗯，按位运算的乐趣。许多师例程的副作用是模 - 因此，在少数情况下应该划分实际上比模量更快。我很感兴趣，看看你得到这个信息的来源。与乘数处理器有使用乘法器有趣的分裂程序，但你可以从除法结果得到与只是一个两个步骤（乘法和减法），以模量所以它仍然具有可比性。如果处理器有一个内置的分割程序，你可能会看到它也提供了其余部分。
不过，有专门模数数论的一个小分支，它需要研究，如果你真的想要了解如何优化模操作。同余，例如，是产生幻方的非常方便的。
因此，在这种精神，这里有一个非常低的水平看看在模数的数学对于x的一个例子，它应该向您展示它如何简单进行比较，以划分：
也许一个更好的方式去思考问题是数量方面
基地和模运算。例如，你的目标是计算DOW
mod7，其中道指的一天的16位重presentation
周。你可以这样写的：
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
防爆$ P $以这种方式pssed，可以分别计算出模7
导致的高和低字节。乘结果为通过高
4，并将其添加到低，然后最终计算结果模7
计算一个8位数字的模7的结果可以在被执行
类似的方式。您可以在八进制写一个8位数字，像这样：
X = A * 64 + B * 8 + C
其中a，b，和c是3位的数字。
X％7 =（（一％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
当然，一个，b和c是
C = X'放大器; 7
B =（X GT;→3）及7
一个=（X GT;→6）及7 //（实际上，一个只有2位）。
为的最大可能值A + B + C 是 7 + 7 + 3 = 17 。所以，你需要
多一个八进制的一步。完整的（未经测试）C版本可能是
这样写的：
unsigned char型Mod7Byte（unsigned char型X）
{
X =（X及7）+（（X - GT;→3）及7）+（X GT;＆→6）;
X =（X及7）+（X GT;→3）; 返回X == 7？ 0：X;
}
我花了一些时间写一个PIC版本。实际执行
稍微不同于上面
Mod7Byte：
MOVWF temp1中;
ANDLW 7; W =Ç
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现在是一个6比特的数
ANDLW 0x38;获得高3位==一
XORWF TEMP2，F; TEMP2现在有3低位== B'
rlncf WREG，F;高右移4
SWAPF WREG，F;
ADDWF TEMP2，W; W = A'+ B' ;在这一点上，W是0和10之间
ADDLW -7
BC Mod7Byte_L2
Mod7Byte_L1：
ADDLW 7
Mod7Byte_L2：
返回
下面是一个例行liitle测试算法
CLRF点¯x
CLRF计数TestLoop：
MOVF X，W
RCALL Mod7Byte
cpfseq计数
胸罩失败 INCF算，W
XORLW 7
skpz
XORLW 7
MOVWF计数 INCFSZ X，˚F
胸罩TestLoop
通过：
最后，对于16位结果（我没有测试），你可以
写：
UINT16 Mod7Word（UINT16 X）
{
返回Mod7Byte（Mod7Byte（X安培; 0xff的）+ Mod7Byte（X GT;→8）* 4）;
}
斯科特
I read somewhere once that the modulus operator is inefficient on small embedded devices such as 8 bit micros without integer division operator. Perhaps someone can confirm this but I thought the difference is 5-10 time slower than with an integer division operation.
Is there another way to do this other than keeping a counter variable and manually overflowing to 0 at the mod point?
const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
vs:
The way I am currently doing it:
const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
Ah, the joys of bitwise arithmetic. A side effect of many division routines is the modulus - so in few cases should division actually be faster than modulus. I'm interested to see the source you got this information from. Processors with multipliers have interesting division routines using the multiplier, but you can get from division result to modulus with just another two steps (multiply and subtract) so it's still comparable. If the processor has a built in division routine you'll likely see it also provides the remainder.
Still, there is a small branch of number theory devoted to Modular Arithmetic which requires study if you really want to understand how to optimize a modulus operation. Modular arithmatic, for instance, is very handy for generating magic squares.
So, in that vein, here's a very low level look at the math of modulus for an example of x, which should show you how simple it can be compared to division:
Maybe a better way to think about the problem is in terms of number bases and modulo arithmetic. For example, your goal is to compute DOW mod 7 where DOW is the 16-bit representation of the day of the week. You can write this as:
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
Expressed in this manner, you can separately compute the modulo 7 result for the high and low bytes. Multiply the result for the high by 4 and add it to the low and then finally compute result modulo 7.
Computing the mod 7 result of an 8-bit number can be performed in a similar fashion. You can write an 8-bit number in octal like so:
X = a*64 + b*8 + c
Where a, b, and c are 3-bit numbers.
X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
= (a%7 + b%7 + c%7) % 7
= (a + b + c) % 7
since 64%7 = 8%7 = 1
Of course, a, b, and c are
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 // (actually, a is only 2-bits).
The largest possible value for a+b+c is 7+7+3 = 17. So, you'll need
one more octal step. The complete (untested) C version could be
written like:
unsigned char Mod7Byte(unsigned char X)
{
X = (X&7) + ((X>>3)&7) + (X>>6);
X = (X&7) + (X>>3);
return X==7 ? 0 : X;
}
I spent a few moments writing a PIC version. The actual implementation is slightly different than described above
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
Here's a liitle routine to test the algorithm
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:
Finally, for the 16-bit result (which I have not tested), you could write:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Scott
这篇关于有没有在C / C ++使用％（模数）的方法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
