bitwise multiplication / division - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# bitwise multiplication / division

Posts: 29Member
hello
does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
«1

• Posts: 9,765Member ✭✭✭
[b][red]This message was edited by stober at 2005-3-9 11:1:43[/red][/b][hr]
: hello
: does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
:

Of course its possible. Just use very basic C operators
[code]
int i = 1;
// multiply by 2^2
i <<= 2;
// multiply by 2^3
i <<= 3;
// multiply by 2^4
i <<= 4;
// multiply by 2^8
i <<= 8;

[/code]

• Posts: 29Member
: [b][red]This message was edited by stober at 2005-3-9 11:1:43[/red][/b][hr]
: : hello
: : does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
: :
:
:
: Of course its possible. Just use very basic C operators
: [code]
: int i = 1;
: // multiply by 2^2
: i <<= 2;
: // multiply by 2^3
: i <<= 3;
: // multiply by 2^4
: i <<= 4;
: // multiply by 2^8
: i <<= 8;
:
: [/code]
:
:
Thx for your reply, but i wanted to know if its possible to multiply by 3 or 5 or 77 using the bitwise operators. I could not find anything about this
• Posts: 9,765Member ✭✭✭
[b][red]This message was edited by stober at 2005-3-9 14:45:51[/red][/b][hr]
: :
: Thx for your reply, but i wanted to know if its possible to multiply by 3 or 5 or 77 using the bitwise operators. I could not find anything about this
:

you could use shifts and addition
[code]
int main()
{
int i = 1;
int k = (i << 1) + i; // i * 3
cout << k << endl;
k = (i << 3) - i; // i * 7
cout << k << endl;
cin.ignore();
return 0;
}
[/code]
• Posts: 29Member
: you could use shifts and addition
: [code]
: int main()
: {
: int i = 1;
: int k = (i << 1) + i; // i * 3
: cout << k << endl;
: k = (i << 3) - i; // i * 7
: cout << k << endl;
: cin.ignore();
: return 0;
: }
: [/code]
:
:
thx again.
i have one last question: can i multiply two values given by variables?

int x = 3;
int y = 5;
printf("%d
", x * y);

• Posts: 33Member

Here's a rudimentary algorithm

unsigned long product(unsigned x,unsigned y) {
unsigned long p = x;

while(y > 0) {
if(y & 1) p += x;
x <<= 1;
y >>= 1;
}
return p;
}

You can make the necessary conversions for signed integgers
according to -x * y = -(x * y) and so on.This algorithm
works slightly faster if x > y.So, you can add
if(y > x) swap(&x,&y); at the begining, or simply
if(y > x) return product(y,x);

Bit wise operations are not portable.This is a major drawback of
using bitwise operations.
• Posts: 29Member
[b][red]This message was edited by luzhell at 2005-3-11 2:51:1[/red][/b][hr]
:
: Here's a rudimentary algorithm
:
: unsigned long product(unsigned x,unsigned y) {
: unsigned long p = x;
:
: while(y > 0) {
: if(y & 1) p += x;
: x <<= 1;
: y >>= 1;
: }
: return p;
: }
:
: You can make the necessary conversions for signed integgers
: according to -x * y = -(x * y) and so on.This algorithm
: works slightly faster if x > y.So, you can add
: if(y > x) swap(&x,&y); at the begining, or simply
: if(y > x) return product(y,x);
:
: Bit wise operations are not portable.This is a major drawback of
: using bitwise operations.
:

you made a small mistake: p has to be initialized with 0 otherwise the result will be too high. but apart from this it works very well.
1000 thx. you helped me out a lot

• Posts: 3,711Member
: Bit wise operations are not portable.This is a major drawback of
: using bitwise operations.
:

???
Sure they are, it is ANSI C.
• Posts: 29Member
: : Bit wise operations are not portable.This is a major drawback of
: : using bitwise operations.
: :
:
:
: ???
: Sure they are, it is ANSI C.
:
yes, they are standard C.
but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
so it looks like bitwise ops are only useful in multiplication with powers of 2?
• Posts: 3,711Member
: : : Bit wise operations are not portable.This is a major drawback of
: : : using bitwise operations.
: : :
: :
: :
: : ???
: : Sure they are, it is ANSI C.
: :
: yes, they are standard C.
: but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
: so it looks like bitwise ops are only useful in multiplication with powers of 2?
:

Yes, that is correct. Left-shift any integer by 1 should be the same as muliplying it by 2. However, if you are doing this only because you want to optimize your code, you shouldn't need to bother with those things
(I thought it was somekind of homework assignment :-)). If you write x*y in the code, then the compiler will probably choose the fastest method for that. With todays computers, mathematical and binary operations are extremly fast, so what you should focus on when you want to optimize your program is things like loops, arrays, data type sizes and memory copying.
• Posts: 29Member
: : : : Bit wise operations are not portable.This is a major drawback of
: : : : using bitwise operations.
: : : :
: : :
: : :
: : : ???
: : : Sure they are, it is ANSI C.
: : :
: : yes, they are standard C.
: : but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
: : so it looks like bitwise ops are only useful in multiplication with powers of 2?
: :
:
: Yes, that is correct. Left-shift any integer by 1 should be the same as muliplying it by 2. However, if you are doing this only because you want to optimize your code, you shouldn't need to bother with those things
: (I thought it was somekind of homework assignment :-)). If you write x*y in the code, then the compiler will probably choose the fastest method for that. With todays computers, mathematical and binary operations are extremly fast, so what you should focus on when you want to optimize your program is things like loops, arrays, data type sizes and memory copying.
:

yes maybe you're right.
but i don't know how the compiler optimizes code. i'm writing an application for mobile phones so i can't say which optimizations are made or not.
i think i have to wait until i get the specs for the compiler...
«1