Действительно ли умножение и деление с использованием операторов сдвига в C быстрее?

Краткий ответ: вряд ли.

Длинный ответ: в вашем компиляторе есть оптимизатор, который знает, как умножать так быстро, как это позволяет архитектура вашего целевого процессора. Лучше всего четко сообщить компилятору о ваших намерениях (т.е. i * 2, а не i ‹---------------- 1) и позволить ему решить, какая последовательность сборки / машинного кода самая быстрая. Возможно даже, что сам процессор реализовал инструкцию умножения как последовательность сдвигов и сложений в микрокоде.

Итог - не тратьте много времени на беспокойство об этом. Если вы хотите сменить, смените. Если вы хотите умножать, умножайте. Делайте то, что семантически наиболее понятно - ваши коллеги поблагодарят вас позже. Или, что более вероятно, проклянет вас позже, если вы поступите иначе.

Просто конкретная точка измерения: много лет назад я протестировал две версии своего алгоритма хеширования:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

а также

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

На каждой машине, на которой я тестировал его, первая была не менее быстрой, чем вторая. Несколько удивительно, но иногда это было быстрее (например, на Sun Sparc). Когда оборудование не поддерживало быстрое умножение (а в то время большинство из них не поддерживало), компилятор преобразовывал умножение в соответствующие комбинации сдвигов и сложения / подмножества. И поскольку он знал конечную цель, он иногда мог сделать это с меньшим количеством инструкций, чем когда вы явно писали сдвиги и добавления / подписки.

