Comment puis-je utiliser le décalage de bits à remplacer division entière?

Je comprends comment le faire pour des puissances de 2, ce qui n'est pas ma question.

Par exemple, si je veux trouver de 5% d'un nombre à l'aide d'un décalage de bits au lieu d'une division d'entier, comment pourrais-je le calculer?

Ainsi, au lieu de (x * 20 /19), j'ai pu faire (x * 100 >> 11). Maintenant, ce n'est pas un droit, mais il est proche et je suis arrivé à l'aide de l'essai et de l'erreur. Comment puis-je déterminer le plus précis possible maj pour utiliser?

Pourquoi? Est-ce censé être une optimisation? De quoi êtes-vous optimiser? Êtes-vous sûr qu'il a besoin d'être optimisé?
Ce qui fait de vous ce que c'est possible?
Jonathan a raison: Si vous voulez l'utiliser comme une optimisation, vous devrait plutôt laisser le compilateur faire le travail pour vous, puisque les compilateurs sont mieux que la plupart des humains de faire de telles choses. Toutefois, si vous voulez juste pour savoir, je ne pense pas qu'il y est un petit guide sur comment convertir entre division et de déplacement.
tout ce qui est, c'est pas de l'optimisation... 🙂
Non, x * 100 >> 11 est x * 100 / 2048 est x * .048828125 qui est une approximation raisonnable de 5%. x * 102 >> 11 est mieux que brainjam souligné, mais x * 51 >> 10 est tout aussi bon et moins susceptibles de déborder, alors que x * 205 >> 12 a un nombre bien moindre erreur.

