A multiplicação e a divisão usando operadores de turno em C são realmente mais rápidas?

A multiplicação e a divisão podem ser obtidas usando operadores de bits, por exemplo

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

e assim por diante.

É realmente mais rápido usar o say (i<<3)+(i<<1)para multiplicar por 10 do que usar i*10diretamente? Existe algum tipo de entrada que não possa ser multiplicada ou dividida dessa maneira?

Resposta curta: improvável.

Resposta longa: Seu compilador possui um otimizador que sabe como multiplicar tão rapidamente quanto a arquitetura do processador de destino. Sua melhor aposta é informar claramente ao seu compilador sua intenção (ou seja, i * 2 em vez de i << 1) e deixar que ele decida qual é a sequência de código de montagem / máquina mais rápida. É até possível que o próprio processador tenha implementado a instrução de multiplicação como uma sequência de turnos e acréscimos no microcódigo.

Conclusão - não gaste muito tempo se preocupando com isso. Se você quer mudar, mude. Se você deseja multiplicar, multiplique. Faça o que é semanticamente mais claro - seus colegas de trabalho agradecerão mais tarde. Ou, mais provavelmente, amaldiçoá-lo mais tarde, se você fizer o contrário.

Apenas um ponto de medida concreto: muitos anos atrás, eu comparei duas versões do meu algoritmo de hash:

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

e

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

Em todas as máquinas em que eu comparava, a primeira era pelo menos tão rápida quanto a segunda. Surpreendentemente, às vezes era mais rápido (por exemplo, em um Sun Sparc). Quando o hardware não suportava multiplicação rápida (e a maioria não era na época), o compilador convertia a multiplicação nas combinações apropriadas de turnos e add / sub. E porque sabia o objetivo final, às vezes podia fazê-lo em menos instruções do que quando você escrevia explicitamente os turnos e os add / subs.