Обратите внимание, что это было примерно 15 лет назад. Надеюсь, с тех пор компиляторы стали только лучше, так что вы можете в значительной степени рассчитывать на то, что компилятор будет делать правильные вещи, возможно, лучше, чем вы. (Кроме того, причина, по которой код выглядит так C'ish, заключается в том, что он был написан более 15 лет назад. Я бы, очевидно, использовал std::string и итераторы сегодня.)

В дополнение ко всем другим хорошим ответам позвольте мне указать еще одну причину не использовать сдвиг, когда вы имеете в виду деление или умножение. Я ни разу не видел, чтобы кто-то вводил ошибку, забывая об относительном приоритете умножения и сложения. Я видел ошибки, возникающие, когда программисты по обслуживанию забывали, что «умножение» с помощью сдвига логически является умножением, но не синтаксически того же приоритета, что и умножение. x * 2 + z и x << 1 + z очень разные!

Если вы работаете с числами, используйте арифметические операторы, такие как + - * / %. Если вы работаете с массивами битов, используйте операторы перестановки битов, такие как & ^ | >>. Не смешивайте их; выражение, которое имеет как битовую перестановку, так и арифметику, является ошибкой, ожидающей своего появления.

Это зависит от процессора и компилятора. Некоторые компиляторы уже оптимизируют код таким образом, другие - нет. Поэтому вам нужно проверять каждый раз, когда ваш код нужно оптимизировать таким образом.

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

На самом ли деле быстрее использовать say (i ‹< 3) + (i ‹< 1) для умножения на 10, чем использовать i * 10 напрямую?

Он может быть, а может и не быть на вашем компьютере - если вам интересно, измерьте его в реальном мире.

Пример использования - от 486 до Core i7

Сравнительный анализ очень сложно провести осмысленно, но мы можем взглянуть на несколько фактов. Из http://www.penguin.cz/~literakl/intel/s.html#SAL и http://www.penguin.cz/~literakl/intel/i.html#IMUL мы получаем представление о тактах x86, необходимых для арифметического сдвига и умножения. Скажем, мы придерживаемся «486» (самый новый из перечисленных), 32-битных регистров и немедленных, IMUL занимает 13-42 цикла, а IDIV 44. Каждая SAL занимает 2, добавляя 1, так что даже с некоторыми из них, сдвигающимися вместе, внешне выглядит как победитель.

В наши дни с Core i7:

(из http://software.intel.com/en-us/forums/showthread.php?t=61481)

Задержка составляет 1 цикл для целочисленного сложения и 3 цикла для целочисленного умножения. Вы можете найти информацию о задержках и пропускной способности в Приложении C «Справочного руководства по оптимизации архитектур Intel® 64 и IA-32», которое находится по адресу http://www.intel.com/products/processor/manuals./.

(из рекламного объявления Intel)

Используя SSE, Core i7 может одновременно выдавать инструкции сложения и умножения, в результате чего максимальная скорость составляет 8 операций с плавающей запятой (FLOP) за такт.

Это дает вам представление о том, как далеко все зашло. Мелочи оптимизации - например, сдвиг бит по сравнению с *, которые воспринимались серьезно даже в 90-е годы, сейчас просто устарели. Битовый сдвиг все еще быстрее, но для множителей без степени двойки к тому времени, когда вы сделаете все свои сдвиги и добавите результаты, он снова станет медленнее. Затем, чем больше инструкций, тем больше ошибок кеша, больше потенциальных проблем с конвейерной обработкой, больше использования временных регистров может означать большее сохранение и восстановление содержимого регистров из стека ... быстро становится слишком сложно количественно оценить все воздействия окончательно, но они преимущественно отрицательный.

функциональность в исходном коде против реализации

В общем, ваш вопрос помечен как C и C ++. Как языки третьего поколения, они специально разработаны, чтобы скрыть детали базового набора инструкций ЦП. Чтобы соответствовать стандартам своего языка, они должны поддерживать операции умножения и сдвига (и многие другие) , даже если базовое оборудование не поддерживает. В таких случаях они должны синтезировать требуемый результат, используя множество других инструкций. Точно так же они должны обеспечивать программную поддержку операций с плавающей запятой, если она отсутствует в ЦП и нет FPU. Все современные процессоры поддерживают * и <<, поэтому это может показаться абсурдным теоретическим и историческим, но важно то, что свобода выбора реализации идет в обоих направлениях: даже если у ЦП есть инструкция, которая реализует операцию, запрошенную в исходном коде в В общем случае компилятор может выбрать что-то еще, что он предпочитает, потому что это лучше для конкретного случая, с которым компилятор сталкивается.

Примеры (с гипотетическим языком ассемблера)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Такие инструкции, как эксклюзивное или (xor) не имеют отношения к исходному коду, но xor-ing что-либо с собой очищает все биты, поэтому его можно использовать для установки чего-либо в 0. Исходный код, который подразумевает адреса памяти, может не повлечь за собой использование каких-либо .

Такого рода взломы использовались с тех пор, как появились компьютеры. На заре существования 3GL, чтобы обеспечить понимание разработчиками, выходные данные компилятора должны были удовлетворять потребности существующего хардкорного разработчика, оптимизирующего язык ассемблера вручную. сообществу, что созданный код не был медленнее, многословнее или хуже. Компиляторы быстро внедрили множество отличных оптимизаций - они стали лучшим централизованным хранилищем, чем мог бы быть любой отдельный программист на языке ассемблера, хотя всегда есть шанс, что они пропустят конкретную оптимизацию, которая имеет решающее значение в конкретном случае - люди иногда могут заткнись и ищи что-нибудь получше, в то время как компиляторы просто делают то, что им говорят, пока кто-нибудь не вернет им этот опыт.

Таким образом, даже если смещение и добавление все еще быстрее на каком-то конкретном оборудовании, то разработчик компилятора, вероятно, сработал именно тогда, когда это безопасно и полезно.

Ремонтопригодность

Если ваше оборудование изменится, вы можете перекомпилировать, и он посмотрит на целевой ЦП и сделает другой лучший выбор, в то время как вы вряд ли когда-нибудь захотите пересмотреть свои «оптимизации» или перечислить, какие среды компиляции должны использовать умножение, а какие должны измениться. Подумайте обо всех «оптимизациях» с битовым сдвигом, не использующих степень двойки, написанных более 10 лет назад, которые теперь замедляют код, в котором они находятся, поскольку он выполняется на современных процессорах ...!

К счастью, хорошие компиляторы, такие как GCC, обычно могут заменить серию битовых сдвигов и арифметики прямым умножением, когда включена какая-либо оптимизация (например, ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax), поэтому перекомпиляция может помочь даже без исправления кода, но это не гарантируется.

Странный код сдвига битов, реализующий умножение или деление, гораздо менее выразит то, что вы концептуально пытались достичь, поэтому другие разработчики будут сбиты с толку этим, а сбитый с толку программист с большей вероятностью внесет ошибки или удалит что-то важное, чтобы восстановить кажущееся здравомыслие. Если вы делаете неочевидные вещи только тогда, когда они действительно ощутимо полезны, а затем хорошо их документируете (но в любом случае не документируете другие интуитивно понятные вещи), все будут счастливы.

Общие решения против частичных решений

Если у вас есть дополнительные знания, например, что ваш int на самом деле будет хранить только значения x, y и z, тогда вы сможете разработать некоторые инструкции, которые работают для этих значений и получить результат быстрее, чем когда компилятор не обладает таким пониманием и нуждается в реализации, которая работает для всех int значений. Например, рассмотрим свой вопрос:

Умножение и деление можно выполнить с помощью битовых операторов ...

Вы иллюстрируете умножение, но как насчет деления?

int x;
x >> 1;   // divide by 2?

Согласно стандарту C ++ 5.8:

-3- Значение E1 >> E2 - это битовые позиции E2 со сдвигом вправо E1. Если E1 имеет беззнаковый тип или если E1 имеет знаковый тип и неотрицательное значение, значение результата представляет собой целую часть частного от E1, деленного на количество 2, возведенное в степень E2. Если E1 имеет тип со знаком и отрицательное значение, результирующее значение определяется реализацией.

Итак, ваш битовый сдвиг имеет результат, определенный реализацией, когда x отрицательно: он может работать по-разному на разных машинах. Но / работает гораздо более предсказуемо. (Это также может быть не идеально согласованным, поскольку разные машины могут иметь разные представления отрицательных чисел и, следовательно, разные диапазоны, даже если есть одно и то же число битов, составляющих представление.)

Вы можете сказать: «Меня не волнует ... что int хранит возраст сотрудника, он никогда не может быть отрицательным». Если у вас есть такое особое понимание, тогда да - ваша >> безопасная оптимизация может быть проигнорирована компилятором, если вы явно не сделаете это в своем коде. Но это рискованно и редко полезно, поскольку большую часть времени у вас не будет такого понимания, и другие программисты, работающие над тем же кодом, не будут знать, что вы поставили дом на некоторые необычные ожидания в отношении данных, которые вы будете обрабатывать ... то, что кажется им полностью безопасным, может иметь неприятные последствия из-за вашей "оптимизации".

Есть ли какие-то данные, которые нельзя умножить или разделить таким образом?

Да ... как упоминалось выше, отрицательные числа имеют поведение, определяемое реализацией, когда они «делятся» битовым сдвигом.

Просто попробовал на моей машине скомпилировать это:

int a = ...;
int b = a * 10;

При разборке выдает вывод:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Эта версия быстрее, чем ваш код, оптимизированный вручную, с чистым сдвигом и сложением.

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

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

На самом деле трюк с делением, известный как «волшебное деление», действительно может принести огромные выгоды. Опять же, вы должны сначала профилировать, чтобы увидеть, нужно ли это. Но если вы все же используете его, есть полезные программы, которые помогут вам выяснить, какие инструкции необходимы для той же семантики деления. Вот пример: http://www.masm32.com/board/index.php?topic=12421.0

Пример, который я взял из ветки OP на MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Сгенерирует:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

Инструкции сдвига и целочисленного умножения имеют одинаковую производительность на большинстве современных процессоров - инструкции целочисленного умножения были относительно медленными в 1980-х годах, но в целом это уже не так. Инструкции целочисленного умножения могут иметь более высокую задержку, поэтому все же могут быть случаи, когда сдвиг предпочтительнее. То же самое для случаев, когда вы можете держать больше исполнительных модулей занятыми (хотя это может быть обоюдоострым).

Однако целочисленное деление все еще относительно медленное, поэтому использование сдвига вместо деления на степень 2 по-прежнему является преимуществом, и большинство компиляторов будут реализовывать это как оптимизацию. Однако обратите внимание, что для того, чтобы эта оптимизация была действительной, дивиденд должен быть либо беззнаковым, либо положительным. Для отрицательного дивиденда сдвиг и деление не эквивалентны!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Выход:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Поэтому, если вы хотите помочь компилятору, убедитесь, что переменная или выражение в дивиденде явно беззнаковое.

Это полностью зависит от целевого устройства, языка, цели и т. Д.

Хруст пикселей в драйвере видеокарты? Скорее всего, да!

Бизнес-приложение .NET для вашего отдела? Абсолютно нет причин даже заглядывать в это.

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

Не делайте этого, если в этом нет крайней необходимости, и ваше намерение кода требует сдвига, а не умножения / деления.

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

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

Насколько я знаю, в некоторых машинах для умножения может потребоваться от 16 до 32 машинных циклов. Итак, Да, в зависимости от типа машины, операторы битового сдвига быстрее, чем умножение / деление.

Однако на некоторых машинах есть математический процессор, который содержит специальные инструкции для умножения / деления.

Я согласен с отмеченным ответом Дрю Холла. Однако для ответа могут потребоваться некоторые дополнительные примечания.

Для подавляющего большинства разработчиков программного обеспечения процессор и компилятор больше не имеют отношения к вопросу. Большинство из нас далеко за пределами 8088 и MS-DOS. Возможно, это актуально только для тех, кто все еще разрабатывает для встраиваемых процессоров ...

В моей компании-разработчике программного обеспечения Math (add / sub / mul / div) следует использовать для всей математики. Хотя Shift следует использовать при преобразовании между типами данных, например. ushort до байта как n >> 8 и not n / 256.

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

Тест Python, выполняющий одно и то же умножение 100 миллионов раз на одни и те же случайные числа.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Таким образом, при выполнении сдвига, а не умножения / деления на степень двойки в python, есть небольшое улучшение (~ 10% для деления; ~ 1% для умножения). Если это не степень двойки, скорее всего, произойдет значительное замедление.

Опять же, эти # будут меняться в зависимости от вашего процессора, вашего компилятора (или интерпретатора - для простоты в python).

Как и все остальные, не оптимизируйте преждевременно. Напишите очень читаемый код, профилируйте, если он недостаточно быстрый, а затем попробуйте оптимизировать медленные части. Помните, что ваш компилятор лучше вас оптимизирует.

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

Ниже приведен пример кода C ++, который может выполнять более быстрое деление, выполняя 64-битное «Умножение на обратное». И числитель, и знаменатель должны быть ниже определенного порога. Обратите внимание, что он должен быть скомпилирован для использования 64-битных инструкций, чтобы на самом деле он был быстрее обычного деления.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}

Я думаю, что в одном случае, когда вы хотите умножить или разделить на степень двойки, вы не ошибетесь, используя операторы битового сдвига, даже если компилятор преобразует их в MUL / DIV, потому что микрокод некоторых процессоров (на самом деле, макрос) их в любом случае, поэтому в этих случаях вы добьетесь улучшения, особенно если сдвиг больше 1. Или, более явно, если ЦП не имеет операторов битового сдвига, в любом случае это будет MUL / DIV, но если ЦП имеет Операторы битового сдвига, вы избегаете ветвления микрокода, и это на несколько инструкций меньше.

Я пишу код прямо сейчас, который требует большого количества операций удвоения / деления пополам, потому что он работает с плотным двоичным деревом, и есть еще одна операция, которая, как я подозреваю, может быть более оптимальной, чем сложение - левая (степень двойного умножения ) сдвиг с добавлением. Это можно заменить левым сдвигом и xor, если сдвиг шире, чем количество бит, которое вы хотите добавить, простой пример: (i ‹* 1) ^ 1, который добавляет единицу к удвоенному значению. Это, конечно, не относится к сдвигу вправо (степень двойного деления), потому что только сдвиг влево (с прямым порядком байтов) заполняет пробел нулями.

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

Кроме того, в алгоритмах, которые я пишу, они визуально представляют происходящие движения, поэтому в этом смысле они на самом деле более четкие. Левая часть двоичного дерева больше, а правая меньше. Кроме того, в моем коде нечетные и четные числа имеют особое значение, и все левые дочерние элементы в дереве являются нечетными, а все правые дочерние элементы и корень - четными. В некоторых случаях, с которыми я еще не сталкивался, но может, на самом деле, я даже не думал об этом, x & 1 может быть более оптимальной операцией по сравнению с x% 2. x & 1 для четного числа даст ноль, но даст 1 для нечетного числа.

Если пойти немного дальше, чем просто идентификация нечетного / четного, если я получу ноль для x и 3, я знаю, что 4 является фактором нашего числа, и то же самое для x% 7 для 8 и так далее. Я знаю, что эти случаи, вероятно, имеют ограниченную полезность, но приятно знать, что вы можете избежать операции модуля и использовать вместо нее побитовую логическую операцию, потому что побитовые операции почти всегда самые быстрые и с меньшей вероятностью будут неоднозначными для компилятора.

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

Будет ли это на самом деле быстрее, зависит от используемого оборудования и компилятора, фактически.

Если вы сравните вывод для синтаксиса x + x, x * 2 и x ‹< 1 на компиляторе gcc, то вы получите тот же результат в сборке x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

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

Я тоже хотел посмотреть, смогу ли я победить дом. это более общий побитовый метод для любого числа путем умножения любого числа. макросы, которые я сделал, примерно на 25% больше или вдвое медленнее, чем обычное умножение *. как говорят другие, если он близок к кратному 2 или состоит из нескольких кратных 2, вы можете выиграть. как X * 23, состоящий из (X ‹* 4) + (X ‹* 2) + (X ‹* 1) + X, будет медленнее, чем X * 65, состоящий из (X ‹* 6) + X.

#include <stdio.h>
#include <time.h>

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}