Деление

Не во всех процессорах имеются инструкции для выполнения операций деления. Например, их нет в Cortex-M0. Поэтому часто вместо этого компилятор реализует деление путем вызова кода из стандартной библиотеки. В зависимости от реализации и типов входных данных такая операция может занять до 100 тактов. Следовательно, там, где возможно, лучше избегать операций / и %. Так или иначе, деление чисел на константу может быть эффективно переписано.

В книге «Алгоритмические трюки для программистов» Генри Уоррена-младшего (Hacker’s Delight, Henry S. Warren Jr.) есть целая глава, посвящённая делению целочисленных переменных.

Допустим, нам нужно отобразить число, состоящее из трех разрядов, на семисегментном дисплее. Тривиальное решение будет выглядеть примерно так:

void get_digits(uint32_t value, uint8_t *digits) {
    digits[2] = value % 10;
    value /= 10;
    digits[1] = value % 10;
    value /= 10;
    digits[0] = value;
}

Более эффективно эту же функцию можно записать так:

void get_digits(uint32_t value, uint8_t *digits) {
    digits[0] = value / 100;
    value -= digits[0] * 100;
    digits[1] = value / 10;
    value -= digits[1] * 10U;
    digits[2] = value;
}

Или другой пример. Циклический буфер — часто использующаяся программистами структура, при реализации которой требуется операция деления с остатком. Допустим, размер хранится в buffer_size, а позиция в буфере — это offset, тогда:

offset = (offset + increment) % buffer_size;

Такую запись лучше заменить на следующую:

offset += increment
if (offset >= buffer_size) {
    offset -= buffer_size;
}

Если без деления не обойтись, стоит использовать беззнаковые переменные, так как при делении компилятор получает абсолютные значения из знаковых, а затем переходит к делению беззнаковых чисел. Знак результата определяется в конце.

Другим популярным «хаком» является замена на побитовое смещение, когда деление производится на степени двойки.

// a == 8;
a /= 2;
// a == 4

Более эффективная запись:

// a == 0b 0000 1000
a >>= 2;
// a == 0b 0000 0100

Изменено: