La multiplication et la division utilisant des opérateurs de décalage en C sont-elles réellement plus rapides?

La multiplication et la division peuvent être réalisées en utilisant des opérateurs de bits, par exemple

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

etc.

Est-il réellement plus rapide d'utiliser disons (i<<3)+(i<<1)pour multiplier par 10 que d'utiliser i*10directement? Y a-t-il une sorte d'entrée qui ne peut pas être multipliée ou divisée de cette façon?

Réponse courte: peu probable.

Réponse longue: votre compilateur contient un optimiseur qui sait se multiplier aussi rapidement que votre architecture de processeur cible est capable. Votre meilleur pari est de dire clairement au compilateur votre intention (c'est-à-dire i * 2 plutôt que i << 1) et de le laisser décider quelle est la séquence de code assembleur / machine la plus rapide. Il est même possible que le processeur lui-même ait implémenté l'instruction multiply comme une séquence de décalages et d'ajouts dans le microcode.

Conclusion - ne passez pas beaucoup de temps à vous en préoccuper. Si vous voulez changer, changez. Si vous voulez multiplier, multipliez. Faites ce qui est sémantiquement le plus clair - vos collègues vous remercieront plus tard. Ou, plus probablement, vous maudire plus tard si vous faites autrement.

Juste un point de mesure concret: il y a de nombreuses années, j'ai comparé deux versions de mon algorithme de hachage:

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

et

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

Sur chaque machine sur laquelle je l'ai comparé, la première était au moins aussi rapide que la seconde. Quelque peu surprenant, il était parfois plus rapide (par exemple sur un Sun Sparc). Lorsque le matériel ne prend pas en charge la multiplication rapide (et la plupart ne le font pas à l'époque), le compilateur convertit la multiplication dans les combinaisons appropriées de décalages et ajoute / sub. Et parce qu'il connaissait l'objectif final, il pouvait parfois le faire en moins d'instructions que lorsque vous écriviez explicitement les changements et les ajouts / sous-marins.

Notez que c'était quelque chose comme il y a 15 ans. J'espère que les compilateurs ne font que s'améliorer depuis lors, vous pouvez donc à peu près compter sur le compilateur qui fait la bonne chose, probablement mieux que vous. (En outre, la raison pour laquelle le code semble si Cish est parce qu'il était il y a plus de 15 ans. J'utiliserais évidemment std::stringet les itérateurs aujourd'hui.)

En plus de toutes les autres bonnes réponses ici, permettez-moi de souligner une autre raison de ne pas utiliser le décalage lorsque vous entendez diviser ou multiplier. Je n'ai jamais vu quelqu'un introduire un bug en oubliant la priorité relative de la multiplication et de l'addition. J'ai vu des bogues introduits lorsque les programmeurs de maintenance ont oublié que la "multiplication" via un décalage est logiquement une multiplication mais pas syntaxiquement de la même priorité que la multiplication. x * 2 + zet x << 1 + zsont très différents!

Si vous travaillez sur des nombres, utilisez des opérateurs arithmétiques comme + - * / %. Si vous travaillez sur des tableaux de bits, utilisez des opérateurs de torsion de bits comme & ^ | >>. Ne les mélangez pas; une expression qui a à la fois un peu de twiddling et d'arithmétique est un bug qui attend de se produire.

Cela dépend du processeur et du compilateur. Certains compilateurs optimisent déjà le code de cette façon, d'autres non. Vous devez donc vérifier chaque fois que votre code doit être optimisé de cette façon.

À moins que vous ayez désespérément besoin d'optimiser, je ne brouillerais pas mon code source juste pour enregistrer une instruction d'assemblage ou un cycle de processeur.

Est-il réellement plus rapide d'utiliser dis (i << 3) + (i << 1) pour multiplier par 10 que d'utiliser i * 10 directement?

Il peut ou non être sur votre machine - si vous vous en souciez, mesurez dans votre utilisation réelle.

Une étude de cas - de 486 à Core i7

L'analyse comparative est très difficile à faire de manière significative, mais nous pouvons examiner quelques faits. Sur http://www.penguin.cz/~literakl/intel/s.html#SAL et http://www.penguin.cz/~literakl/intel/i.html#IMUL nous avons une idée des cycles d'horloge x86 nécessaire pour le décalage arithmétique et la multiplication. Supposons que nous nous en tenions à "486" (le plus récent répertorié), aux registres 32 bits et aux intermédiaires, IMUL prend 13 à 42 cycles et IDIV 44. Chaque SAL en prend 2 et en ajoute 1, donc même avec quelques-uns d'entre eux, le décalage superficiel semble comme un gagnant.

