Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

bitwise multiplication / division

luzhellluzhell Posts: 29Member
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 Posts: 9,765Member ✭✭✭
    [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 Posts: 29Member
    : [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 Posts: 9,765Member ✭✭✭
    [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 Posts: 29Member
    : 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 Posts: 33Member

    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 Posts: 29Member
    [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 Posts: 3,711Member
    : Bit wise operations are not portable.This is a major drawback of
    : using bitwise operations.
    :


    ???
    Sure they are, it is ANSI C.
  • luzhellluzhell Posts: 29Member
    : : 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 Posts: 3,711Member
    : : : 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 Posts: 29Member
    : : : : 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.