How to use bit operations to replace modulu and division operators?

Question

i have this line of code:

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

This line runs in a loop and the operations "/" and "%" take a lot of resources and time to perform. I would like to change this line and apply bit operations in order to maximize the program performance. How can i do that?

Thanks.

Answer 1

If base is the nth power of two, you can replace division by it with a bitshift of n to the right. Then, since taking the mod 256 of an integer is equivalent to taking its last 8 bits, you can AND it with 0xFF. Alternately, you can reverse the operations if you AND it with 256*base and then bitshift n to the right.

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

Of course, any half-decent compiler should be able to do this for you.

Answer 2

Add -O1 or greater to your compiler options and the compiler will do it for you.

In gcc, -O1 turns on -ftree-slsr which is, according to the docs,

Perform straight-line strength reduction on trees. This recognizes related expressions involving multiplications and replaces them by less expensive calculations when possible.

This will replace the modulo, and the base if it is constant. However, if you know that the base will be some non-constant power of two, you can refactor the surrounding code to give you the log2 of that number, and >> by that amount minus one.

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.