Observe que isso foi algo como 15 anos atrás. Felizmente, os compiladores só ficaram melhores desde então, então você pode contar com o compilador fazendo a coisa certa, provavelmente melhor do que você poderia. (Além disso, a razão pela qual o código parece tão C'ish é porque era há mais de 15 anos. Eu obviamente usaria std::stringe iteradores hoje.)

Além de todas as outras boas respostas aqui, deixe-me apontar outro motivo para não usar turno quando você quer dizer dividir ou multiplicar. Nunca vi alguém introduzir um bug esquecendo a relativa precedência da multiplicação e adição. Vi bugs introduzidos quando os programadores de manutenção esqueceram que "multiplicar" por meio de um turno é logicamente uma multiplicação, mas não sintaticamente da mesma precedência que a multiplicação. x * 2 + ze x << 1 + zsão muito diferentes!

Se você estiver trabalhando em números , use operadores aritméticos como + - * / %. Se você estiver trabalhando em matrizes de bits, use operadores de ajuste de bits como & ^ | >>. Não os misture; uma expressão que tanto modifica como aritmética é um bug que está esperando para acontecer.

Isso depende do processador e do compilador. Alguns compiladores já otimizam o código dessa maneira, outros não. Portanto, você precisa verificar sempre que seu código precisar ser otimizado dessa maneira.

A menos que você precise desesperadamente otimizar, eu não codificaria meu código-fonte apenas para salvar uma instrução de montagem ou um ciclo do processador.

É realmente mais rápido usar say (i << 3) + (i << 1) para multiplicar por 10 do que usar i * 10 diretamente?

Pode ou não estar em sua máquina - se você se importa, meça seu uso no mundo real.

Um estudo de caso - do 486 ao core i7

O benchmarking é muito difícil de ser feito de maneira significativa, mas podemos observar alguns fatos. Em http://www.penguin.cz/~literakl/intel/s.html#SAL e http://www.penguin.cz/~literakl/intel/i.html#IMUL, temos uma idéia dos ciclos do relógio x86 necessário para mudança aritmética e multiplicação. Digamos que aderimos ao "486" (o mais novo listado), registradores e imediatos de 32 bits, o IMUL leva 13-42 ciclos e o IDIV 44. Cada SAL pega 2 e adiciona 1, portanto, mesmo com alguns desses que mudam superficialmente a aparência como um vencedor.

Hoje em dia, com o core i7:

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

A latência é de 1 ciclo para uma adição inteira e 3 ciclos para uma multiplicação inteira . Você pode encontrar as latências e a capacidade de processamento no Apêndice C do "Manual de referência da otimização de arquiteturas Intel® 64 e IA-32", localizado em http://www.intel.com/products/processor/manuals/ .

(de alguns anúncios da Intel)

Usando o SSE, o Core i7 pode emitir instruções simultâneas de adição e multiplicação, resultando em uma taxa de pico de 8 operações de ponto flutuante (FLOP) por ciclo de clock

Isso dá uma idéia de quão longe as coisas chegaram. A trivialidade da otimização - como deslocamento de bits versus* - que foi levada a sério até os anos 90 é obsoleta agora. A troca de bits ainda é mais rápida, mas, para uma potência de dois mul / div, no momento em que você faz todos os seus turnos e adiciona os resultados, é mais lento novamente. Então, mais instruções significam mais falhas de cache, mais problemas em potencial no pipelining, mais uso de registros temporários podem significar mais economia e restauração do conteúdo do registro da pilha ... rapidamente fica muito complicado quantificar definitivamente todos os impactos, mas eles são predominantemente negativo.

funcionalidade no código fonte versus implementação

De maneira mais geral, sua pergunta é marcada como C e C ++. Como linguagens de terceira geração, eles são projetados especificamente para ocultar os detalhes do conjunto de instruções da CPU subjacente. Para satisfazer seus padrões de idioma, eles devem oferecer suporte a operações de multiplicação e deslocamento (e muitas outras), mesmo que o hardware subjacente não o faça . Nesses casos, eles devem sintetizar o resultado necessário usando muitas outras instruções. Da mesma forma, eles devem fornecer suporte de software para operações de ponto flutuante se a CPU não tiver e não houver FPU. CPUs modernas suportam* e<<, portanto, isso pode parecer absurdamente teórico e histórico, mas o importante é que a liberdade de escolher a implementação seja nos dois sentidos: mesmo que a CPU possua uma instrução que implemente a operação solicitada no código-fonte no caso geral, o compilador estará livre para escolha outra coisa que prefira, porque é melhor para o caso específico que o compilador enfrenta.

Exemplos (com uma linguagem de montagem hipotética)

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...............

Instruções como exclusive ou ( xor) não têm relação com o código-fonte, mas armazenar qualquer coisa por si só limpa todos os bits; portanto, pode ser usado para definir algo como 0. O código-fonte que implica endereços de memória pode não implicar o uso.

Esses tipos de hacks são utilizados há tanto tempo quanto os computadores existem. Nos primeiros dias do 3GLs, para garantir a aceitação do desenvolvedor, a saída do compilador tinha que satisfazer o desenvolvedor de linguagem assembly otimizado para mão, já existente. comunidade que o código produzido não era mais lento, mais detalhado ou pior. Os compiladores adotaram rapidamente muitas ótimas otimizações - eles se tornaram um repositório centralizado melhor do que qualquer programador de linguagem assembly poderia ser, embora sempre haja a chance de que eles percam uma otimização específica que é crucial em um caso específico - às vezes os humanos podem enlouqueça e procure algo melhor, enquanto os compiladores fazem o que lhes foi dito até que alguém os devolva a experiência.

Portanto, mesmo que a troca e a adição ainda sejam mais rápidas em algum hardware específico, é provável que o gravador do compilador tenha funcionado exatamente quando é seguro e benéfico.

Manutenção

Se o seu hardware mudar, você poderá recompilar e ele olhará para a CPU de destino e fará outra melhor escolha, enquanto é improvável que você queira revisitar suas "otimizações" ou listar quais ambientes de compilação devem usar multiplicação e quais devem mudar. Pense em todas as "otimizações" sem deslocamento de dois bits, escritas há mais de 10 anos, que agora estão diminuindo o código em que estão, enquanto são executadas nos processadores modernos ...!

Felizmente, bons compiladores como o GCC podem substituir uma série de turnos de bits e aritmética por uma multiplicação direta quando qualquer otimização é ativada (por exemplo, ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax), para que uma recompilação possa ajudar mesmo sem corrigir o código, mas isso não é garantido.

Código estranho de mudança de bits que implementa multiplicação ou divisão é muito menos expressivo do que você estava tentando alcançar conceitualmente; portanto, outros desenvolvedores ficarão confusos com isso, e um programador confuso terá mais chances de introduzir bugs ou remover algo essencial em um esforço para restaurar a aparente sanidade. Se você só faz coisas não óbvias quando elas são realmente benéficas tangíveis e depois as documenta bem (mas não documenta outras coisas que são intuitivas de qualquer maneira), todos ficarão mais felizes.

Soluções gerais versus soluções parciais

Se você tem algum conhecimento extra, tal como a sua intvontade realmente apenas ser armazenar valores x, ye z, em seguida, você pode ser capaz de trabalhar para fora algumas instruções que o trabalho para esses valores e que você obtenha o seu resultado mais rapidamente do que quando o compilador de não ter esse insight e precisa de uma implementação que funcione para todos os intvalores. Por exemplo, considere sua pergunta:

A multiplicação e a divisão podem ser obtidas usando operadores de bits ...

Você ilustra a multiplicação, mas e a divisão?

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

De acordo com o C ++ Standard 5.8:

-3- O valor de E1 >> E2 é E1 com posições de bits E2 deslocadas à direita. Se E1 tiver um tipo não assinado ou E1 tiver um tipo assinado e um valor não negativo, o valor do resultado será a parte integrante do quociente de E1 dividido pela quantidade 2 elevada à potência E2. Se E1 tiver um tipo assinado e um valor negativo, o valor resultante será definido pela implementação.

Portanto, seu deslocamento de bits tem um resultado definido de implementação quando xé negativo: pode não funcionar da mesma maneira em máquinas diferentes. Mas, /funciona muito mais previsivelmente. (Também pode não ser perfeitamente consistente, pois máquinas diferentes podem ter representações diferentes de números negativos e, portanto, intervalos diferentes, mesmo quando há o mesmo número de bits que compõem a representação.)

Você pode dizer "eu não ligo ... isso inté armazenar a idade do funcionário, nunca pode ser negativo". Se você tiver esse tipo de insight especial, sim - sua >>otimização segura pode ser ignorada pelo compilador, a menos que você faça isso explicitamente em seu código. Porém, é arriscado e raramente útil, na maioria das vezes você não terá esse tipo de insight, e outros programadores trabalhando no mesmo código não saberão que você apostou em algumas expectativas incomuns dos dados que você ' vou lidar com ... o que parece uma mudança totalmente segura para eles pode sair pela culatra por causa da sua "otimização".

Existe algum tipo de entrada que não possa ser multiplicada ou dividida dessa maneira?

Sim ... como mencionado acima, os números negativos têm um comportamento definido pela implementação quando "dividido" pela troca de bits.

Apenas tentei na minha máquina compilar isso:

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

Ao desmontar, produz saída:

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

Esta versão é mais rápida que o seu código otimizado para as mãos, com pura mudança e adição.

Você realmente nunca sabe o que o compilador criará, então é melhor simplesmente escrever uma multiplicação normal e deixá-lo otimizar da maneira que ele deseja, exceto em casos muito precisos em que você sabe que o compilador não pode otimizar.

Mudar é geralmente muito mais rápido do que multiplicar em um nível de instrução, mas você pode estar perdendo seu tempo fazendo otimizações prematuras. O compilador pode muito bem executar essas otimizações em tempo de compilação. Fazer você mesmo afetará a legibilidade e possivelmente não terá efeito no desempenho. Provavelmente, só vale a pena fazer coisas assim se você criar um perfil e achar que isso é um gargalo.

Na verdade, o truque da divisão, conhecido como 'divisão mágica', pode realmente render grandes recompensas. Novamente, você deve criar um perfil primeiro para ver se é necessário. Mas se você o usar, existem programas úteis para ajudá-lo a descobrir quais instruções são necessárias para a mesma semântica de divisão. Aqui está um exemplo: http://www.masm32.com/board/index.php?topic=12421.0

Um exemplo que tirei do thread do OP no MASM32:

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

Geraria:

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

As instruções de mudança e multiplicação de números inteiros têm desempenho semelhante na maioria das CPUs modernas - as instruções de multiplicação de números inteiros eram relativamente lentas nos anos 80, mas, em geral, isso não é mais verdade. Instruções de multiplicação de número inteiro podem ter maior latência ; portanto, ainda pode haver casos em que uma mudança é preferível. O mesmo vale para os casos em que você pode manter mais unidades de execução ocupadas (embora isso possa ocorrer nos dois sentidos).

A divisão de números inteiros ainda é relativamente lenta, portanto, usar uma mudança em vez de divisão por uma potência de 2 ainda é uma vitória, e a maioria dos compiladores implementará isso como uma otimização. Observe, no entanto, que para que essa otimização seja válida, o dividendo precisa ser não assinado ou deve ser positivo. Para um dividendo negativo, o deslocamento e a divisão não são equivalentes!

#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;
}