OriginalL'auteur glutz78 | 2010-10-03

  1. 20

    Meilleure approche est de laisser le compilateur faire pour vous. Il suffit d'écrire

    a/b

    dans la langue de votre choix, et le compilateur génère le peu tourner.

    MODIFIER (j'espère que vous n'avez pas l'esprit, je suis en ajoutant des renforts votre réponse:

    #include <stdio.h>

int main(int argc, char **argv) {
  printf("%d\n", argc/4);
}

    Évidemment, de la manière la plus rapide chose à faire est de argc>>2. Permet de voir ce qui se passe:

            .file   "so3.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        andl    $-16, %esp
        subl    $16, %esp
        movl    8(%ebp), %eax
        movl    %eax, %edx
        sarl    $31, %edx
        shrl    $30, %edx
        leal    (%edx,%eax), %eax
        sarl    $2, %eax
        movl    %eax, %edx
        movl    $.LC0, %eax
        movl    %edx, 4(%esp)
        movl    %eax, (%esp)
        call    printf
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
        .section        .note.GNU-stack,"",@progbits

    yup, ça y est, sarl $2, %eax

    EDIT 2 (Désolé pour la pile sur, mais 20/19 est un peu plus compliqué...)

    J'ai juste remplacé argc*20/19 pour argc/4 et c'est les maths qui vient de sortir:

    0000000100000f07        shll    $0x02,%edi
0000000100000f0a        movl    $0x6bca1af3,%edx
0000000100000f0f        movl    %edi,%eax
0000000100000f11        imull   %edx
0000000100000f13        sarl    $0x03,%edx
0000000100000f16        sarl    $0x1f,%edi
0000000100000f19        subl    %edi,%edx

    Ainsi, le processus est

    • Multiplier entrée par 4 (shll)
    • Charge (movl 0x...) et de le multiplier par (imull) un point fixe de la fraction de l'obtention d'un résultat de 64 bits (c'est le code 32 bits)
    • Diviser élevé-de l'ordre de 32 bits de résultat par 8 (sarl), notez la façon dont elle traite les nombres négatifs
    • Diviser faible-de l'ordre de 32 bits de résultat par INT_MAX (sarl) pour obtenir 0 ou -1
    • Correctement tour de la haute-ordre obtenu en ajoutant 1 (soustraction de l'-1) si nécessaire.
    +1 - travailler les morceaux à la main est une corvée, et la meilleure façon d'apprendre le processus consiste à examiner lors de la compilation de sortie.
    J'ai ajouté de la sortie du compilateur pour prouver à quel point vous avez raison!
    +1 l'Amour le code assembleur!
    Je suis tombé baaaddd gagner autant de rep de vos efforts. Pas très mauvais, il ne sera pas me garder éveillé la nuit, mais un peu de mal 🙂
    Meh, si j'étais allé à la peine de la décrire en termes généraux, cela serait plus utile. Pas de point de laisser rep effectivement décider quoi que ce soit.

    OriginalL'auteur High Performance Mark

  2. 7

    Il n'a pas de sens parce que ce que vous essayez de faire ne permet pas d'optimiser le processus qui en résulte!!!

    Hey, je n'ai pas lu n'importe où dans votre question que vous avez eu l'intention de les optimiser.

    Électrique Engg les gens n'ont jamais cesser d'être curieux, indépendamment de leur "utilité". Nous sommes comme obsessionnel-compulsif accapareurs des éléments dont vous lisez dans la presse où ils entassent leurs greniers, caves, chambres et salles de séjour avec l'ordure qui, à leur avis, utile un jour. Du moins c'était le cas lorsque j'étais à l'Engg l'école un peu moins de 30 ans. Je vous encourage à poursuivre votre quête pour ammasser "inutile" de la connaissance qui semble avoir peu de possibilités d'optimisation de votre vie ou votre style de vie. Pourquoi dépendre du compilateur quand vous pouvez le faire à la main codé algorithme?! Yah? Être un peu plus aventureux, vous savez. Ok enuf dissing les personnes qui en expriment le mépris à votre quête de la connaissance.

    Rappel dans votre milieu de l'école, de la façon que vous avez appris à faire de votre division? 437/24, par exemple

      _____
24|437


   018
  -----
24|437
   24
  -----
   197
    24
  -----
     5

    Le nombre qui est soumis à la division, 437, est appelé le dividende. 24 est le diviseur, le résultat de 18 ans, est le quotient, et 5 est le reste. Comme lorsque vous produisez votre déclaration d'impôts, vous devez remplir les profits que vous avait gagné de stock "dividendes", ce qui est un abus de langage. Ce que vous renseignez dans le formulaire d'impôt est un multiple de le quotient d'un seul énorme partie du dividende. Vous n'avez pas reçu le dividende, mais des portions de dividende - sinon, ça voudrait dire qu'il vous appartient à 100% du stock.

         ___________
11000|110110101



      000010010
     -----------
11000|110110101 
      11000
     ----------
      000110101 remainder=subtract divisor from dividend
       11000000 shift divisor right and append 0 to quotient until
        1100000 divisor is not greater than remainder.
         110000 Yihaa!
     ----------
         000101 remainder=subtract shifted divisor from remainder
          11000 shift divisor right and append 0 to quotient until
           1100 divisor is not greater than remainder.
     ----------
               oops, cannot shift anymore.

    Ci-dessus, comme vous le savez peut être déjà, est VRAI de la division. Ce qui est obtenu par la soustraction par un décalage d'diviseur.

    Ce que vous voulez est d'obtenir la même chose par le simple fait de transférer le dividende. Qui, malheureusement, ne peut pas être fait, sauf si le diviseur est une exponentielle de la puissance de 2 (2,4,8,16). Ce qui est un fait évident de l'arithmétique binaire. Ou, au moins, je ne suis pas au courant de toute méthode qui peut le faire sans approximation et intrapolative techniques.

    Par conséquent, vous devez utiliser une combinaison de dividendes changement et de la vraie division.
    par exemple,

    24 = 2 x 2 x 2 x 3

    D'abord, diviser 437 par 8 à l'aide de décalage binaires pour obtenir 010010 puis utilisez vraie division pour diviser par 3:

       010010
  --------
11|110110
   11
   -------
     011
      11
     -----
        0

    pour 010010 = 18.

    Le tour est joué.

    Comment déterminez-vous les 24 = 2^8 x 3?

    Par le passage de 11000 rightwards jusqu'à ce que vous frappez un 1.

    Ce qui signifie, vous pouvez changer le dividende le même nombre de fois que vous le feriez maj le diviseur jusqu'à ce que le diviseur de frappe 1.

    Donc, de toute évidence, cette méthode ne fonctionne pas si un diviseur impair.
    par exemple, il ne fonctionnera pas pour diviseur 25, mais il faudra travailler un peu pour diviseur 50.

    Peut-être, il y a les méthodes de prévision qui pourrait interpoler un diviseur de 13 à être entre les 2^3=8 et 2^4=16. Si il y a, je ne suis pas familier avec eux.

    Ce dont vous avez besoin pour explorer à l'aide d'un numéro de série. Par exemple, en divisant par 25:

     1    1    1     1     1
__ = __ - ___ - ___ + ___ -  ... until the precision you require.
25   16   64    128   256

    où la forme générale de la série est

    1    1      b1              bn
_ = ___ + _______ + ... + ______
D   2^k   2^(k+1)         2^(k+n)

    où bn est soit -1, 0 ou +1.

    J'en espérant que mon binaire de la manipulation ci-dessus ne serait pas avoir des erreurs ou des fautes de frappe. Si oui, des milliers d'excuses.

    OriginalL'auteur Blessed Geek

  3. 6

    Supposons que vous avez l'expression a = b /c. Comme hroptatyr mentionné, la multiplication est assez rapide (et c'est beaucoup plus rapide que pour la division). Donc l'idée de base est de transformer la division en multiplication comme : a = b * (1/c).

    Maintenant, nous avons encore besoin de la division pour le calcul de reciprical 1/c, donc cela ne peut fonctionner que si c est connu apriorique. Tandis que, pour le calcul à virgule flottante, il suffit, pour intereges il faut utiliser une autre astuce: on peut l'utiliser pour la réciproque de la valeur de c la valeur some_big_number /c, de sorte que, finalement, nous allons calculer a2 = b * (some_big_number /c), qui est égal à some_big_number * b/c. Parce que nous sommes intéressés à la valeur de b/c, nous devons diviser le résultat final par some_big_number. Si il est choisi pour être une puissance de 2, puis la finale de la division rapide.

    ex:

    //we'll compute 1/20 of the input
unsigned divide_by_20(unsigned n){
    unsigned reciprocal = (0x10000 + 20 - 1) / 20; //computed at compile time, but you can precompute it manually, just to be sure
    return (n * reciprocal) >> 16;
}

    EDIT: une bonne partie de cette méthode est que vous pouvez choisir n'importe quelle méthode d'arrondi pour la divison par le choix de la correction (dans ce cas, il a été 20 - 1 pour l'arrondi vers zéro).

    Pour des valeurs signées, diviser par 65536 au lieu de déplacer le 16, le compilateur va se convertir à un décalage et un fix-up.

    OriginalL'auteur ruslik

  4. 6

    Si vous êtes intéressé par les mathématiques derrière elle, lire Hacker Plaisir par Henry S. Warren.

    Si vous êtes intéressé par un code optimisé, il suffit d'écrire ce qui est le plus facile à lire par les humains. Par exemple:

    int five_percent(int x) {
  return x / 20;
}

    Lors de la compilation de cette fonction à l'aide g++ -O2, il ne fera pas une réelle division, mais la magie de la multiplication, de décalage de bits et de correction à la place.

    OriginalL'auteur Roland Illig

  5. 3

    Vous ne pouvez pas tout faire avec les quarts de travail, vous aurez besoin d'utiliser la "magie" diviseurs(voir les pirates plaisir). La magie de la division travaille en multipliant un nombre par un autre convenablement grand nombre, le faisant rouler sur de manière à produire la réponse de la division(mul/imul est plus rapide que la div/idiv). Il y a de la magie des constantes ne sont uniques pour chaque prime, les multiples nécessitent un déplacement, par exemple: unsigned division par 3 peut être représenté (sur 32 bits) comme x * 0xAAAAAAAB, la division par 6 serait (x * 0xAAAAAAAB) >> 1 de la division par 12 passerait par 2, 24, par 3, etc (c'est la série géométrique 3 * (2 ^ x), où 0 <= x < 32)

    OriginalL'auteur Necrolis

  6. 2

    Supposons que vous voulez à environ 5% de x en multipliant par y et le déplacement par n. Depuis le 5% est 1/20, et a>>n = un/2n, voulez-vous résoudre

    x/20 ≈ x*y/2n (le symbole "≈" signifie "environ égal")

    qui simplifie à

    y ≈ 2n/20

    Donc, si n=11, alors

    y ≈ 2n/20 = 2048/20 =102 + 8/20

    Afin que nous puissions définir y=102, qui est en fait mieux que le 100 vous les avez trouvés par l'essai et l'erreur.

    Généralement, on peut jouer avec n pour voir si nous pouvons obtenir une meilleure réponse.

    J'ai travaillé pour la fraction 1/20, mais vous devriez être capable de faire ce travail pour toute fraction p/q, en suivant la même méthode.

    OriginalL'auteur brainjam

  7. 0

    Bien en général:

    • obtenir le premier factorisation du nombre, vous feriez décomposer N en 2^k * reste, alors vous pouvez utiliser le décalage de bits sur la puissance de deux. Exemple: 20 = 2^2 * 5, donc à multiplier par vingt, vous multipliez par 5, puis utiliser le décalage de bits << 2
    • D'utiliser le décalage de bits sur la non-deux pouvoirs, respectez les consignes suivantes pour impair l: a * l = a * (l - 1) + a, maintenant l - 1 est même et ainsi se décompose en une puissance de deux, pour laquelle le décalage de bits "truc" s'applique.

    Division peut être construit de la même façon.

    Qui n'a pas de sens. La Multiplication par 5 comprend tous les frais de déplacement << 2. L'objet ici est de multiplier par un nombre rationnel dans un ou deux instructions avec pas de division, pas de décomposer le nombre et l'usage d'un nombre indéfini de insns.
    Qui a dit cela? L'OP veut savoir comment son tour entier de multiplication en décalage de bits, j'ai juste décrit la procédure générale.
    Oh et btw, ne jamais juger avant d'avoir mesuré, j'ai juste trouvé qu'un imul serait de 3 cycles sur mon CPU alors que ma solution avec un shl et un add prend 2 cycles.
    Un shl et un add seulement accomplit une multiplication par 5. Vous avez encore besoin d'un autre insn à changer à nouveau. Le compilateur doit être assez intelligent pour le comprendre et de ne pas produire les imul si ses vraiment de qualité inférieure, bien que pour des raisons de portabilité, il pourrait ne pas être un spécialiste de votre puce, et le supérieur de l'instruction de comptage peut causer d'autres problèmes de congestion.
    De toute façon, la question n'est pas tellement sur le remplacement de la multiplication de la division, vous n'avez pas d'adresse à tous. Qui nécessite d'avoir les résultat de la multiplication, qui ne peuvent pas être représentés à l'aide de C-opérateurs. (Au moins, de ne pas obtenir la totalité de la largeur d'un entier registre). C'est un point fixe de mathématiques truc.

    OriginalL'auteur hroptatyr