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
braker15Asked:
Who is Participating?
 
evilrixConnect With a Mentor 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
 
itsmeandnobodyelseCommented:
>>>> 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
 
itsmeandnobodyelseConnect With a Mentor 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
 
braker15Author 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
 
itsmeandnobodyelseCommented:
>>>> 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.

All Courses

From novice to tech pro — start learning today.