ejemplos - operadores relacionales en java
¿Cómo puedo realizar la multiplicación sin el operador ''*''? (30)
Solo estaba revisando algunas cosas básicas mientras aprendía C. Encontré una pregunta para multiplicar un número por 7 sin usar el operador *. Básicamente es así
(x << 3) - x;
Ahora que conozco las operaciones básicas de manipulación de bits, pero no entiendo, ¿cómo se multiplica un número por otro número impar sin usar el operador *? ¿Hay un algoritmo general para esto?
@Wang, eso es una buena generalización. Pero aquí hay una versión ligeramente más rápida. Pero no asume ningún desbordamiento y es no negativo.
int mult(int a, int b){
int p=1;
int rv=0;
for(int i=0; a >= p && i < 31; i++){
if(a & p){
rv += b;
}
p = p << 1;
b = b << 1;
}
return rv;
}
Se repetirá como máximo 1 + log_2 (a) veces. Podría ser más rápido si cambia a y b cuando a> b.
Al hacer uso de la recursión, podemos multiplicar dos enteros con las restricciones dadas.
Para multiplicar x e y, agrega recursivamente xy veces.
#include<stdio.h>
/* function to multiply two numbers x and y*/
int multiply(int x, int y)
{
/* multiplied with anything gives */
if(y == 0)
return 0;
/* Add x one by one */
if(y > 0 )
return (x + multiply(x, y-1));
/* the case where y is negative */
if(y < 0 )
return -multiply(x, -y);
}
int main()
{
printf("/n %d", multiply(5, -11));
getchar();
return 0;
}
Cía#:
private static string Multi(int a, int b)
{
if (a == 0 || b == 0)
return "0";
bool isnegative = false;
if (a < 0 || b < 0)
{
isnegative = true;
a = Math.Abs(a);
b = Math.Abs(b);
}
int sum = 0;
if (a > b)
{
for (int i = 1; i <= b; i++)
{
sum += a;
}
}
else
{
for (int i = 1; i <= a; i++)
{
sum += b;
}
}
if (isnegative == true)
return "-" + sum.ToString();
else
return sum.ToString();
}
Cualquier número, par o impar, se puede expresar como una suma de potencias de dos. Por ejemplo,
1 2 4 8
------------------
1 = 1
2 = 0 + 2
3 = 1 + 2
4 = 0 + 0 + 4
5 = 1 + 0 + 4
6 = 0 + 2 + 4
7 = 1 + 2 + 4
8 = 0 + 0 + 0 + 8
11 = 1 + 2 + 0 + 8
Por lo tanto, puede multiplicar x por cualquier número realizando el conjunto correcto de turnos y adiciones.
1x = x
2x = 0 + x<<1
3x = x + x<<1
4x = 0 + 0 + x<<2
5x = x + 0 + x<<2
11x = x + x<<1 + 0 + x<<3
Cuando se trata de eso, la multiplicación por un entero positivo se puede hacer de la siguiente manera:
int multiply(int a, int b) {
int ret = 0;
for (int i=0; i<b; i++) {
ret += b;
}
return ret;
}
¿Eficiente? Apenas. Pero es correcto (teniendo en cuenta los límites de las acciones y demás).
Por lo tanto, usar un turno a la izquierda es solo un método abreviado para multiplicar por 2. Pero una vez que llegue a la potencia más alta de 2 en b , simplemente agregue la cantidad necesaria de veces, así que:
int multiply(int a, int b) {
int ret = a;
int mult = 1;
while (mult <= b) {
ret <<= 1;
mult <<= 1;
}
while (mult < b) {
ret += a;
}
return ret;
}
O algo parecido a eso.
Para decirlo de otra manera, multiplicar por 7.
- Desplazar a la izquierda por 2 (4 veces). El desplazamiento a la izquierda 3 es 8, que es> 7;
- Añadir
b3 veces.
Es fácil evitar el operador ''*'':
mov eax, 1234h
mov edx, 5678h
imul edx
No ''*'' a la vista. Por supuesto, si desea entrar en el espíritu de la misma, también puede usar el antiguo turno de confianza y agregar un algoritmo:
mult proc
; Multiplies eax by ebx and places result in edx:ecx
xor ecx, ecx
xor edx, edx
mul1:
test ebx, 1
jz mul2
add ecx, eax
adc edx, 0
mul2:
shr ebx, 1
shl eax, 1
test ebx, ebx
jnz mul1
done:
ret
mult endp
Por supuesto, con los procesadores modernos, todos (?) Tienen instrucciones de multiplicación, pero cuando el PDP-11 era brillante y nuevo, un código como este vio un uso real.
Es lo mismo que x*8-x = x*(8-1) = x*7
Esta es la solución C99 / C11 más simple para números positivos:
unsigned multiply(unsigned x, unsigned y) { return sizeof(char[x][y]); }
Hablando matemáticamente, la multiplicación se distribuye sobre la suma. Esencialmente, esto significa:
x * (a + b + c ...) = (x * a) + (x * b) + (x * c) ...
Cualquier número real (en su caso 7 ) se puede presentar como una serie de adiciones (como 8 + (-1) , ya que la resta es simplemente una suma que va por el camino equivocado). Esto le permite representar cualquier instrucción de multiplicación individual como una serie equivalente de instrucciones de multiplicación, que dará el mismo resultado:
x * 7
= x * (8 + (-1))
= (x * 8) + (x * (-1))
= (x * 8) - (x * 1)
= (x * 8) - x
El operador de cambio a nivel de bits esencialmente multiplica o divide un número por una potencia de 2. Mientras que su ecuación solo trate con dichos valores, el desplazamiento de bits se puede usar para reemplazar toda la ocurrencia del operador de multiplicación.
(x * 8) - x = (x * 2 3 ) - x = (x << 3) - x
Se puede usar una estrategia similar en cualquier otro entero, y no importa si es par o impar.
La pregunta dice:
multiplica un número por 7 sin usar el operador *
Esto no usa * :
number / (1 / 7)
Editar:
Esto compila y funciona bien en C:
int number,result;
number = 8;
result = number / (1. / 7);
printf("result is %d/n",result);
Loop Ejecute un bucle siete veces e itere por el número que está multiplicando por siete.
Pseudocódigo
total = 0
multiply = 34
loop while i < 7
total = total + multiply
endloop
Mayús y agregar no funciona (incluso con la extensión de signo) cuando el multiplicando es negativo. La multiplicación firmada debe hacerse usando la codificación Booth :
A partir de la LSB , un cambio de 0 a 1 es -1; un cambio de 1 a 0 es 1, de lo contrario 0. También hay un bit adicional implícito 0 debajo del LSB.
Por ejemplo, el número 5 (0101) se codificará como: (1) (- 1) (1) (- 1). Puedes verificar que esto es correcto:
5 = 2 ^ 3 - 2 ^ 2 + 2 -1
Este algoritmo también funciona con números negativos en forma de complemento a 2:
-1 en el complemento de 4 bits 2 es 1111. Usando el algoritmo Booth: (1) (0) (0) (0) (- 1), donde no hay espacio para el bit 1 más a la izquierda, por lo que obtenemos: (0) (0) (0) (- 1) que es -1.
/* Multiply two signed integers using the Booth algorithm */
int booth(int x, int y)
{
int prev_bit = 0;
int result = 0;
while (x != 0) {
int current_bit = x & 0x1;
if (prev_bit & ~current_bit) {
result += y;
} else if (~prev_bit & current_bit) {
result -= y;
}
prev_bit = current_bit;
x = static_cast<unsigned>(x) >> 1;
y <<= 1;
}
if (prev_bit)
result += y;
return result;
}
El código anterior no comprueba el desbordamiento. A continuación se muestra una versión ligeramente modificada que multiplica dos números de 16 bits y devuelve un número de 32 bits para que nunca se desborden:
/* Multiply two 16-bit signed integers using the Booth algorithm */
/* Returns a 32-bit signed integer */
int32_t booth(int16_t x, int16_t y)
{
int16_t prev_bit = 0;
int16_t sign_bit = (x >> 16) & 0x1;
int32_t result = 0;
int32_t y1 = static_cast<int32_t>(y);
while (x != 0) {
int16_t current_bit = x & 0x1;
if (prev_bit & ~current_bit) {
result += y1;
} else if (~prev_bit & current_bit) {
result -= y1;
}
prev_bit = current_bit;
x = static_cast<uint16_t>(x) >> 1;
y1 <<= 1;
}
if (prev_bit & ~sign_bit)
result += y1;
return result;
}
Muy simple, amigo ... Cada vez que dejas desplazar un número significa que estás multiplicando el número por 2, lo que significa que la respuesta es (x << 3) -x.
O (log (b)) método
public int multiply_optimal(int a, int b) {
if (a == 0 || b == 0)
return 0;
if (b == 1)
return a;
if ((b & 1) == 0)
return multiply_optimal(a + a, b >> 1);
else
return a + multiply_optimal(a + a, b >> 1);
}
El código resursivo funciona de la siguiente manera:
Caso base:
si cualquiera de los números es 0, el producto es 0.
si b = 1, producto = a.
Si b es par
ab puede escribirse como 2a (b / 2)
2a (b / 2) = (a + a) (b / 2) = (a + a) (b >> 1) donde ''>>'' es el operador de desplazamiento a la derecha en java.
Si b es impar
ab puede escribirse como a + a (b-1)
a + a (b-1) = a + 2a (b-1) / 2 = a + (a + a) (b-1) / 2 = a + (a + a) ((b-1) >> 1)
Como b es impar (b-1) / 2 = b / 2 = b >> 1
Entonces ab = a + (2a * (b >> 1))
NOTA: cada llamada recursiva b se divide en la mitad => O (log (b))
Otra respuesta de pensar fuera de la caja:
BigDecimal a = new BigDecimal(123);
BigDecimal b = new BigDecimal(2);
BigDecimal result = a.multiply(b);
System.out.println(result.intValue());
Piensa en cómo multiplicar en decimal usando lápiz y papel:
12
x 26
----
72
24
----
312
¿Cómo se ve la multiplicación en binario?
0111
x 0101
-------
0111
0000
0111
-------
100011
¿Notaste algo? A diferencia de la multiplicación en decimal, donde debe memorizar la "tabla de tiempos", al multiplicar en binario, siempre está multiplicando uno de los términos por 0 o 1 antes de escribirlo en la lista de sumandos. No hay tabla de tiempos necesaria. Si el dígito del segundo término es 1, agregue el primer término. Si es 0, no lo haces. También tenga en cuenta cómo los adendos se desplazan progresivamente hacia la izquierda.
Si no estás seguro de esto, haz algunas multiplicaciones binarias en papel. Cuando hayas terminado, convierte el resultado de nuevo a decimal y ve si es correcto. Una vez que haya hecho algunos, creo que tendrá una idea de cómo se puede implementar la multiplicación binaria usando turnos y adiciones.
Sea N el número que queremos multiplicar con 7.
N x 7 = N + N + N + N + N + N + N
N x 7 = N + N + N + N + N + N + N + (N - N)
N x 7 = (N + N + N + N + N + N + N + N) - N
N x 7 = 8xN - N
Como sabemos, el desplazamiento a la izquierda de cualquier número por un bit lo multiplica por 2. Por lo tanto, multiplicar cualquier número por 8 es equivalente al desplazamiento a la derecha por 3 bits
N x 7 = (N << 3) - N
Encontré esta descripción aquí http://www.techcrashcourse.com/2016/02/c-program-to-multiply-number-by-7-bitwise-operator.html
Espero eso ayude.
Si puede utilizar la función de registro:
public static final long multiplyUsingShift(int a, int b) {
int absA = Math.abs(a);
int absB = Math.abs(b);
//Find the 2^b which is larger than "a" which turns out to be the
//ceiling of (Log base 2 of b) == numbers of digits to shift
double logBase2 = Math.log(absB) / Math.log(2);
long bits = (long)Math.ceil(logBase2);
//Get the value of 2^bits
long biggerInteger = (int)Math.pow(2, bits);
//Find the difference of the bigger integer and "b"
long difference = biggerInteger - absB;
//Shift "bits" places to the left
long result = absA<<bits;
//Subtract the "difference" "a" times
int diffLoop = Math.abs(a);
while (diffLoop>0) {
result -= difference;
diffLoop--;
}
return (a>0&&b>0 || a<0&&b<0)?result:-result;
}
Si no puede utilizar la función de registro:
public static final long multiplyUsingShift(int a, int b) {
int absA = Math.abs(a);
int absB = Math.abs(b);
//Get the number of bits for a 2^(b+1) larger number
int bits = 0;
int bitInteger = absB;
while (bitInteger>0) {
bitInteger /= 2;
bits++;
}
//Get the value of 2^bit
long biggerInteger = (int)Math.pow(2, bits);
//Find the difference of the bigger integer and "b"
long difference = biggerInteger - absB;
//Shift "bits" places to the left
long result = absA<<bits;
//Subtract the "difference" "a" times
int diffLoop = absA;
while (diffLoop>0) {
result -= difference;
diffLoop--;
}
return (a>0&&b>0 || a<0&&b<0)?result:-result;
}
Encontré que esto es más eficiente:
public static final long multiplyUsingShift(int a, int b) {
int absA = Math.abs(a);
int absB = Math.abs(b);
long result = 0L;
while (absA>0) {
if ((absA&1)>0) result += absB; //Is odd
absA >>= 1;
absB <<= 1;
}
return (a>0&&b>0 || a<0&&b<0)?result:-result;
}
Y aún otra manera.
public static final long multiplyUsingLogs(int a, int b) {
int absA = Math.abs(a);
int absB = Math.abs(b);
long result = Math.round(Math.pow(10, (Math.log10(absA)+Math.log10(absB))));
return (a>0&&b>0 || a<0&&b<0)?result:-result;
}
Todo el mundo está pasando por alto lo obvio. No hay multiplicación involucrada:
10^(log10(A) + log10(B))
Un desplazamiento entero a la izquierda se multiplica por 2, siempre que no se desborde. Solo suma o resta según sea apropiado una vez que te acerques.
Un enfoque de JavaScript para números positivos
function recursiveMultiply(num1, num2){
const bigger = num1 > num2 ? num1 : num2;
const smaller = num1 <= num2 ? num1 : num2;
const indexIncrement = 1;
const resultIncrement = bigger;
return recursiveMultiplyHelper(bigger, smaller, 0, indexIncrement, resultIncrement)
}
function recursiveMultiplyHelper(num1, num2, index, indexIncrement, resultIncrement){
let result = 0;
if (index === num2){
return result;
}
if ((index+indexIncrement+indexIncrement) >= num2){
indexIncrement = 1;
resultIncrement = num1;
} else{
indexIncrement += indexIncrement;
resultIncrement += resultIncrement;
}
result = recursiveMultiplyHelper(num1, num2, (index+indexIncrement), indexIncrement, resultIncrement);
result += resultIncrement;
console.log(num1, num2, index, result);
return result;
}
Una noche, descubrí que estaba extremadamente aburrido, y cociné esto:
#include <iostream>
typedef unsigned int uint32;
uint32 add(uint32 a, uint32 b) {
do {
uint32 s = a ^ b;
uint32 c = a & b;
a = s;
b = c << 1;
} while (a & b)
return (a | b)
}
uint32 mul(uint32 a, uint32 b) {
uint32 total = 0;
do {
uint32 s1 = a & (-(b & 1))
b >>= 1; a <<= 1;
total = add(s1, total)
} while (b)
return total;
}
int main(void) {
using namespace std;
uint32 a, b;
cout << "Enter two numbers to be multiplied: ";
cin >> a >> b;
cout << "Total: " << mul(a,b) << endl;
return 0;
}
El código anterior debe ser bastante autoexplicativo, ya que traté de mantenerlo lo más simple posible. Debería funcionar, más o menos, de la forma en que una CPU podría realizar estas operaciones. El único error que conozco es que a no se permite que sea mayor que 32.767 y a b no se le permite que sea lo suficientemente grande como para desbordar a (es decir, no se maneja el desbordamiento múltiple, por lo que no es posible obtener resultados de 64 bits) . Incluso debería funcionar con números negativos, siempre que las entradas se reinterpret_cast<> apropiadamente reinterpret_cast<> .
JAVA:
Teniendo en cuenta el hecho de que cada número se puede dividir en potencias de dos:
1 = 2 ^ 0
2 = 2 ^ 1
3 = 2 ^ 1 + 2 ^ 0
...
Queremos obtener x donde:
x = n * m
Así que podemos lograrlo haciendo los siguientes pasos:
1. while m is greater or equal to 2^pow:
1.1 get the biggest number pow, such as 2^pow is lower or equal to m
1.2 multiply n*2^pow and decrease m to m-2^pow
2. sum the results
Implementación de ejemplo usando recursión:
long multiply(int n, int m) {
int pow = 0;
while (m >= (1 << ++pow)) ;
pow--;
if (m == 1 << pow) return (n << pow);
return (n << pow) + multiply(n, m - (1 << pow));
}
Obtuve esta pregunta en la última entrevista de trabajo y esta respuesta fue aceptada.
EDITAR: solución para números positivos
import java.math.BigInteger;
public class MultiplyTest {
public static void main(String[] args) {
BigInteger bigInt1 = new BigInteger("5");
BigInteger bigInt2 = new BigInteger("8");
System.out.println(bigInt1.multiply(bigInt2));
}
}
int multiply(int multiplicand, int factor)
{
if (factor == 0) return 0;
int product = multiplicand;
for (int ii = 1; ii < abs(factor); ++ii) {
product += multiplicand;
}
return factor >= 0 ? product : -product;
}
Querías multiplicación sin * , lo tienes, amigo!
package com.amit.string;
// Here I am passing two values, 7 and 3 and method getResult() will
// return 21 without use of any operator except the increment operator, ++.
//
public class MultiplyTwoNumber {
public static void main(String[] args) {
int a = 7;
int b = 3;
System.out.println(new MultiplyTwoNumber().getResult(a, b));
}
public int getResult(int i, int j) {
int result = 0;
// Check for loop logic it is key thing it will go 21 times
for (int k = 0; k < i; k++) {
for (int p = 0; p < j; p++) {
result++;
}
}
return result;
}
}
public static int multiply(int a, int b)
{
int temp = 0;
if (b == 0) return 0;
for (int ii = 0; ii < abs(b); ++ii) {
temp = temp + a;
}
return b >= 0 ? temp : -temp;
}
public static int abs(int val) {
return val>=0 ? val : -val;
}
public static void main(String[] args) {
System.out.print("Enter value of A -> ");
Scanner s=new Scanner(System.in);
double j=s.nextInt();
System.out.print("Enter value of B -> ");
Scanner p=new Scanner(System.in);
double k=p.nextInt();
double m=(1/k);
double l=(j/m);
System.out.print("Multiplication of A & B=> "+l);
}
unsigned int Multiply(unsigned int m1, unsigned int m2)
{
unsigned int numBits = sizeof(unsigned int) * 8; // Not part of the core algorithm
unsigned int product = 0;
unsigned int mask = 1;
for(int i =0; i < numBits; ++i, mask = mask << 1)
{
if(m1 & mask)
{
product += (m2 << i);
}
}
return product;
}
unsigned int Multiply( unsigned int a, unsigned int b )
{
int ret = 0;
// For each bit in b
for (int i=0; i<32; i++) {
// If that bit is not equal to zero
if (( b & (1 << i)) != 0) {
// Add it to our return value
ret += a << i;
}
}
return ret;
}
Evité el bit de signo, porque no es el tema del post. Esta es una implementación de lo que Wayne Conrad dijo básicamente. Aquí hay otro problema: si desea probar más operaciones matemáticas de bajo nivel. Proyecto Euler es genial!