c++ - 如何使用位运算来代替模数和除法运算符？

Question

我有这行代码：

 base_num = (arr[j]/base)%256;

此行循环运行，操作“/”和“%”需要大量资源和时间来执行。我想更改此行并应用位操作以最大化程序性能。我怎样才能做到这一点？

谢谢。

Answer 1

如果 base 是 2 的 n 次方，您可以将除法替换为向右移动 n 位。然后，由于取整数的 mod 256 等价于取其最后 8 位，因此您可以将其与 0xFF 进行与运算。或者，如果您将其与 256*base 和然后将 n 向右移位，则可以反转操作。

base_num = arr[j] >> n;
base_num &= 0xFF;

当然，任何半体面的编译器都应该能够为您做到这一点。

Answer 2

为您的编译器选项添加-O1或更高版本，编译器将为您完成。

在 gcc中，根据文档，-O1打开哪个，-ftree-slsr

对树木进行直线强度降低。这可以识别涉及乘法的相关表达式，并在可能的情况下用成本较低的计算替换它们。

这将替换模数和基数（如果它是常数）。但是，如果您知道基数将是 2 的某个非常数幂，则可以重构周围的代码以提供log2该数字的 the 数，然后>>减去该数。

Answer 3

You could also just declare base_num as an 8 bit integer:

#include <stdint.h>

uint8_t base_num;
uint16_t crap;
crap = 0xFF00;
base_num = crap;

If your compiler is standards compliment, it will put the value of byte(0xFF00) (0x00) into base_num.

I have yet to meet a compiler that does saturated arithmetic in plain C (neither C++ or C#), but if it does, it will put the value of sat_byte(0xFF00) which being greater than 0xFF, it will put 0xFF into base_num.

Keep in mind your compiler will warn you of a loss of precision in this instance. Your compiler may error out in this case (Visual Studio does with Treat Warnings as Errors On). If that happens, you can just do:

base_num = (uint8_t)crap;

but this seems like what you are trying to avoid.

What you are trying to do it seems is to remove the modulus operator as that requires a division and division is the most costly basic arithmetic operation. I generally would not think of this as a bottleneck in any way as any "intelligent" compiler (even in debug mode) would "optimize" it to:

base_num = crap & 0xFF;

on a supported platform (every mainstream processor I've heard of - x86, AMD64, ARM, MIPS), which should be any. I would be dumbfounded to hear of a processor that has no basic AND and OR arithmetic instructions.