Bitwise operation for division

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

[Walter Roberson]

In article <11*********************@l41g2000cwc.googlegroups. com>,
Jerry <zi****@gmail.com> 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

[Chris Williams]

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

[CBFalconer]

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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Keith Thompson]

"Jerry" <zi****@gmail.com> 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) ks***@mib.org <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.

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

[Keith Thompson]

"Jerry" <zi****@gmail.com> 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) ks***@mib.org <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.

[Chris Williams]

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