Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

bitwise multiplication / division

luzhellluzhell Member Posts: 29
hello
does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
«1

Comments

  • stoberstober Member Posts: 9,765 ✭✭✭
    [b][red]This message was edited by stober at 2005-3-9 11:1:43[/red][/b][hr]
    : hello
    : does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
    :


    Of course its possible. Just use very basic C operators
    [code]
    int i = 1;
    // multiply by 2^2
    i <<= 2;
    // multiply by 2^3
    i <<= 3;
    // multiply by 2^4
    i <<= 4;
    // multiply by 2^8
    i <<= 8;

    [/code]




  • luzhellluzhell Member Posts: 29
    : [b][red]This message was edited by stober at 2005-3-9 11:1:43[/red][/b][hr]
    : : hello
    : : does anyone know how muliplication and division can be achieved solely by bitwise operators. That means not only operations involving powers of two, but also any others. Is this possible at all?
    : :
    :
    :
    : Of course its possible. Just use very basic C operators
    : [code]
    : int i = 1;
    : // multiply by 2^2
    : i <<= 2;
    : // multiply by 2^3
    : i <<= 3;
    : // multiply by 2^4
    : i <<= 4;
    : // multiply by 2^8
    : i <<= 8;
    :
    : [/code]
    :
    :
    Thx for your reply, but i wanted to know if its possible to multiply by 3 or 5 or 77 using the bitwise operators. I could not find anything about this
  • stoberstober Member Posts: 9,765 ✭✭✭
    [b][red]This message was edited by stober at 2005-3-9 14:45:51[/red][/b][hr]
    : :
    : Thx for your reply, but i wanted to know if its possible to multiply by 3 or 5 or 77 using the bitwise operators. I could not find anything about this
    :

    you could use shifts and addition
    [code]
    int main()
    {
    int i = 1;
    int k = (i << 1) + i; // i * 3
    cout << k << endl;
    k = (i << 3) - i; // i * 7
    cout << k << endl;
    cin.ignore();
    return 0;
    }
    [/code]
  • luzhellluzhell Member Posts: 29
    : you could use shifts and addition
    : [code]
    : int main()
    : {
    : int i = 1;
    : int k = (i << 1) + i; // i * 3
    : cout << k << endl;
    : k = (i << 3) - i; // i * 7
    : cout << k << endl;
    : cin.ignore();
    : return 0;
    : }
    : [/code]
    :
    :
    thx again.
    i have one last question: can i multiply two values given by variables?

    int x = 3;
    int y = 5;
    printf("%d
    ", x * y);

  • cheriocherio Member Posts: 33

    Here's a rudimentary algorithm

    unsigned long product(unsigned x,unsigned y) {
    unsigned long p = x;

    while(y > 0) {
    if(y & 1) p += x;
    x <<= 1;
    y >>= 1;
    }
    return p;
    }

    You can make the necessary conversions for signed integgers
    according to -x * y = -(x * y) and so on.This algorithm
    works slightly faster if x > y.So, you can add
    if(y > x) swap(&x,&y); at the begining, or simply
    if(y > x) return product(y,x);

    Bit wise operations are not portable.This is a major drawback of
    using bitwise operations.
  • luzhellluzhell Member Posts: 29
    [b][red]This message was edited by luzhell at 2005-3-11 2:51:1[/red][/b][hr]
    :
    : Here's a rudimentary algorithm
    :
    : unsigned long product(unsigned x,unsigned y) {
    : unsigned long p = x;
    :
    : while(y > 0) {
    : if(y & 1) p += x;
    : x <<= 1;
    : y >>= 1;
    : }
    : return p;
    : }
    :
    : You can make the necessary conversions for signed integgers
    : according to -x * y = -(x * y) and so on.This algorithm
    : works slightly faster if x > y.So, you can add
    : if(y > x) swap(&x,&y); at the begining, or simply
    : if(y > x) return product(y,x);
    :
    : Bit wise operations are not portable.This is a major drawback of
    : using bitwise operations.
    :

    you made a small mistake: p has to be initialized with 0 otherwise the result will be too high. but apart from this it works very well.
    1000 thx. you helped me out a lot :)


  • LundinLundin Member Posts: 3,711
    : Bit wise operations are not portable.This is a major drawback of
    : using bitwise operations.
    :


    ???
    Sure they are, it is ANSI C.
  • luzhellluzhell Member Posts: 29
    : : Bit wise operations are not portable.This is a major drawback of
    : : using bitwise operations.
    : :
    :
    :
    : ???
    : Sure they are, it is ANSI C.
    :
    yes, they are standard C.
    but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
    so it looks like bitwise ops are only useful in multiplication with powers of 2?
  • LundinLundin Member Posts: 3,711
    : : : Bit wise operations are not portable.This is a major drawback of
    : : : using bitwise operations.
    : : :
    : :
    : :
    : : ???
    : : Sure they are, it is ANSI C.
    : :
    : yes, they are standard C.
    : but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
    : so it looks like bitwise ops are only useful in multiplication with powers of 2?
    :

    Yes, that is correct. Left-shift any integer by 1 should be the same as muliplying it by 2. However, if you are doing this only because you want to optimize your code, you shouldn't need to bother with those things
    (I thought it was somekind of homework assignment :-)). If you write x*y in the code, then the compiler will probably choose the fastest method for that. With todays computers, mathematical and binary operations are extremly fast, so what you should focus on when you want to optimize your program is things like loops, arrays, data type sizes and memory copying.
  • luzhellluzhell Member Posts: 29
    : : : : Bit wise operations are not portable.This is a major drawback of
    : : : : using bitwise operations.
    : : : :
    : : :
    : : :
    : : : ???
    : : : Sure they are, it is ANSI C.
    : : :
    : : yes, they are standard C.
    : : but after testing it i came to the conclusion that the algorithm provides no speed improvements due to its comparisons and the function call (i guess). even inlining had no better performance than x*y.
    : : so it looks like bitwise ops are only useful in multiplication with powers of 2?
    : :
    :
    : Yes, that is correct. Left-shift any integer by 1 should be the same as muliplying it by 2. However, if you are doing this only because you want to optimize your code, you shouldn't need to bother with those things
    : (I thought it was somekind of homework assignment :-)). If you write x*y in the code, then the compiler will probably choose the fastest method for that. With todays computers, mathematical and binary operations are extremly fast, so what you should focus on when you want to optimize your program is things like loops, arrays, data type sizes and memory copying.
    :

    yes maybe you're right.
    but i don't know how the compiler optimizes code. i'm writing an application for mobile phones so i can't say which optimizations are made or not.
    i think i have to wait until i get the specs for the compiler...
«1
Sign In or Register to comment.