# Bitwise operation for division

Discussion in 'C Programming' started by Jerry, Mar 2, 2005.

1. ### JerryGuest

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.

Jerry, Mar 2, 2005

2. ### Walter RobersonGuest

In article <>,
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.

Think "long division".
--
Beware of bugs in the above code; I have only proved it correct,
not tried it. -- Donald Knuth

Walter Roberson, Mar 2, 2005

3. ### Chris WilliamsGuest

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

Chris Williams, Mar 2, 2005
4. ### CBFalconerGuest

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

CBFalconer, Mar 2, 2005
5. ### Keith ThompsonGuest

"Jerry" <> 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.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Mar 2, 2005
6. ### JerryGuest

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

Jerry, Mar 2, 2005
7. ### Keith ThompsonGuest

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

Keith Thompson, Mar 2, 2005
8. ### Chris WilliamsGuest

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

Chris Williams, Mar 2, 2005

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.