Resultado:

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

Portanto, se você deseja ajudar o compilador, verifique se a variável ou expressão no dividendo está explicitamente sem sinal.

Depende completamente do dispositivo de destino, idioma, finalidade etc.

Trituração de pixels em um driver de placa de vídeo? Muito provavelmente sim!

Aplicativo de negócios .NET para o seu departamento? Absolutamente nenhuma razão para sequer olhar para ele.

Para um jogo de alto desempenho para um dispositivo móvel, pode valer a pena investigar, mas somente após a otimização mais fácil.

Não faça isso, a menos que seja absolutamente necessário e sua intenção de código exija mudança em vez de multiplicação / divisão.

Em um dia típico - você pode economizar potencialmente poucos ciclos de máquina (ou menos, já que o compilador sabe melhor o que otimizar), mas o custo não vale a pena - você gasta tempo com pequenos detalhes em vez de trabalhos reais, mantendo o código mais difícil e seus colegas de trabalho o amaldiçoarão.

Pode ser necessário fazer isso para cálculos de alta carga, em que cada ciclo salvo significa minutos de tempo de execução. Porém, você deve otimizar um local de cada vez e fazer testes de desempenho a cada vez para ver se realmente tornou mais rápido ou quebrou a lógica dos compiladores.

Tanto quanto sei em algumas máquinas, a multiplicação pode precisar de 16 a 32 ciclos de máquina. Portanto , sim , dependendo do tipo de máquina, os operadores de deslocamento de bits são mais rápidos que a multiplicação / divisão.

