Как использовать битовые операции для замены модулей и операторов деления?
у меня есть эта строка кода:
base_num = (arr[j]/base)%256;
Эта строка выполняется в цикле, а операции «/» и «%» занимают много ресурсов и времени для выполнения. Я хотел бы изменить эту строку и применить битовые операции, чтобы максимизировать производительность программы. Как я могу это сделать?
Благодарю.
Решение
Если основание является n-й степенью двойки, вы можете заменить деление на него битовым сдвигом n вправо. Затем, поскольку получение значения 256 из целого числа эквивалентно получению последних 8 бит, вы можете использовать AND с 0xFF. Кроме того, вы можете отменить операции, если вы И это с 256 * базы, а затем сдвиг бит n вправо.
base_num = arr[j] >> n;
base_num &= 0xFF;
Конечно, любой полуприличный компилятор должен быть в состоянии сделать это за вас.
Другие решения
добавлять -O1 или больше к вашим опциям компилятора, и компилятор сделает это за вас.
В gcc, -O1 включается -ftree-slsr что, согласно документам,
Выполните прямолинейное снижение прочности на деревьях. Это распознает связанные выражения, включающие умножения, и заменяет их на менее дорогие вычисления, когда это возможно.
Это заменит модуль и базу, если она постоянна. Однако, если вы знаете, что основа будет иметь некоторую непостоянную степень двойки, вы можете реорганизовать окружающий код, чтобы дать вам log2 из этого числа, и >> на эту сумму минус один.
Вы также можете просто объявить base_num как 8-битное целое число:
#include <stdint.h>
uint8_t base_num;
uint16_t crap;
crap = 0xFF00;
base_num = crap;
Если ваш компилятор является стандартом комплимента, он примет значение byte(0xFF00) (0x00) в base_num,
Я еще не встречал компилятор, который выполняет насыщенную арифметику в простом C (ни C ++, ни C #), но если это произойдет, он установит значение sat_byte(0xFF00) который больше чем 0xFF, это поставит 0xFF в base_num,
Имейте в виду, что в этом случае ваш компилятор предупредит вас о потере точности. В этом случае ваш компилятор может выдать ошибку (Visual Studio делает с Treat Warnings as Errors На). Если это произойдет, вы можете просто сделать:
base_num = (uint8_t)crap;
но это похоже на то, что вы пытаетесь избежать.
Кажется, что вы пытаетесь сделать, это удалить оператор модуля, поскольку для этого требуется деление, а деление является самой дорогостоящей базовой арифметической операцией. Я вообще не думал бы об этом как о каком-либо узком месте, поскольку любой «интеллектуальный» компилятор (даже в режиме отладки) «оптимизировал бы» его для:
base_num = crap & 0xFF;
на поддерживаемой платформе (каждый основной процессор, о котором я слышал — x86, AMD64, ARM, MIPS), который должен быть любым. Я был бы ошеломлен, услышав о процессоре, который не имеет базовых арифметических инструкций AND и OR.
detector