multiplication using bit operation

Hi

If I need to multiply a number by 2, I can left shift the number by 1 bit.
because shifting left by n bits on a signed or unsigned binary number
has the effect of multiplying it by 2^n (base 2 and power n).
Now if I want to multiple by 3, how can write a C program using bit operations.

please comment

thanks & regards
Onebrother

I don't know how, but I don't think it'll be as simple as 2^n. Why would you want to do this anyways?

You can do that - if you want to make it generic, you will have to do something that checks if the lowest bit of the first multiplicand is 1, add the second multiplicand to the product, then shift the first multiplicand right, and the second multiplicand left.

So for example 10 * 5 = (10 + (10 << 2)).

--
Mats

Very very nice question indeed... Actually you would probably implement it with a shift and add.
If x was the number to multiply by 3, then:
(x<<1)+x is your answer.
The problem is if you can not use arithmetic addition, as bitwise operators can't replace addition i think, except if you use something like... masking all 32 bits and xoring them one bye one? But that would be much slower than the original addition no? And a mess code too.

Quote:

---

Originally Posted by xuftugulus

Very very nice question indeed... Actually you would probably implement it with a shift and add.
If x was the number to multiply by 3, then:
(x<<1)+x is your answer.
The problem is if you can not use arithmetic addition, as bitwise operators can't replace addition i think, except if you use something like... masking all 32 bits and xoring them one bye one? But that would be much slower than the original addition no? And a mess code too.

---

thanks for your reply...

what is the equivalent bit operation if I want to divide a number
by 3, as right shift of a number by n bits is equivalent of dividing it by 2^n.

Quote:

---

what is the equivalent bit operation if I want to divide a number
by 3, as right shift of a number by n bits is equivalent of dividing it by 2^n.

---

I think you may have to implement a division algorithm yourself, like what xuftugulus mentioned about implementing addition in general with bitwise operators.

multiplying x by 3 using bit operation in general as you explained is

(x<<1) + x

But say if I want to multiply (x=) 3 by 5 then how this will work?

because left shifting 3 by 1 bit will result 6 & adding 3 to it will be 9 only. It
does not become 15.

please comment

Quote:

---

But say if I want to multiply (x=) 3 by 5 then how this will work?

---

(5 << 1) + 5 = 10 + 5 = 15

As you noted, the formula works for multiply by 3, not multiply by 5.

Hint: 5 == 4 + 1

Quote:

---

Originally Posted by onebrother

Hi

If I need to multiply a number by 2, I can left shift the number by 1 bit.
because shifting left by n bits on a signed or unsigned binary number
has the effect of multiplying it by 2^n (base 2 and power n).
Now if I want to multiple by 3, how can write a C program using bit operations.

please comment

thanks & regards
Onebrother

---

Forgetting basic math? If you have a method of multiplying by two, then you can multiply by three, because 3 * x = 2 * x + x... Right?

Quote:

---

Originally Posted by onebrother

But say if I want to multiply (x=) 3 by 5 then how this will work?

---

How about 5 * x = 4 * x + x? Figure out how to multiply by 4 with a shift.