?
Solved

bitwise multiplication without * sign

Posted on 2009-04-22
5
Medium Priority
?
473 Views
Last Modified: 2012-05-06
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?
0
Comment
Question by:braker15
  • 3
5 Comments
 
LVL 40

Accepted Solution

by:
evilrix earned 1000 total points
ID: 24212333
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
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24212598
>>>> 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
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 1000 total points
ID: 24212677
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
 
LVL 1

Author Comment

by:braker15
ID: 24214031
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
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24219926
>>>> 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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question