Bitwise operation for division

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

  1. Jerry

    Jerry Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. 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
    #3
  4. Jerry

    CBFalconer Guest

    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
    #4
  5. "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
    #5
  6. Jerry

    Jerry Guest

    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
    #6
  7. "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
    #7
  8. 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
    #8
    1. Advertising

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.
Similar Threads
  1. Pasquale Imbemba

    Bitwise Operation

    Pasquale Imbemba, May 6, 2004, in forum: Java
    Replies:
    2
    Views:
    540
    Roedy Green
    May 7, 2004
  2. biswaranjan.rath

    bitwise AND operation in xslt

    biswaranjan.rath, May 8, 2006, in forum: XML
    Replies:
    3
    Views:
    4,889
    shaunroe
    Nov 12, 2008
  3. silentlights

    Fast Division/Modulo Operation

    silentlights, Apr 16, 2004, in forum: C Programming
    Replies:
    8
    Views:
    994
    Dik T. Winter
    Apr 23, 2004
  4. Replies:
    94
    Views:
    4,487
    ┬Ča\\/b
    Feb 9, 2007
  5. bhargava.ram

    Implementing division operation.

    bhargava.ram, Feb 18, 2010, in forum: VHDL
    Replies:
    0
    Views:
    1,121
    bhargava.ram
    Feb 18, 2010
Loading...

Share This Page