De nos jours, avec le Core i7:

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

La latence est de 1 cycle pour une addition entière et de 3 cycles pour une multiplication entière . Vous pouvez trouver les latences et le débit dans l'annexe C du "Intel® 64 and IA-32 Architectures Optimization Reference Manual", qui se trouve sur http://www.intel.com/products/processor/manuals/ .

(à partir d'un texte Intel)

À l'aide de SSE, le Core i7 peut émettre des instructions d'ajout et de multiplication simultanées, ce qui entraîne un taux de pointe de 8 opérations à virgule flottante (FLOP) par cycle d'horloge

Cela vous donne une idée du chemin parcouru. Anecdote sur l'optimisation - comme le décalage de bits par rapport* - qui a été pris au sérieux même dans les années 90 est maintenant obsolète. Le décalage de bits est encore plus rapide, mais pour les mul / div sans puissance de deux au moment où vous effectuez tous vos changements et ajoutez les résultats, il est à nouveau plus lent. Ensuite, plus d'instructions signifie plus de défauts de cache, plus de problèmes potentiels dans le pipelining, plus d'utilisation de registres temporaires peut signifier plus de sauvegarde et de restauration du contenu du registre de la pile ... cela devient rapidement trop compliqué pour quantifier définitivement tous les impacts mais ils sont principalement négatif.

fonctionnalité dans le code source vs implémentation

Plus généralement, votre question est balisée C et C ++. En tant que langages de 3e génération, ils sont spécifiquement conçus pour masquer les détails du jeu d'instructions CPU sous-jacent. Pour satisfaire leurs normes linguistiques, ils doivent prendre en charge les opérations de multiplication et de décalage (et bien d'autres), même si le matériel sous-jacent ne le fait pas . Dans de tels cas, ils doivent synthétiser le résultat requis en utilisant de nombreuses autres instructions. De même, ils doivent fournir un support logiciel pour les opérations en virgule flottante si le processeur en manque et qu'il n'y a pas de FPU. Les processeurs modernes prennent tous en charge* et<<, donc cela peut sembler absurdement théorique et historique, mais la chose importante est que la liberté de choisir l'implémentation va dans les deux sens: même si le CPU a une instruction qui implémente l'opération demandée dans le code source dans le cas général, le compilateur est libre de choisissez autre chose qu'il préfère, car c'est mieux pour le cas spécifique auquel le compilateur est confronté.

Exemples (avec un langage d'assemblage hypothétique)

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

Des instructions telles que exclusive ou ( xor) n'ont aucune relation avec le code source, mais tout ce qui est effacé lui-même efface tous les bits, il peut donc être utilisé pour mettre quelque chose à 0. Le code source qui implique des adresses mémoire ne peut impliquer aucune utilisation.

Ce type de piratage est utilisé depuis aussi longtemps que les ordinateurs existent. Dans les premiers jours des 3GL, pour sécuriser l'adoption par les développeurs, la sortie du compilateur devait satisfaire le développeur existant en langage d'assemblage optimisant la main. communauté que le code produit n'était pas plus lent, plus verbeux ou pire. Les compilateurs ont rapidement adopté beaucoup de grandes optimisations - ils en sont devenus un meilleur stockage centralisé que tout programmeur individuel en langage d'assemblage pourrait être, bien qu'il y ait toujours la possibilité qu'ils manquent une optimisation spécifique qui s'avère cruciale dans un cas spécifique - les humains peuvent parfois écraser et tâtonner pour quelque chose de mieux tandis que les compilateurs font juste ce qu'on leur a dit jusqu'à ce que quelqu'un leur fasse revivre cette expérience.

Donc, même si le décalage et l'ajout sont encore plus rapides sur un matériel particulier, le rédacteur du compilateur a probablement fonctionné exactement quand il est à la fois sûr et bénéfique.

Maintenabilité

Si votre matériel change, vous pouvez recompiler et il examinera le processeur cible et fera un autre meilleur choix, alors que vous ne voudrez probablement jamais revoir vos "optimisations" ou répertorier les environnements de compilation qui devraient utiliser la multiplication et ceux qui devraient changer. Pensez à toutes les «optimisations» décalées non-puissance de deux écrites il y a plus de 10 ans qui ralentissent maintenant le code dans lequel il se trouve lorsqu'il fonctionne sur des processeurs modernes ...!

Heureusement, de bons compilateurs comme GCC peuvent généralement remplacer une série de décalages de bits et d'arithmétique par une multiplication directe lorsque toute optimisation est activée (c'est ...main(...) { return (argc << 4) + (argc << 2) + argc; }-à- dire -> imull $21, 8(%ebp), %eax), donc une recompilation peut aider même sans corriger le code, mais ce n'est pas garanti.

