Как выполнить умножение, используя побитовые операторы?

Question

Я работаю над проблемой, которую мне удалось решить, за исключением последней части - я не уверен, как можно умножить, используя побитовые операторы:

0*8 = 0

1*8 = 8

2*8 = 16 

3*8 = 24 

4*8 = 32

Можете ли вы порекомендовать подход для решения этой проблемы?

Answer 1

Для умножения на любое значение от 2 до степени N (то есть 2 ^ N) сдвиньте биты N раз влево.

0000 0001 = 1 

times 4 = (2^2 => N = 2) = 2 bit shift : 0000 0100 = 4

times 8 = (2^3 -> N = 3) = 3 bit shift : 0010 0000 = 32

и т.д ..

Чтобы разделить, сдвиньте биты вправо.

Биты целые 1 или 0 - вы не можете сдвинуться на часть бита, поэтому, если число, на которое вы умножаете, не учитывает целое значение N то есть.

since: 17 = 16  + 1 
thus:  17 = 2^4 + 1

therefore: x * 17 = (x * 16) + x in other words 17 x's  

, таким образом, чтобы умножить на 17, нужно сделать 4-битный сдвиг влево, а затем снова добавить исходное число:

==> x * 17 = (x * 2^4) + x 
==> x * 17 = (x shifted to left by 4 bits) + x 

so let x = 3 = 0000 0011 

times 16 = (2^4 => N = 4) = 4 bit shift : 0011 0000 = 48

plus the x (0000 0011)

т.

    0011 0000  (48)  
+   0000 0011   (3)
=============
    0011 0011  (51)

Редактировать: обновить до исходного ответа. Чарльз Петцольд написал фантастическую книгу «Код» , которая объяснит все это и многое другое самым простым способом. Я настоятельно рекомендую это.

Answer 2

Для умножения двух двоичных кодированных чисел без инструкции умножения. Было бы просто добавить итеративно к продукту.

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while(y--)
        reg += x;
    return reg;
}

Используя битовые операции, можно использовать характеристику кодирования данных. Как объяснено ранее, битовый сдвиг такой же, как умножение на два. С помощью этого сумматор можно использовать на двух степенях.

// multiply two numbers with bit operations

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while (y != 0)
    {
        if (y & 1)
        {
            reg += x;
        }
        x <<= 1;
        y >>= 1;
    }
    return reg;
}

Answer 3

public static int multi(int x, int y){
        boolean neg = false;
        if(x < 0 && y >= 0){
            x = -x;
            neg = true;
        }
        else if(y < 0 && x >= 0){
            y = -y;
            neg = true;
        }else if( x < 0 && y < 0){
            x = -x;
            y = -y;
        }

        int res = 0;
        while(y!=0){
            if((y & 1) == 1) res += x;
            x <<= 1;
            y >>= 1;
        }
        return neg ? (-res) : res;
    }

Answer 4

Вы бы умножили множитель на степени 2.
3 * 17 = 3 * (16 + 1) = 3 * 16 + 3 * 1 ... = 0011b << 4 + 0011b </p>

Answer 5

Я считаю, что это должен быть левый сдвиг. 8 равно 2 ^ 3, поэтому сдвиг влево на 3 бита:

2 << 3 = 8 </p>

Answer 6

Я только что понял, что это тот же ответ, что и предыдущий. LOL извините.

public static uint Multiply(uint a, uint b)
{
   uint c = 0;
   while(b > 0)
   {
      c += ((b & 1) > 0) ? a : 0;
      a <<= 1;
      b >>= 1;
   }
   return c;
}

Answer 7

-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
    int mulResult =0;
    int ithBit;

    BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0)   ;
    num1 = abs(num1);
    num2 = abs(num2);


    for(int i=0;i<sizeof(num2)*8;i++)
    {
        ithBit =  num2 & (1<<i);
        if(ithBit>0){
            mulResult +=(num1<<i);
        }

    }

    if (isNegativeSign) {
        mulResult =  ((~mulResult)+1 );
    }

    return mulResult;
}