No entanto, certas máquinas possuem seu processador matemático, que contém instruções especiais para multiplicação / divisão.

Concordo com a resposta marcada por Drew Hall. A resposta pode usar algumas notas adicionais.

Para a grande maioria dos desenvolvedores de software, o processador e o compilador não são mais relevantes para a questão. A maioria de nós está muito além do 8088 e do MS-DOS. Talvez seja relevante apenas para aqueles que ainda estão desenvolvendo para processadores embarcados ...

Na minha empresa de software, Math (add / sub / mul / div) deve ser usado para toda a matemática. Enquanto Shift deve ser usado ao converter entre tipos de dados, por exemplo. ushort para byte como n >> 8 e não n / 256.

No caso de números inteiros assinados e deslocamento à direita x divisão, isso pode fazer a diferença. Para números negativos, o turno arredonda para o infinito negativo, enquanto a divisão arredonda para o zero. É claro que o compilador mudará a divisão para algo mais barato, mas geralmente mudará para algo que tenha o mesmo comportamento de arredondamento da divisão, porque é incapaz de provar que a variável não será negativa ou simplesmente não Cuidado. Portanto, se você puder provar que um número não será negativo ou se não se importar com a maneira como ele arredondará, poderá fazer essa otimização de uma maneira que seja mais provável que faça a diferença.

Teste Python executando a mesma multiplicação 100 milhões de vezes contra os mesmos números aleatórios.

>>> 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

Portanto, ao fazer uma mudança em vez de multiplicar / divisão por uma potência de dois em python, há uma ligeira melhora (~ 10% para divisão; ~ 1% para multiplicação). Se não for dois, provavelmente haverá uma desaceleração considerável.

Novamente, esses #s mudam dependendo do seu processador, compilador (ou intérprete - feito em python por simplicidade).

Como com todos os outros, não otimize prematuramente. Escreva um código muito legível, crie um perfil, se não for rápido o suficiente, e tente otimizar as partes lentas. Lembre-se de que seu compilador é muito melhor em otimização do que você.