Un code de décalage de bits étrange implémentant la multiplication ou la division est beaucoup moins expressif de ce que vous tentiez de réaliser conceptuellement, de sorte que d'autres développeurs seront confus par cela, et un programmeur confus est plus susceptible d'introduire des bogues ou de supprimer quelque chose d'essentiel dans un effort pour restaurer une apparence saine. Si vous ne faites des choses non évidentes que lorsqu'elles sont vraiment tangibles, puis les documentez bien (mais ne documentez pas d'autres choses intuitives de toute façon), tout le monde sera plus heureux.

Solutions générales versus solutions partielles

Si vous avez quelques connaissances supplémentaires, par exemple que votre intvolonté soit vraiment seulement stocker des valeurs x, yet z, alors vous pouvez être en mesure d'élaborer des instructions de travail pour ces valeurs et vous obtenez votre résultat plus rapidement que lorsque n'a pas de compilateur cet aperçu et a besoin d'une mise en œuvre qui fonctionne pour toutes les intvaleurs. Par exemple, considérez votre question:

La multiplication et la division peuvent être réalisées en utilisant des opérateurs de bits ...

Vous illustrez la multiplication, mais qu'en est-il de la division?

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

Selon la norme C ++ 5.8:

-3- La valeur de E1 >> E2 correspond aux positions de bits E2 décalées vers la droite E2. Si E1 a un type non signé ou si E1 a un type signé et une valeur non négative, la valeur du résultat est la partie intégrante du quotient de E1 divisée par la quantité 2 élevée à la puissance E2. Si E1 a un type signé et une valeur négative, la valeur résultante est définie par l'implémentation.

Ainsi, votre décalage de bits a un résultat défini par l'implémentation lorsqu'il xest négatif: il peut ne pas fonctionner de la même manière sur différentes machines. Mais, /fonctionne de manière beaucoup plus prévisible. (Il peut ne pas être parfaitement cohérent non plus, car différentes machines peuvent avoir différentes représentations de nombres négatifs, et donc des plages différentes même lorsqu'il y a le même nombre de bits constituant la représentation.)

Vous pouvez dire "Je m'en fiche ... c'est intmémoriser l'âge de l'employé, ça ne peut jamais être négatif". Si vous avez ce genre d'informations particulières, alors oui - votre >>optimisation sûre peut être ignorée par le compilateur, sauf si vous le faites explicitement dans votre code. Mais, c'est risqué et rarement utile la plupart du temps, vous n'aurez pas ce genre de perspicacité, et les autres programmeurs travaillant sur le même code ne sauront pas que vous avez parié la maison sur des attentes inhabituelles des données que vous '' Je vais gérer ... ce qui semble être un changement totalement sûr pourrait se retourner contre vous à cause de votre "optimisation".

Y a-t-il une sorte d'entrée qui ne peut pas être multipliée ou divisée de cette façon?

Oui ... comme mentionné ci-dessus, les nombres négatifs ont un comportement défini par l'implémentation lorsqu'ils sont "divisés" par décalage de bits.

Je viens d'essayer sur ma machine de compiler ceci:

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

Lors du démontage, il produit une sortie:

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

Cette version est plus rapide que votre code optimisé à la main avec un décalage et un ajout purs.

Vous ne savez jamais vraiment ce que le compilateur va proposer, il est donc préférable d'écrire simplement une multiplication normale et de le laisser optimiser comme il le souhaite, sauf dans des cas très précis où vous savez que le compilateur ne peut pas optimiser.

Le décalage est généralement beaucoup plus rapide que la multiplication au niveau de l'instruction, mais vous perdez peut-être votre temps à faire des optimisations prématurées. Le compilateur peut très bien effectuer ces optimisations au moment de la compilation. Le faire vous-même affectera la lisibilité et n'aura probablement aucun effet sur les performances. Cela vaut probablement la peine de faire des choses comme ça si vous avez profilé et trouvé que c'était un goulot d'étranglement.

En fait, l'astuce de division, connue sous le nom de «division magique», peut en fait générer d'énormes gains. Encore une fois, vous devez d'abord profiler pour voir si cela est nécessaire. Mais si vous l'utilisez, il existe des programmes utiles pour vous aider à comprendre quelles instructions sont nécessaires pour la même sémantique de division. Voici un exemple : http://www.masm32.com/board/index.php?topic=12421.0

Un exemple que j'ai retiré du fil de l'OP sur MASM32:

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

Générerait:

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

Les instructions de décalage et de multiplication d'entiers ont des performances similaires sur la plupart des processeurs modernes - les instructions de multiplication d'entiers étaient relativement lentes dans les années 1980, mais en général, ce n'est plus le cas. Les instructions de multiplication d'entiers peuvent avoir une latence plus élevée , il peut donc toujours y avoir des cas où un décalage est préférable. Idem pour les cas où vous pouvez occuper plus d'unités d'exécution (même si cela peut aller dans les deux sens).

La division entière est encore relativement lente, donc utiliser un décalage au lieu de la division par une puissance de 2 est toujours une victoire, et la plupart des compilateurs implémenteront cela comme une optimisation. Notez cependant que pour que cette optimisation soit valide, le dividende doit être non signé ou doit être connu pour être positif. Pour un dividende négatif, le décalage et la division ne sont pas équivalents!

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

Production:

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

Donc, si vous voulez aider le compilateur, assurez-vous que la variable ou l'expression dans le dividende n'est pas explicitement signée.

Cela dépend complètement de l'appareil cible, de la langue, du but, etc.

Pixel craquant dans un pilote de carte vidéo? Très probablement, oui!

Application métier .NET pour votre département? Absolument aucune raison de même y jeter un œil.

Pour un jeu de haute performance pour un appareil mobile, il peut être utile de l'examiner, mais seulement après avoir effectué des optimisations plus faciles.

Ne le faites pas sauf si vous en avez absolument besoin et que votre intention de code nécessite un décalage plutôt qu'une multiplication / division.

Dans la journée typique - vous pourriez potentiellement économiser quelques cycles de machine (ou perdre, car le compilateur sait mieux quoi optimiser), mais le coût n'en vaut pas la peine - vous passez du temps sur des détails mineurs plutôt que sur le travail réel, maintenir le code devient plus difficile et vos collègues vous maudiront.

Vous devrez peut-être le faire pour les calculs à haute charge, où chaque cycle enregistré signifie des minutes d'exécution. Mais, vous devez optimiser un endroit à la fois et faire des tests de performances à chaque fois pour voir si vous avez vraiment accéléré ou cassé la logique des compilateurs.

Pour autant que je sache, sur certaines machines, la multiplication peut nécessiter jusqu'à 16 à 32 cycles machine. Alors oui , selon le type de machine, les opérateurs de décalage de bits sont plus rapides que la multiplication / division.

Cependant, certaines machines ont leur processeur mathématique, qui contient des instructions spéciales pour la multiplication / division.

Je suis d'accord avec la réponse marquée de Drew Hall. La réponse pourrait cependant utiliser quelques notes supplémentaires.

Pour la grande majorité des développeurs de logiciels, le processeur et le compilateur ne sont plus pertinents pour la question. La plupart d'entre nous sont bien au-delà du 8088 et du MS-DOS. Il n'est peut-être pertinent que pour ceux qui développent encore des processeurs embarqués ...

Dans ma société de logiciels, Math (add / sub / mul / div) devrait être utilisé pour toutes les mathématiques. Alors que Shift doit être utilisé lors de la conversion entre les types de données, par exemple. ushort à octet comme n >> 8 et non n / 256.

Dans le cas d'entiers signés et de décalage à droite vs division, cela peut faire une différence. Pour les nombres négatifs, le décalage arrondit vers l'infini négatif tandis que la division arrondit vers zéro. Bien sûr, le compilateur changera la division en quelque chose de moins cher, mais il le changera généralement en quelque chose qui a le même comportement d'arrondi que la division, car il est incapable de prouver que la variable ne sera pas négative ou simplement non se soucier. Donc, si vous pouvez prouver qu'un nombre ne sera pas négatif ou si vous ne vous souciez pas de la façon dont il sera arrondi, vous pouvez faire cette optimisation d'une manière plus susceptible de faire la différence.

Test Python effectuant la même multiplication 100 millions de fois contre les mêmes nombres aléatoires.

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

Donc, en faisant un décalage plutôt que la multiplication / division par une puissance de deux en python, il y a une légère amélioration (~ 10% pour la division; ~ 1% pour la multiplication). Si c'est une non-puissance de deux, il y a probablement un ralentissement considérable.

Encore une fois, ces #s changeront en fonction de votre processeur, de votre compilateur (ou interprète - fait en python pour plus de simplicité).

Comme pour tout le monde, n'optimisez pas prématurément. Écrivez du code très lisible, profilez s'il n'est pas assez rapide, puis essayez d'optimiser les parties lentes. N'oubliez pas que votre compilateur est bien meilleur en optimisation que vous.

Il y a des optimisations que le compilateur ne peut pas faire car elles ne fonctionnent que pour un ensemble réduit d'entrées.

Ci-dessous, il y a un exemple de code c ++ qui peut effectuer une division plus rapide en effectuant une "multiplication par la réciproque" de 64 bits. Le numérateur et le dénominateur doivent être inférieurs à un certain seuil. Notez qu'il doit être compilé pour utiliser des instructions 64 bits pour être réellement plus rapide que la division normale.

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

Je pense que dans le cas où vous voulez multiplier ou diviser par une puissance de deux, vous ne pouvez pas vous tromper en utilisant des opérateurs de décalage de bits, même si le compilateur les convertit en MUL / DIV, parce que certains microcodes de processeurs (vraiment, un macro) de toute façon, donc dans ces cas, vous obtiendrez une amélioration, surtout si le décalage est supérieur à 1. Ou plus explicitement, si le CPU n'a pas d'opérateurs de décalage de bit, ce sera de toute façon un MUL / DIV, mais si le CPU a opérateurs bithift, vous évitez une branche de microcode et c'est quelques instructions de moins.

J'écris actuellement du code qui nécessite beaucoup d'opérations de doublement / réduction de moitié car il fonctionne sur un arbre binaire dense, et il y a une opération de plus que je soupçonne peut-être plus optimale qu'une addition - une gauche (puissance de deux multiplier ) décalage avec un ajout. Cela peut être remplacé par un décalage vers la gauche et un xor si le décalage est plus large que le nombre de bits que vous souhaitez ajouter, un exemple simple est (i << 1) ^ 1, qui ajoute un à une valeur doublée. Cela ne s'applique bien sûr pas à un décalage à droite (puissance de deux) car seul un décalage à gauche (petit endian) remplit l'espace avec des zéros.

Dans mon code, ces multiplications / divisions par deux et les puissances de deux opérations sont utilisées de manière très intensive et parce que les formules sont déjà assez courtes, chaque instruction qui peut être éliminée peut être un gain substantiel. Si le processeur ne prend pas en charge ces opérateurs de décalage de bits, aucun gain ne se produira mais il n'y aura pas non plus de perte.

De plus, dans les algorithmes que j'écris, ils représentent visuellement les mouvements qui se produisent donc en ce sens ils sont en fait plus clairs. Le côté gauche d'un arbre binaire est plus grand et le côté droit est plus petit. En plus de cela, dans mon code, les nombres pairs et impairs ont une signification particulière, et tous les enfants de gauche dans l'arbre sont impairs et tous les enfants de droite, et la racine, sont pairs. Dans certains cas, que je n'ai pas encore rencontrés, mais peut-être, oh, en fait, je n'y ai même pas pensé, x & 1 peut être une opération plus optimale que x% 2. x & 1 sur un nombre pair produira zéro, mais produira 1 pour un nombre impair.

Allant un peu plus loin qu'une simple identification impaire / paire, si j'obtiens zéro pour x et 3, je sais que 4 est un facteur de notre nombre, et même pour x% 7 pour 8, et ainsi de suite. Je sais que ces cas ont probablement une utilité limitée, mais il est bon de savoir que vous pouvez éviter une opération de module et utiliser une opération logique au niveau du bit, car les opérations au niveau du bit sont presque toujours les plus rapides et les moins susceptibles d'être ambiguës pour le compilateur.

J'invente à peu près le domaine des arbres binaires denses, donc je m'attends à ce que les gens ne saisissent pas la valeur de ce commentaire, car très rarement, les gens ne veulent effectuer des factorisations que sur des puissances de deux seulement, ou seulement multiplier / diviser des puissances de deux.

Qu'il soit réellement plus rapide dépend du matériel et du compilateur réellement utilisés.

Si vous comparez la sortie pour la syntaxe x + x, x * 2 et x << 1 sur un compilateur gcc, vous obtiendrez le même résultat dans l'assemblage 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

Vous pouvez donc considérer gcc comme un outil suffisamment intelligent pour déterminer sa propre meilleure solution indépendamment de ce que vous avez tapé.

Moi aussi, je voulais voir si je pouvais battre la Chambre. ceci est un bitwise plus général pour n'importe quel nombre par n'importe quelle multiplication de nombre. les macros que j'ai créées sont environ 25% plus à deux fois plus lentes que la multiplication normale *. comme disent les autres si c'est proche d'un multiple de 2 ou composé de quelques multiples de 2, vous pourriez gagner. comme X * 23 composé de (X << 4) + (X << 2) + (X << 1) + X va être plus lent que X * 65 composé de (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;
}