Bitshift à multiplier par un nombre quelconque

En utilisant uniquement l'addition, la soustraction, et bitshifting, comment puis-je multiplier un nombre entier par un nombre donné?

Par exemple, je veux multiplier un nombre entier par 17.

Je sais que le passage de gauche est en multipliant par un multiple de 2 et de déplacement de droite est la division par une puissance de 2, mais je ne sais pas comment faire pour généraliser cela.

Que sur des nombres négatifs? Convertir en complément à deux et de faire la même procédure?

(EDIT: OK, j'ai eu ce, tant pis. Vous convertir en complément à deux et puis ne vous déplaçant selon le nombre de gauche à droite au lieu de droite à gauche.)

Maintenant la partie la plus délicate est en. Nous ne pouvons utiliser 3 opérateurs.

Par exemple, en multipliant par 60 je peux accomplir en utilisant ce:

(x << 5) + (x << 4) + (x << 3) + (x << 2)

Où x est le numéro je suis multipliant. Mais c'est 7 opérateurs - comment puis-je condenser ce n'utilisent que 3?

  • En général, les multiplications ne peut pas être fait en 3 opérations de quarts de travail, ajouter/soustrait... Mais les deux 17 et 60 peut être fait en 3 opérations. (astuce: essayez une soustraction pour 60) EDIT: je ne vois pas cela a déjà été répondu.
  • ils ont fait les problèmes de sorte des idéalement travail dans les 3 opérateurs haha. merci pour toute l'aide.
InformationsquelleAutor Adam | 2011-09-02
  1. 3

    Autant que je sache, il n'y a pas de moyen facile de multiplier, en général, à l'aide de seulement 3 opérateurs.

    Multipliant avec 60 est possible, depuis 60 = 64 - 4: (x << 6) - (x << 2)

    • Je ne pense pas que c'est possible en 3 opérations en général. (à moins de multiplier, de l'enseignement de cours)
    InformationsquelleAutor Timbits
  2. 12

    Elle est appelée shift-and-add. Wikipedia a une bonne explication de ce:

    http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

    EDIT:
    Pour répondre à votre question, oui, la conversion à deux du compliment de fonctionner. Mais vous devez vous inscrire prolonger assez longtemps pour que l'ensemble du produit. (en supposant que c'est ce que vous voulez)

    EDIT2:
    Si les deux opérandes sont négatifs, juste deux du compliment de deux d'entre eux dès le début et vous n'aurez pas à vous inquiéter à ce sujet.

    • Merci très utile.
    • Édité avec la réponse à votre deuxième question.
    InformationsquelleAutor Mysticial
  3. 6

    Voici un exemple de la multiplication par 3:

    unsigned int y = (x << 1) + (x << 0);

    (où je suis en supposant que x est également unsigned).

    Nous l'espérons vous devriez être en mesure de généraliser cette.

    • Oui, je peux et je vous remercie. Que faire si ses un nombre négatif à multiplier par? dois-je faire 2s complément sur elle, puis utiliser ce numéro pour faire ma fonction?
    InformationsquelleAutor Oliver Charlesworth
  4. 4

    17 = 16 + 1 = (2^4) + (2^0). Donc, changement de votre numéro de left 4 bits (à multiplier par 2^4 = 16), et ajouter le numéro d'origine à elle.

    Une autre façon de voir les choses est de: 17 est 10001 en binaire (base 2), de sorte que vous besoin d'une opération de déplacement pour chacun des bits définis dans le multiplicateur (c'est à dire les bits 4 et 0, comme ci-dessus).

    Je ne sais pas C, donc je ne vais pas me mettre dans l'embarras en offrant code.

    • Je vous remercie. Que faire si ses un nombre négatif à multiplier par? dois-je faire 2s complément sur elle, puis utiliser ce numéro pour faire ma fonction/quarts de travail?
    InformationsquelleAutor dty