Что самый быстрый путь состоит в том, чтобы разделить целое число на 3?

См. , Как Разделиться На 3 для расширенного обсуждения более эффективно деления на 3, сфокусированный на выполнении арифметических операций FPGA.

Также релевантный:

• Оптимизирующие целочисленные подразделения с Умножаются, Переключают C#

В зависимости от Вашей платформы и в зависимости от Вашего компилятора C, встроенное решение как просто использование

y = x / 3

Может быть быстрым, или это может быть ужасно медленно (даже если подразделение сделано полностью в аппаратных средствах, если это сделано с помощью инструкции по DIV, эта инструкция приблизительно в 3 - 4 раза медленнее, чем умножение на современных центральных процессорах). Очень хорошие компиляторы C с включенными флагами оптимизации могут оптимизировать эту операцию, но если Вы хотите быть уверенными, Вы - более обеспеченная оптимизация ее сами.

Для оптимизации важно иметь целые числа известного размера. В интервале C не имеет никакого известного размера (он может варьироваться платформой и компилятором!), таким образом, Вы лучше используете целые числа фиксированного размера C99. Код ниже предполагает, что Вы хотите разделить неподписанное 32-разрядное целое число на три и что Вы компилятор C знаете целые числа на приблизительно 64 бита ( ПРИМЕЧАНИЕ: Даже на архитектуре ЦП на 32 бита большинство компиляторов C может обработать целые числа на 64 бита очень хорошо ):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

Столь сумасшедший, как это могло бы звучать, но метод выше действительно делится на 3. Все, в чем требуется для того, чтобы сделать так, является единственным умножением на 64 бита и сдвигом (как, я сказал, умножение могло бы быть в 3 - 4 раза быстрее, чем подразделения на Вашем ЦП). В приложении на 64 бита этот код будет намного быстрее, чем в приложении на 32 бита (в приложении на 32 бита, умножающем два числа на 64 бита, берут 3 умножения и 3 дополнения на 32 битовых значениях) - однако, это могло бы быть еще быстрее, чем подразделение на машине на 32 бита.

, С другой стороны, если Ваш компилятор является очень хорошим и знает прием, как оптимизировать целочисленное деление на константу (последний GCC делает, я просто проверил), это генерирует код выше так или иначе (GCC создаст точно этот код для "/3" при включении, по крайней мере, уровня 1 оптимизации). Для других компиляторов... Вы не можете положиться или ожидать, что это будет использовать приемы как этот, даже при том, что этот метод очень хорошо документируется и упоминается везде в Интернете.

проблема состоит в том, что это только работает на постоянные числа, не на переменные. Всегда необходимо знать магическое число (здесь 0xAAAAAAAB) и корректные операции после умножения (сдвиги и/или дополнения в большинстве случаев), и оба отличаются в зависимости от числа, на которое Вы хотите разделиться, и оба занимают слишком много процессорного времени для вычисления их на лету (который был бы медленнее, чем аппаратное деление). Однако для компилятора легко вычислить их в течение времени компиляции (где одно второе более или менее время компиляции играет едва роль).

Я не знаю, быстрее ли это, но если Вы хотите использовать побитовый оператор для выполнения двоичного деления, можно использовать сдвиг и вычесть метод, описанный в эта страница :

• частное Набора к 0
• Выравнивают крайние левые цифры в дивиденде и делителе
• Повторение:
  • , Если та часть дивиденда выше делителя больше, чем или равна делителю:
    <литий> Тогда Еще вычитают делитель из той части дивиденда и <литий> Concatentate 1 к правому концу частного <литий> concatentate 0 к правому концу частного Сдвиг
  • делитель одно право места
• , Пока дивиденд не является меньше, чем делитель:
• частное корректно, дивиденд является остатком
• ОСТАНОВКА

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

Что если вы действительно не хотите ни умножать, ни делить? Вот пример, который я только что придумал. Это работает, потому что (x / 3) = (x / 4) + (x / 12). Но поскольку (x / 12) = (x / 4) / 3, нам просто нужно повторять процесс до тех пор, пока он не станет достаточно хорошим.

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

Результат 330. Его можно было бы сделать более точным, используя b = ((b + 2) >> 2); для учета округления.

Если вам разрешено умножать, просто выберите подходящее приближение для (1/3) с делителем степени двойки. Например, n * (1/3) ~ = n * 43/128 = (n * 43) >> 7.

Этот метод наиболее полезен в Индиане.