# bitwise multiplication without * sign

How can i make something like:
x * 0x01010101 in to a bitwise operator without using the * sign?

I was able to subtract without using -
x = (x - ((x >> 1) & var));
became
x = (x + (~((x >> 1) & var)) + 1);

i was hoping there was something like that.. but for multiplication?
LVL 1
###### Who is Participating?

Senior Software Engineer (Avast)Commented:
Every time you bit-shift to the left you are performing a 2 x multiplication. Every time you bit-shift to the right you are doing a divide by two.

0x01010101 << 2 == 0x10101010

0x01010101 == 85
0x10101010 == 170

170 / 85 == 2
0

Commented:
>>>> Every time you bit-shift to the left you are performing a 2 x multiplication. Every time you bit-shift to the right you are doing a divide by two.

==> you need to express x as a sum of power of two operands. Then do the appropriate bitshifts.
0

Commented:
a * b = (1*a1 + 2*a2 + 4*a3 + ... + 2^31*a31) * b =

a1 * b + 2 * a2 * b + ... + 2^31 * a31 * b

where ai = is either 1 if the i-th bit of a was set or 0.

All partial products in the last expression can be made by bit-shift operation on b.

0

Author Commented:
I'm not sure how to do this because the value of x is all over the map:

x = 16843009

x = 118429471

x = 135272479

x = 84413200

x = 16843010

x = 118429470

x = 135272479

x = 67767826

x = 16843010

x = 118429470

x = 135272480

x = 34015501

x = 16843011

x = 118429469

x = 0

x = 50792718

x = 16843010

x = 118429470

x = 1

x = 67570446

0

Commented:
>>>> I'm not sure how to do this because the value of x is all over the map:

You would do it by a loop from 0 to 31 where you test on each bit of one of the operands:

int multiplication(unsigned int a, unsigned int b)
{
__int64 temp = 0;
__int64 sum  = 0;

for (int i = 0; i < 32; ++i)
{
if ((a&(1<<i)) != 0)
(
// use the 64-bit temp to assign b and make a bitshift left by i
// then add it to sum

...
}

}
// Here you have to cast the 64-bit sum to 32 -bit and return it (cause it is the product of a*b)
// Or you throw an exception if there is an 32-bit overflow
...
}

Note, I didn't give full code cause it probably is some kind of homework
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.