Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Bitwise operation for division

Reply
Thread Tools

Bitwise operation for division

 
 
Jerry
Guest
Posts: n/a
 
      03-02-2005
I want an algorithm that do arithmetic operations(divide,mutiply,add
etc.)just using bitwise operators:<<,>>,&,|,^;



For example,how "a/10" can be implemented.

I just want a hint.

Thanks.

 
Reply With Quote
 
 
 
 
Walter Roberson
Guest
Posts: n/a
 
      03-02-2005
In article <(E-Mail Removed). com>,
Jerry <(E-Mail Removed)> wrote:
:I want an algorithm that do arithmetic operations(divide,mutiply,add
:etc.)just using bitwise operators:<<,>>,&,|,^;

:For example,how "a/10" can be implemented.

:I just want a hint.

Think "long division".
--
Beware of bugs in the above code; I have only proved it correct,
not tried it. -- Donald Knuth
 
Reply With Quote
 
 
 
 
Chris Williams
Guest
Posts: n/a
 
      03-02-2005
Jerry wrote:
> I want an algorithm that do arithmetic operations(divide,mutiply,add
> etc.)just using bitwise operators:<<,>>,&,|,^;
>
> For example,how "a/10" can be implemented.
>


Oddly enough, just the other day I figured out how to do increment or
decrement by a value 2^n. With enough fiddling you could do arbitrary
addition and subtraction by any value (2's complement if you want to
use for signed values.) Some more fiddling would allow you to use 100
byte or 200 byte values--though you could do the same using + and -
creatively.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define INT_BIT (CHAR_BIT * sizeof(int))

int main(void) {
int L, leftShift, i, changeMask;

leftShift = 0; /* added or subtracted value will be 2^leftShift */
i = 25; /* value we are adding to or subtracting from */
changeMask = 1 << leftShift;

for (L = leftShift; L < INT_BIT; L++) {
i ^= changeMask;
if ( /* ! */ (i & changeMask)) { /* comment in or out "!" for
addition or subtraction */
break;
}
changeMask <<= 1;
}

printf("%i", i);

return 0;
}

Knowing that this would work came about from fiddling with a binary
tree (...it would take a bit to explain beyond that.) Though I am not
sure there is any point in creating such code--I do believe that
processors boil down mathematical operations to logical operations, but
I would have to assume intel has a better algorithm than this.

-Chris

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-02-2005
Jerry wrote:
>
> I want an algorithm that do arithmetic operations (divide, mutiply,
> add etc.) just using bitwise operators:<<,>>,&,|,^;
>
> For example,how "a/10" can be implemented.
>
> I just want a hint.


<http://cbfalconer.home.att.net/download/dubldabl.txt>

--
Chuck F ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      03-02-2005
"Jerry" <(E-Mail Removed)> writes:
> I want an algorithm that do arithmetic operations(divide,mutiply,add
> etc.)just using bitwise operators:<<,>>,&,|,^;
>
>
>
> For example,how "a/10" can be implemented.
>
> I just want a hint.


Um, why do you want to do this? My first thought is that if you want
to do division, just use the "/" operator; that's what it's there for.

I'm not implying that you shouldn't do this, but we can probably be
more helpful if we understand the rationale. It can also be useful in
nailing down the requirements; did you mean to exclude the unary "~"
operator, or was that just an oversight?

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Jerry
Guest
Posts: n/a
 
      03-02-2005
The situation is such:
We are processing a project porting products on Windows platform to
Mac. OS.,and,we are not familar with Mac.so there are always some
troublesome things bother us.
Today my partner want a QWORD data type and want to use 'sturct' to
difine QWORD variables,and,do artithmetics operations with such
variables.
I remember that there are methods that can do this just using BitwiSe
operation.
If popssible,it should be convenient.
That's the orignal of all.
Thanks again.^_~

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      03-02-2005
"Jerry" <(E-Mail Removed)> writes:
> The situation is such:
> We are processing a project porting products on Windows platform to
> Mac. OS.,and,we are not familar with Mac.so there are always some
> troublesome things bother us.
> Today my partner want a QWORD data type and want to use 'sturct' to
> difine QWORD variables,and,do artithmetics operations with such
> variables.
> I remember that there are methods that can do this just using BitwiSe
> operation.


I'm not sure how big a QWORD is, but if you want to implement, say,
128-bit arithmetic on a system that only supports 64-bit arithmetic,
bitwise operators are not the best approach. For addition, for
example, it's going to be a lot easier to use addition on the lower
and upper halves with a little extra code to handle carries. The
technique is well known (but I don't know the details).

I'm sure it's possible using just bitwise operators, but it's going to
be slow, difficult, and error-prone.

(If a QWORD is 64 bits, there's a good chance your compiler supports
it directly, probably as "long long".)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Chris Williams
Guest
Posts: n/a
 
      03-02-2005
Keith Thompson wrote:
> I'm not sure how big a QWORD is, but if you want to implement, say,
> 128-bit arithmetic on a system that only supports 64-bit arithmetic,
> bitwise operators are not the best approach. For addition, for
> example, it's going to be a lot easier to use addition on the lower
> and upper halves with a little extra code to handle carries. The
> technique is well known (but I don't know the details).
>
> I'm sure it's possible using just bitwise operators, but it's going

to
> be slow, difficult, and error-prone.
>
> (If a QWORD is 64 bits, there's a good chance your compiler supports
> it directly, probably as "long long".)


A QWORD is 64 and DWORD 32.
Doing a search for "64-bit mac apple c++" (c++ so it will be less
likely to be ignored), it appears that there are probably "long long"
and "unsigned long long" in the Mac world.
Looking at my Windows header files, it looks like you will want to try:

typedef unsigned long long QWORD;

And that would be that.

-Chris

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing division operation. bhargava.ram VHDL 0 02-18-2010 10:02 AM
bitwise AND operation in xslt biswaranjan.rath XML 3 11-12-2008 03:14 PM
division by 7 without using division operator krypto.wizard@gmail.com C Programming 94 02-09-2007 06:57 AM
Bitwise Operation Pasquale Imbemba Java 2 05-06-2004 11:19 PM
Fast Division/Modulo Operation silentlights C Programming 8 04-23-2004 12:21 PM



Advertisments