Bitwise operation for division

J

Jerry

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.
 
W

Walter Roberson

: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".
 
C

Chris Williams

Jerry said:
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
 
K

Keith Thompson

Jerry said:
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?
 
J

Jerry

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.^_~
 
K

Keith Thompson

Jerry said:
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".)
 
C

Chris Williams

Keith said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Bitwise Operations 9
bitwise operation... 13
String of digits, certain radix, perform division 5
BItwise Operation ... 5
Division and Modular Reduction 1
bitwise decimal operators 2
Bitwise operators 14
bitwise on float 44

Staff online

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top