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

- 141.1K All Categories
- 104.5K Programming Languages
- 6.4K Assembler Developer
- 1.8K Basic
- 39.8K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 508 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 311 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 726 Computer Hardware
- 3.4K Database & SQL
- 522 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 256 XML Development
- 3.3K Classifieds
- 195 Co-operative Projects
- 182 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.2K Miscellaneous
- 3 Join the Team
- 0 User Profiles
- 349 Comments on this site
- 59 Computer Emulators
- 2K General programming
- 178 New programming languages
- 609 Off topic board
- 164 Mobile & Wireless
- 38 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 19 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 885 Software Development
- 405 Algorithms
- 68 Object Orientation
- 87 Project Management
- 90 Quality & Testing
- 234 Security
- 7.5K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 33 JQuery
- 286 WEB Servers
- 145 WEB-Services / SOAP

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?

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

9,765Member ✭✭✭: 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]

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?

: :

:

:

: 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

9,765Member ✭✭✭: :

: 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]

29Member: [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);

33MemberHere'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.

29Member:

: 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

3,711Member: using bitwise operations.

:

???

Sure they are, it is ANSI C.

29Member: : 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?

3,711Member: : : 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.

29Member: : : : 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...