What does this do, and WHy?!?!?!?

This is a discussion on What does this do, and WHy?!?!?!? within the C++ Programming forums, part of the General Programming Boards category; int middleX = SCREEN_WIDTH >> 1;...

  1. #1
    Shadow12345
    Guest

    What does this do, and WHy?!?!?!?

    int middleX = SCREEN_WIDTH >> 1;

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    It's bitshifting.
    If you shift the bits to the left you multiply the number, if you shift the bits to the right (as in this case) you divide it.

    Shifting 1 step to the right divides the number by 2 (2^1 = 2)
    Shifting 2 steps equals to division by 4 (2^2 = 4)
    Shifting 3 steps equals to division by 8 (2^3 = 8)
    and so on...

    The middle of the screen is the screen's width divided by two, so the width is shifted one step to the right.

    Bitshifting is faster than normal multiplication.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Me want cookie! Monster's Avatar
    Join Date
    Dec 2001
    Posts
    680
    Have you never seen that before? It's a (fast) division by 2.
    Double shift is division by 4 and so on (left shift is multiply).

    Divide by 2: >> 1
    Multiply by 4: >> 2
    Divide by 8: >> 3

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    559
    Originally posted by Monster
    Have you never seen that before? It's a (fast) division by 2.
    Double shift is division by 4 and so on (left shift is multiply).
    Multiply by 4: >> 2
    Wouldn't that be Multiply by 4: << 2
    Bit shifting isn't my area, though.
    Truth is a malleable commodity - Dick Cheney

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Monster
    Divide by 2: >> 1
    Multiply by 4: >> 2
    Divide by 8: >> 3
    You may want to change >> into <<
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    While we're speaking of bitshifting.
    Multiplication isn't limited to numbers of the form 2^n (2, 4, 8, 16...). You can split what you're multiplying with:

    x * 20
    x * (16 + 4)
    (x * 16) + (x * 4)
    (x << 4) + (x << 2)

    x * 320
    x * (256 + 64)
    (x * 256) + (x * 64)
    (x << 8) + (x << 6)
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  7. #7
    Me want cookie! Monster's Avatar
    Join Date
    Dec 2001
    Posts
    680
    Originally posted by salvelinus
    Wouldn't that be Multiply by 4: << 2
    Bit shifting isn't my area, though.
    You're right, my mistake

  8. #8
    Seeking motivation... endo's Avatar
    Join Date
    May 2002
    Posts
    537
    Thats very handy, I'll have to write that down

    Its the only explanation I've clearly understood...
    Couldn't think of anything interesting, cool or funny - sorry.

  9. #9
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    dont bother writing x << 2 instead of x * 4

    any 1/10th decent compiler will optimize it for you
    hello, internet!

  10. #10
    Shadow12345
    Guest
    Okay cool. I've seen it tons of times, but, well, I had no clue what was going on. So when the side with two prongs are facing the left it is division by a power of 2
    that is why
    a number >> 4
    is the same as
    a number / (2 * 2 * 2 * 2)
    and when it is the other way it is multiplication.

    Umm, I hate to be a little buttmonger, but, why exactly is it faster than regular multiplication and division? I mean, aren't you ultimately shifting bits anyway?

  11. #11
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Shadow12345

    Umm, I hate to be a little buttmonger, but, why exactly is it faster than regular multiplication and division? I mean, aren't you ultimately shifting bits anyway?
    Because the compilers are stupid. A good compiler will relize that
    x*2 == x << 1
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Shadow12345
    Umm, I hate to be a little buttmonger, but, why exactly is it faster than regular multiplication and division? I mean, aren't you ultimately shifting bits anyway?
    When multiplying the compiler does use bitshifting, but it needs extra code for parting up the shifts as I showed above. If you use bitshifting directly instead of *, you're saving the compiler that trouble thus making your program faster.
    It's true though that modern compilers should optimize this, but you can never be sure .
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  13. #13
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I wrote this program to clock the time it takes for a multiplication and a shifting to do the same task.
    If you want to see how optimized your compiler is,
    try and run it (remove conio.h and getch() if you are non-Borlanders ).
    Code:
    #include <windows.h>
    #include <iostream.h>
    #include <values.h>
    #include <conio.h>
    
    int main()
    {
       DWORD StartTime;
       DWORD EndTime;
       DWORD MultiAct1;
       DWORD MultiAct2;
       DWORD MultiAct3;
       DWORD ShiftAct1;
       DWORD ShiftAct2;
       DWORD ShiftAct3;
    
       int i;
       int NrOfLoops = (MAXINT / 5);
       long int TempVar;
    
       cout << "Press any key to begin" << endl;
       getch();
       cout << "...processing, please wait!  ";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = i * 8;
       EndTime = GetTickCount();
       MultiAct1 = EndTime - StartTime;
       cout << "#";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = (i << 3);
       EndTime = GetTickCount();
       ShiftAct1 = EndTime - StartTime;
       cout << "#";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = i * 66;
       EndTime = GetTickCount();
       MultiAct2 = EndTime - StartTime;
       cout << "#";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = (i << 6) + (i << 1);
       EndTime = GetTickCount();
       ShiftAct2 = EndTime - StartTime;
       cout << "#";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = i * 255;
       EndTime = GetTickCount();
       MultiAct3 = EndTime - StartTime;
       cout << "#";
    
       StartTime = GetTickCount();
       for(i=0; i<NrOfLoops; i++) TempVar = (i << 7) + (i << 6) + (i << 5) + (i << 4) + (i << 3) + (i << 2) + (i << 1) + i;
       EndTime = GetTickCount();
       ShiftAct3 = EndTime - StartTime;
       cout << "#" << endl << endl;;
    
       cout << "Results:" << endl << endl;
       cout << "Nr:\t8\t66\t255" << endl;
       cout << "----------------------------------" << endl;
       cout << "Multi:\t" << MultiAct1 << "\t" << MultiAct2 << "\t" << MultiAct3 << endl;
       cout << "Shift:\t" << ShiftAct1 << "\t" << ShiftAct2 << "\t" << ShiftAct3 << endl;
       getch();
    
       return 0;
    }
    I got some interesting results. I ran it several times to be sure.
    When multiplying with 8, shifting is faster, when multiplying with 255, both have equal time,
    BUT when multiplying with 66, the normal multiplication was faster (or at equal time, but never slower).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  14. #14
    Registered User
    Join Date
    Oct 2002
    Posts
    160
    If that's true then it's kind of imposible to know which one to use when you don't know the values.
    Well english isn't my first language, (it's instead a useless language called danish which only 5 milion people speak!!) so if you think my grammar SUCKS (it does by the way) than you're more then welcome to correct me.
    Hell I might even learn something

  15. #15
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Magos
    I wrote this program to clock the time it takes for a multiplication and a shifting to do the same task.
    If you want to see how optimized your compiler is,
    try and run it
    Heh. My compiler was too smart, it removed the loops, making every calculation take 0 ms.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21