Я просто изучал некоторые основные вещи, поскольку я изучаю C. Я наткнулся на вопрос, чтобы умножить число на 7 без использования оператора *. В основном это похоже на
(x << 3) - x;
Теперь я знаю об основных операциях манипулирования битами, но я не могу понять, как вы умножаете число на любое другое нечетное число без использования оператора *? Есть ли общий алгоритм для этого?
Подумайте, как вы умножаете десятичное число с помощью карандаша и бумаги:
12
x 26
----
72
24
----
312
Что такое умножение в двоичном формате?
0111
x 0101
-------
0111
0000
0111
-------
100011
Заметьте что-нибудь? В отличие от умножения в десятичном значении, когда вам нужно запомнить "таблицу раз" при умножении в двоичном формате, вы всегда умножаете одно из условий на 0 или 1, прежде чем записывать их в списках. Нет необходимости в таблице раз. Если цифра второго слагаемого равна 1, вы добавляете в первый член. Если это 0, вы этого не сделаете. Также обратите внимание, как слагаемые постепенно смещаются влево.
Если вы не уверены в этом, сделайте несколько бинарных умножений на бумаге. Когда вы закончите, верните результат обратно в десятичный и посмотрите, правильно ли он. После того, как вы сделали несколько, я думаю, вы поймете, как двоичное умножение может быть реализовано с помощью сдвигов и добавлений.
Все игнорируют очевидное. Не используется умножение:
10^(log10(A) + log10(B))
Целый левый сдвиг умножается на 2, если он не переполняется. Просто добавьте или вычтите по мере необходимости, как только вы приблизитесь.
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;
}
Вы хотели размножаться без *, вы получили его, приятель!
В вопросе говорится:
умножьте число на 7 без использования * operator
Это не использует *:
number / (1 / 7)
Edit:
Это компилируется и отлично работает в C:
int number,result;
number = 8;
result = number / (1. / 7);
printf("result is %d\n",result);
Легко избежать оператора '*':
mov eax, 1234h
mov edx, 5678h
imul edx
Нет '*' в поле зрения. Конечно, если вы хотели вникать в это, вы могли бы также использовать надежную старую смену и добавить алгоритм:
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
Конечно, с современными процессорами все (?) имеют инструкции умножения, но назад, когда PDP-11 был блестящим и новым, такой код видел реальное использование.
Математически умножение распределяется по сложениям. По сути, это означает:
x * (a + b + c...) = (x * a) + (x * b) + (x * c)...
Любое действительное число (в вашем случае 7) может быть представлено в виде серии дополнений (например, 8 + (-1), так как вычитание действительно просто происходит неправильно). Это позволяет представить любой оператор умножения как эквивалентную последовательность операторов умножения, которая будет иметь тот же результат:
x * 7
= x * (8 + (-1))
= (x * 8) + (x * (-1))
= (x * 8) - (x * 1)
= (x * 8) - x
Оператор побитового сдвига по существу просто умножает или делит число на мощность 2. Пока ваше уравнение имеет дело только с такими значениями, смещение битов может использоваться для замены всего возникновения оператор умножения.
(x * 8) - x = (x * 2 3) - x = (x < 3) - x
Аналогичная стратегия может быть использована для любого другого целого числа, и не имеет значения, является ли это нечетным или четным.
Это то же самое, что и x*8-x = x*(8-1) = x*7
Любое число, нечетное или четное, может быть выражено как сумма степеней двух. Например,
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
Итак, вы можете умножить x на любое число, выполнив правильный набор сдвигов и добавив.
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
Когда дело доходит до этого, умножение на положительное целое можно сделать следующим образом:
int multiply(int a, int b) {
int ret = 0;
for (int i=0; i<b; i++) {
ret += b;
}
return ret;
}
Эффективное? Едва. Но он правильный (факторинг в пределах по ints и т.д.).
Таким образом, использование сдвига влево - это просто ярлык для умножения на 2. Но как только вы дойдете до наивысшей мощности-2 в b, просто добавьте a необходимое количество раз, поэтому:
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;
}
или что-то близкое к этому.
Иными словами, умножить на 7.
b 3 раза.Однажды вечером я обнаружил, что мне очень скучно, и приготовил это:
#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;
}
Приведенный выше код должен быть совершенно понятным, поскольку я старался максимально упростить его. Он должен работать, более или менее, способом, которым процессор может выполнять эти операции. Единственная ошибка, о которой я знаю, заключается в том, что a не разрешается превышать 32 767, а b не допускается достаточно большим для переполнения a (то есть переполнение переполнения не обрабатывается, поэтому 64- битные результаты невозможны). Он должен работать даже с отрицательными числами, если входы соответствуют reinterpret_cast<>.
O (log (b)) метод
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);
}
Ресурсный код работает следующим образом:
Базовый блок:
если любое из чисел 0, произведение равно 0.
если b = 1, product = a.
Если b четно:
ab можно записать как 2a (b/2)
2a (b/2) = (a + a) (b/2) = (a + a) (b → 1) где ' → ' арифметический оператор правого сдвига в java.
Если b нечетно:
ab может быть записано как a + a (b-1)
а + а (б-1) = а + 2а (B-1)/2 = а + (а + а) (б-1)/2 = а + (а + а) ((б-1) → 1)
Так как b нечетно (b-1)/2 = b/2 = b → 1
Итак, ab = a + (2a * (b → 1))
ПРИМЕЧАНИЕ: каждый рекурсивный вызов b уменьшается наполовину = > O (log (b))
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;
}
@Wang, это хорошее обобщение. Но вот немного более быстрая версия. Но он не предполагает переполнения и a неотрицателен.
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;
}
Он будет занимать не более 1 + log_2 (a) раз. Может быть быстрее, если вы замените a и b, когда a > b.
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;
}
Я избегал знакового бита, потому что это не тема поста. Это реализация того, что сказал Уэйн Конрад. Еще одна проблема заключается в том, что вы хотите попробовать более низкие математические операции. Project Euler - это классно!
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));
}
}
Сдвиг и добавление не работают (даже с расширением знака), когда мультипликация отрицательна. Подписанное умножение должно быть выполнено с помощью Бут-кодировка:
Начиная с LSB, изменение от 0 до 1 равно -1; изменение от 1 до 0 равно 1, в противном случае 0. Существует также неявный дополнительный бит 0 ниже LSB.
Например, номер 5 (0101) будет кодироваться как: (1) (- 1) (1) (- 1). Вы можете убедиться, что это правильно:
5 = 2 ^ 3 - 2 ^ 2 + 2 -1
Этот алгоритм также работает с отрицательными числами в 2 форме дополнения:
-1 в 4-битном дополнении - 1111. Используя алгоритм Бута: (1) (0) (0) (0) (- 1), где нет места для самого левого бита 1, получаем: (0) (0) (0) (-1), которая равна -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;
}
Приведенный выше код не проверяет переполнение. Ниже приведена небольшая версия, которая умножает два 16-разрядных номера и возвращает 32-битное число, поэтому оно никогда не переполняется:
/* 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;
}
Если вы можете использовать функцию журнала:
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;
}
Если вы не можете использовать функцию журнала:
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;
}
Я нашел это более эффективным:
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;
}
и еще один способ.
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;
}
JAVA:. Учитывая тот факт, что каждое число можно разделить на степени двух:
1 = 2 ^ 0
2 = 2 ^ 1
3 = 2 ^ 1 + 2 ^ 0
...
Мы хотим получить x где: x = n * m
Поэтому мы можем добиться этого, выполнив следующие шаги:
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
Пример реализации с использованием рекурсии:
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));
}
Я получил этот вопрос на последнем собеседовании, и этот ответ был принят. EDIT: решение для положительных чисел
Это простейшее решение C99/C11 для положительных чисел:
unsigned multiply(unsigned x, unsigned y) { return sizeof(char[x][y]); }
Другой ответ на вопрос:
BigDecimal a = new BigDecimal(123);
BigDecimal b = new BigDecimal(2);
BigDecimal result = a.multiply(b);
System.out.println(result.intValue());
В С#:
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();
}
Завершить его. Запустите цикл семь раз и итерации по числу, которое вы умножаете на семь.
псевдокод:
total = 0
multiply = 34
loop while i < 7
total = total + multiply
endloop
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);
}
Пусть N - число, которое мы хотим умножить на 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
Как мы знаем, левое смещение любого числа на один бит умножает его на 2. Следовательно, умножение любого числа на 8 эквивалентно праву, смещающему его на 3 бита
N x 7 = (N << 3) - N
Я нашел это описание здесь http://www.techcrashcourse.com/2016/02/c-program-to-multiply-number-by-7-bitwise-operator.html
Надеюсь, это поможет.
Очень просто, приятель... Каждый раз, когда вы оставляете сдвиг числа, это означает, что вы умножаете число на 2, что означает, что ответ равен (x < 3) -x.
Чтобы умножить два числа без оператора *:
int mul(int a,int b) {
int result = 0;
if(b > 0) {
for(int i=1;i<=b;i++){
result += a;
}
}
return result;
}
Уродливый, медленный и непроверенный, но...
int mult(a,b){
int i, rv=0;
for(i=0; i < 31; ++i){
if(a & 1<<i){
rv += b << i;
}
}
if(a & 1<<31){ // two complement
rv -= b<<31;
}
return rv;
}