Existem otimizações que o compilador não pode fazer porque elas funcionam apenas para um conjunto reduzido de entradas.

Abaixo, há um código de exemplo c ++ que pode fazer uma divisão mais rápida executando uma "Multiplicação pelo inverso" de 64 bits. O numerador e o denominador devem estar abaixo de determinado limite. Observe que ele deve ser compilado para usar instruções de 64 bits para ser realmente mais rápido que a divisão normal.

#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;
}

Eu acho que, no caso em que você deseja multiplicar ou dividir por uma potência de dois, você não pode errar ao usar operadores de deslocamento de bits, mesmo que o compilador os converta em um MUL / DIV, porque alguns processadores microcódigo (na verdade, um macro) de qualquer maneira, portanto, nesses casos, você obterá uma melhoria, especialmente se o deslocamento for maior que 1. Ou mais explicitamente, se a CPU não tiver operadores de deslocamento de bits, será um MUL / DIV de qualquer maneira, mas se a CPU tiver operadores de deslocamento de bits, você evita uma ramificação de microcódigo e estas são algumas instruções a menos.

Estou escrevendo algum código agora que requer muitas operações de duplicação / redução pela metade porque está trabalhando em uma árvore binária densa, e há mais uma operação que eu suspeito que possa ser mais ideal do que uma adição - uma esquerda (potência de duas multiplique ) mudar com uma adição. Isso pode ser substituído por um deslocamento à esquerda e um xor se o deslocamento for maior que o número de bits que você deseja adicionar; o exemplo fácil é (i << 1) ^ 1, que adiciona um a um valor dobrado. Obviamente, isso não se aplica a um deslocamento à direita (potência de duas divisões) porque apenas um deslocamento à esquerda (little endian) preenche a lacuna com zeros.

No meu código, essas multiplicações / divisões por duas e potências de duas operações são usadas intensivamente e, como as fórmulas já são bastante curtas, cada instrução que pode ser eliminada pode ser um ganho substancial. Se o processador não suportar esses operadores de deslocamento de bits, nenhum ganho ocorrerá, mas também não haverá perda.

Além disso, nos algoritmos que estou escrevendo, eles representam visualmente os movimentos que ocorrem e, nesse sentido, são de fato mais claros. O lado esquerdo de uma árvore binária é maior e o direito é menor. Além disso, no meu código, os números pares e ímpares têm um significado especial, e todos os filhos da esquerda na árvore são ímpares e todos os filhos da mão direita e a raiz são pares. Em alguns casos, que eu ainda não encontrei, mas talvez não tenha pensado nisso, x & 1 pode ser uma operação mais ideal em comparação com x% 2. x e 1 em um número par produzirão zero, mas produzirão 1 para um número ímpar.

Indo um pouco além da identificação ímpar / par, se eu receber zero para x e 3, sei que 4 é um fator do nosso número e o mesmo para x% 7 para 8 e assim por diante. Sei que esses casos provavelmente têm utilidade limitada, mas é bom saber que você pode evitar uma operação de módulo e usar uma operação lógica bit a bit, porque as operações bit a bit são quase sempre as mais rápidas e com menor probabilidade de serem ambíguas para o compilador.

Estou inventando praticamente o campo de árvores binárias densas, por isso espero que as pessoas não compreendam o valor desse comentário, pois muito raramente as pessoas querem apenas executar fatorações com apenas potências de dois ou apenas multiplicar / dividir potências de duas.

Se é realmente mais rápido depende do hardware e compilador realmente usado.

Se você comparar a saída para a sintaxe x + x, x * 2 e x << 1 em um compilador gcc, obterá o mesmo resultado no assembly 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

Portanto, você pode considerar o gcc suficientemente inteligente para determinar sua melhor solução independentemente do que você digitou.

Eu também queria ver se eu poderia bater a casa. este é um bit a bit mais geral para qualquer número por qualquer multiplicação de números. as macros que fiz são cerca de 25% a mais que o dobro da multiplicação normal *. como dito por outros, se for próximo de um múltiplo de 2 ou composto de poucos múltiplos de 2, você poderá ganhar. como X * 23 composto por (X << 4) + (X << 2) + (X << 1) + X será mais lento que X * 65 composto por (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;
}