Cambio Bits para multiplicar por cualquier número

Usando solo sumar, restar y cambiar bits, ¿cómo puedo multiplicar un número entero por un número dado?Cambio Bits para multiplicar por cualquier número

Por ejemplo, quiero multiplicar un número entero por 17.

Yo sé que el desplazamiento de la izquierda es la multiplicación por un múltiplo de 2 y desplazando a la derecha se divide por una potencia de 2, pero no sé cómo generalizar eso.

¿Qué hay de los números negativos? Convierte a dos complemento y hacer el mismo procedimiento?

(EDIT: OK, tengo esto, no importa que convierte a complemento a dos y luego es lo que el cambio en función del número de izquierda a derecha en vez de derecha a izquierda..)

Ahora viene la parte difícil. Solo podemos usar 3 operadores.

Por ejemplo, multiplicando por 60 que puedo lograr mediante el uso de esto:

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

Dónde x es el número estoy multiplicando. Pero eso son 7 operadores: ¿cómo puedo condensar esto para usar solo 3?

Fuente

2011-09-02 Adam

En multiplicaciones generales no se puede hacer en 3 operaciones de cambios, añadir/resta ... Pero ambos 17 y 60 se puede hacer en 3 operaciones . (pista: prueba una resta de 60) EDITAR: No vi que esto ya haya sido respondido. – Mysticial

hicieron los problemas para que el trabajo convenientemente en 3 operadores jaja. Gracias por toda la ayuda. – Adam

Por lo que sé, no hay una manera fácil de multiplicar en general con solo 3 operadores.

Multiplicando con 60 es posible, ya que el 60 = 64 - 4: (x << 6) - (x << 2)

Fuente

2011-09-02 17:04:10 Timbits

No creo que sea posible en 3 operaciones en general. (salvo la instrucción de multiplicación, por supuesto) – Mysticial

17 = 16 + 1 = (2^4) + (2^0). Por lo tanto, cambie su número a 4 bits (para multiplicar por 2^4 = 16) y añádale el número original.

Otra forma de verlo es: 17 es 10001 en binario (base 2), por lo que necesita una operación de cambio para cada uno de los bits establecidos en el multiplicador (es decir, bits 4 y 0, como se indicó anteriormente).

No sé C, así que no me avergonzaré ofreciendo código.

Fuente

2011-09-02 16:10:11 dty

Gracias. ¿Qué pasa si es un número negativo para multiplicar? ¿Hago un complemento de 2 segundos y luego uso ese número para hacer mi función/turno? – Adam

Se llama shift-and-add. Wikipedia tiene una buena explicación de esto:

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

EDIT: para responder a su otra pregunta, sí a convertir el cumplido de dos va a trabajar. Pero debe firmar extenderlo el tiempo suficiente para mantener todo el producto. (suponiendo que eso es lo que quiere)

EDIT2: Si ambos operandos son negativos, solo dos los complementan desde el principio y no tendrá que preocuparse por esto.

Fuente

2011-09-02 16:10:41 Mysticial

Muchas gracias. – Adam

Editado con la respuesta a su segunda pregunta. – Mysticial

He aquí un ejemplo de multiplicar por 3:

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

(donde yo estoy asumiendo que es también xunsigned).

Esperemos que pueda generalizar esto.

Fuente

2011-09-02 16:10:54

Sí, puedo y gracias. ¿Qué pasa si es un número negativo para multiplicar? ¿Hago complemento 2s y uso ese número para hacer mi función? – Adam

Cambio Bits para multiplicar por cualquier número

Respuesta

Cuestiones relacionadas