# bitwise multiplication / division

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?

• [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]

• : [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
• [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]
• : 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);

• 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.
• [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

• : Bit wise operations are not portable.This is a major drawback of
: using bitwise operations.
:

???
Sure they are, it is ANSI C.
• : : 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?
• : : : 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.
• : : : : 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...
• [b][red]This message was edited by cherio at 2005-3-12 23:26:38[/red][/b][hr]
: : Bit wise operations are not portable.This is a major drawback of
: : using bitwise operations.
: :
:
:
: ???
: Sure they are, it is ANSI C.
:
It is standard C.But not all machines might provide instructions
for performing bitwise operations.
For those that do, the bitwise operators translate directly into
those instructions and are hence efficient, which is why
bitwise operators were included in C.
Fortunately almost all recent architectures at least do, provide
instructions for performing bitwise operations.

This means, that , it is still possible to write non-portable
code in standard C as well.

Besides, the use of these operations are still a bit dicey, on
architectures, where the byte order is reversed for instance.
What does, shifting mean in this case ?

Anyway, the book on good programming practise(I dont remember the
name) by kernighan and pike clearly discourages the use of bitwise
operators, I think for the same portability reason.

• : : : 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?
:

It should be tough, if not impossible to write a function to beat
a multiplication instruction.That instruction would possibly be
using a very good algorithm involving bitwise operations
for accomplishing the task.Besides that instruction will be an order
of times faster to perform its own shifting, and addition operations,
because it uses the internal circuitry, and the algorithm itself is
hardcoded to use the internal adders and so on.

But this and similar algorithms are
devised and used for performing operations on extended integer's
occupying several words for-instance.Of course, various other
alternatives like use of word-multiplication are also possible.

If the machine you are programming for does not provide a built-in
multiplication instruction, only then you might consider devising
your own efficient algorithm for multiplication,otherwise it
should be an unproductive effort.
• : [b][red]This message was edited by cherio at 2005-3-12 23:26:38[/red][/b][hr]
: : : Bit wise operations are not portable.This is a major drawback of
: : : using bitwise operations.
: : :
: :
: :
: : ???
: : Sure they are, it is ANSI C.
: :
: It is standard C.But not all machines might provide instructions
: for performing bitwise operations.
: For those that do, the bitwise operators translate directly into
: those instructions and are hence efficient, which is why
: bitwise operators were included in C.
: Fortunately almost all recent architectures at least do, provide
: instructions for performing bitwise operations.
:
: This means, that , it is still possible to write non-portable
: code in standard C as well.
:
: Besides, the use of these operations are still a bit dicey, on
: architectures, where the byte order is reversed for instance.
: What does, shifting mean in this case ?
:
: Anyway, the book on good programming practise(I dont remember the
: name) by kernighan and pike clearly discourages the use of bitwise
: operators, I think for the same portability reason.
:
:

Heh, can you please mention the last processor made that didn't support bitwise operators? Were it made during the last 25 years? :-)