Solved

# bitwise multiplication without * sign

Posted on 2009-04-22
Medium Priority
473 Views
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
Question by:braker15
• 3

LVL 40

Accepted Solution

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

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

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

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

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

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 …
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
Course of the Month15 days, 8 hours left to enroll