C++ Bitwise ... Stuff

archer1662archer1662 Join Date: 2004-03-30 Member: 27610Members
edited July 2004 in Off-Topic
I'm out to learn C++ (as some of you know from my earlier post) but I've run into something which I can't seem to comprehend at all; Bitwise logical operators and bitwise shift operators (as the book I'm reading puts them)

As I'm reading it, it gives me no help as to what they are and how they are used. It gives me an example for bitwise shift operator:
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Depending on the compiler (and the computer's math capabilities), replacing multiplies or divides with shifts may result in faster and more compact code. For example, consider this statement:

x = y * 10;

Of course, 10 is not a power of two. However, you could rewrite this statement as:

x = y * 8 + y * 2;

Or using <u>shift operators</u>

x = y << 3 + y << 1;

This technique is most useful when you are desperate to make a program run as quickly as possible.<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->

Ok, I understand the first and second examples, but WHAT is the last one supposed to mean ?

Comments

  • OttoDestructOttoDestruct Join Date: 2002-11-08 Member: 7790Members
    Eh. Bitwise blows tbh. IIRC it deals a lot with shifting numbers around in binary, personally I think anyone who uses it needs to be shot, as I don't feel like taking my time looking through a bigarse algorightm figuring out mathematics I _could_ be doing at a glance.
  • WheeeeWheeee Join Date: 2003-02-18 Member: 13713Members, Reinforced - Shadow
    edited July 2004
    since binary digits are powers of two, and 8 = 2^3, left-shifting the bits of y by the operation "<< 3" is equivalent to y * 8, and y << 1 is equivalent to y * 2.

    *edit* example:

    let's take base 10 for example, what we're all familiar with.

    let y = 51.

    5 is the second digit, 1 is the first digit.

    now, let's say that we wanted y*120.

    This would break down into y * 100 + y * 10 + y * 10 (we need even powers of 10, since this is a logarithmic function).

    Since 100 = 10^2 and 10 = 10^1, the operation y << 2 + y << 1 + y << 1 would be logically equivalent to y *120.

    to do this, y << 2 is equivalent of shifting 51's "bits" two spaces to the right - remember, in programming, each number occupies a specific number of digits in memory.

    So, y <<2 = 5100 and y <<1 = 510. so, y <<2 + y<<1 + y <<1 = 5100 + 510 + 510 = 6120.

    now, just use this example, except in base-2 logarithms, and voila, you have bitwise shift operators.

    for example, in a byte, 00001000 is the binary equivalent of 8 in decimal.

    if we apply << 2 to it, it would become 00100000, which is the equivalent of 32 in decimal.

    *edit2* why you would use bitwise shifting: The multiplication algorithm in a CPU's arithmetic logic units, and especially the division algorithm, takes a lot longer than the addition and subtraction algorithms. If you really want a program to go as fast as possible, left- and right-shifting makes it so that you can bypass the multiplication and division instructions.
  • DOOManiacDOOManiac Worst. Critic. Ever. Join Date: 2002-04-17 Member: 462Members, NS1 Playtester
    The only time I've seen bitwise actually used is in the HL SDK when they need to cram lots of data into very few bytes (known as bitpacking).

    Here's a quicker summary than Wheeee's more in depth explaination :P

    Say you got 1 in a variable

    binary is: 0001

    if you bit shift it twice you get:

    0100

    which is 4

    Bit shifting just moves the bits left or right. Don't pay too much attention to it though unless you're writing device drivers or something complex. :P
  • WheeeeWheeee Join Date: 2003-02-18 Member: 13713Members, Reinforced - Shadow
    /me nods at Doomeh, you can use it for bitpacking, although there are functions like __declspec(align) and pack that you can use to pack things fairly well. Don't use shift-packing unless you know WTH you're doing, since it can lead to all sorts of nasty stuff happening, and only if you really really need to get stuff into tiny amounts of space.
  • archer1662archer1662 Join Date: 2004-03-30 Member: 27610Members
    Ok, thanks it makes *much* more sense now
  • Dorian_GrayDorian_Gray Join Date: 2004-02-15 Member: 26581Members, Constellation
    edited July 2004
    I've seen it in exactly two places. First was on a C++ exam, second was in the HL SDK. Not that hard once you get the hang of it, and Doom's explanation was excellent <!--emo&:p--><img src='http://www.unknownworlds.com/forums/html//emoticons/tounge.gif' border='0' style='vertical-align:middle' alt='tounge.gif' /><!--endemo-->
  • [WHO]Them[WHO]Them You can call me Dave Join Date: 2002-12-11 Member: 10593Members, Constellation
    I just wanted to add an opinion. Bit packing is not evil and is sometimes the most elegant solution to around 2% of all data storage. Elegant meaning both efficient and easy to read.
  • archer1662archer1662 Join Date: 2004-03-30 Member: 27610Members
    If I learned them flawlessly, would it be a better coding habit?
  • OttoDestructOttoDestruct Join Date: 2002-11-08 Member: 7790Members
    <!--QuoteBegin-archer1662+Jul 30 2004, 12:11 AM--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (archer1662 @ Jul 30 2004, 12:11 AM)</td></tr><tr><td id='QUOTE'><!--QuoteEBegin--> If I learned them flawlessly, would it be a better coding habit? <!--QuoteEnd--> </td></tr></table><div class='postcolor'> <!--QuoteEEnd-->
    Like everyone else has said, its used in extremely specialized cases. Don't bother. Just know that it exists.
  • SkulkBaitSkulkBait Join Date: 2003-02-11 Member: 13423Members
    As for Bitwise logic operators (|, &, and ^), they are similar to their "logical" logic operators only they are done on a per bit level. For instance:

    <!--c1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->
    With the | (bitwise OR) if both bits are 0 the resulting bit will be 0, otherwise 1.

    decimal 5 = binary 0101
    decimal 3 = binary 0011
    5 | 3 = 7

    0101 |
    0011 =
    0111

    With & (bitwise AND) , if both bits are 1 the resulting bit will be 1, otherwise 0.
    5 & 3 = 1

    0101 &
    0011 =
    0001

    With ^ (bitwise XOR), if both bits are 1 or both bits are 0 the result is 0, otherwise 1.
    5 ^ 3 = 6

    0101 ^
    0011 =
    0110
    <!--c2--></td></tr></table><div class='postcolor'><!--ec2-->

    Often this is used to pack a whole bunch of flags into one parameter, for instance in the SDL_SetVideoMode:
    SDL_SetVideoMode(int width, int height, int bpp, Uint32 flags);
    where flags is any of these options
    SDL_SWSURFACE
    SDL_HWSURFACE
    SDL_ASYNCBLIT
    SDL_ANYFORMAT
    SDL_HWPALETTE
    SDL_DOUBLEBUF
    SDL_FULLSCREEN
    SDL_OPENGL
    SDL_OPENGLBLIT
    SDL_RESIZABLE
    SDL_NOFRAME
    which are #defined to one bit on binary values like 1, 2, 4, 8, 16, ect
    bitwise ORd together, like so:
    SDL_SetVideoMode(640, 480, 32, SDL_HWSURFACE | SDL_DOUBLEBUF | SDL_FULLSCREEN);
    When the function wants to check for these flags, it uses the bitwise AND:
    if(flags & SDL_HWSURFACE)
    {
    //do something
    }

    So lets say we passed the above flags (SDL_HWSURFACE | SDL_DOUBLEBUF | SDL_FULLSCREEN), which had respective valuse of 1, 2 and 4.
    1 = 0001
    2 = 0010
    4 = 0100
    so the resulting value is 0111 or 7 in decimal. Later we want to check for the SDL_DOUBLEBUF flag, so we use bitwise AND:
    0111 &
    0010 =
    0010
    or 2 in decimal, which is greater than 0 and therefor TRUE.
    Now lets say we were checking for SDL_OPENGL which has a value of 8, or 1000 in binary:
    0111 &
    1000 =
    0000
    or 0, and therefore FALSE

    Please forgive me if this doesn't make alot of sense, Its late so my brain isn't working at full capacity.
  • WheeeeWheeee Join Date: 2003-02-18 Member: 13713Members, Reinforced - Shadow
    <!--QuoteBegin-[WHO]Them+Jul 29 2004, 10:43 PM--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> ([WHO]Them @ Jul 29 2004, 10:43 PM)</td></tr><tr><td id='QUOTE'><!--QuoteEBegin--> I just wanted to add an opinion. Bit packing is not evil and is sometimes the most elegant solution to around 2% of all data storage. Elegant meaning both efficient and easy to read. <!--QuoteEnd--> </td></tr></table><div class='postcolor'> <!--QuoteEEnd-->
    i agree, but to someone who is just learning C++, it's best not to mess with bitwise shifting and operators so much. in small programs it's much better to use just a plain bool for flags and such (just a lot less work). sure, it's faster and more efficient, but as my father always says, "get your basics down first."
  • Jim_has_SkillzJim_has_Skillz Join Date: 2003-01-19 Member: 12475Members, Constellation
    Its used a lot in Assembly aswell.

    Here's a big example of what it looks like in assembly language.
    (Take note this is using the intel x386 architecture and the operations in question are, shr and shl which mean shift right and shift left).

    <!--c1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->/*
       This is the function for the logic unit simulator. Given an input: 01ABCDEFh
       if theFlags == X0X0X0X1h then *result = EFh, and so on for other theFlags values  
    */

    __declspec(naked) void
    logicUnit( unsigned long int theValue, unsigned long int theFlags, unsigned char *result )
    {
       __asm{
           // start the code for part A here
     push eax
     push ebx
     push ecx
     push edx
     push esi

     mov esi, dword ptr[esp + 32] // points to the result
     mov ecx, dword ptr[esp + 24] // points to the Value
     mov edx, dword ptr[esp + 28] // points to the Flags

     //Start the Assignment

     mov eax, 00000001000000010000000100000001b // Mask

     and edx, eax

     cmp edx, 00000000000000000000000000000001b
      je FOUND_BYTE1

     cmp edx, 00000000000000000000000100000000b
      je FOUND_BYTE2

     cmp edx, 00000000000000010000000000000000b
      je FOUND_BYTE3

     cmp edx, 00000001000000000000000000000000b
      je FOUND_BYTE4

     jmp OTHER_CASE

    FOUND_BYTE1: // Put theValue into the result
     mov byte ptr[ esi ], cl  
     jmp END_ALL

    FOUND_BYTE2: // Put theValue into the result
     mov byte ptr[ esi ], ch
     jmp END_ALL

    FOUND_BYTE3: // Put theValue into the result
     shr ecx, 16
     mov byte ptr[ esi ], cl
     jmp END_ALL

    FOUND_BYTE4: // Put theValue into the result
     shr ecx, 16
     mov byte ptr[ esi ], ch
     jmp END_ALL

    OTHER_CASE:
     mov eax, 11000000110000001100000011000000b
     and ecx, eax
     
     mov al, 00000000b
     shr ecx, 6

     add al, cl

     shr ecx, 8
     shl ecx, 2
     
     add al, cl

     shr ecx, 10
     shl ecx, 4

     add al, cl

     shr ecx, 12
     shl ecx, 6

     add al, cl

     mov byte ptr[ esi ], al

    END_ALL: // End everything.

     pop esi
     pop edx
     pop ecx
     pop ebx
     pop eax

           ret  // end code for part A.
       }
    }<!--c2--></td></tr></table><div class='postcolor'><!--ec2-->
  • Soylent_greenSoylent_green Join Date: 2002-12-20 Member: 11220Members, Reinforced - Shadow
    edited July 2004
    There is exactly 2 things that I know bitwise operators are commonly used for, one has been mentioned.

    Flags are often dealt with like this:

    //Many flags have some "prefix" in their name to show what they are.
    //They are usually implemented with #defines

    #define DD_SOMETHING1 1 // 1
    #define DD_SOMETHING2 2 // 10
    #define DD_SOMETHING3 4 // 100
    #define DD_SOMETHING4 8 // 1000
    #define DD_SOMETHING5 16 // 10000
    ...

    int DD_flags = DD_SOMETHING1 | DD_SOMETHING5; //with | both flags get set.

    //if a bit is 1 in either DD_SOMETHING1 or DD_SOMETHING5 is will be 1 in DD_flags
    // DD_flags in binary looks like this ...0010001

    //is DD_SOMETHING3 set?
    if ( DD_flags & DD_SOMETHING3 == DD_SOMETHING3 )
    { //do something}

    //turning of a flag
    DD_flags &= ~DD_SOMETHING5;
    //~ is the complement, 1 becomes zero and wise versa. ~DD_SOMETHING5 is ...111101111
    // &= means DD_flags = DD_flags & ...
    // DD_flags & (~DD_SOMETHING5) will allways be 0 for bit 5 since it is zero in
    //~DD_SOMETHING5, and will be 1 for all bits in DD_flags that are 1. The only
    //change in DD_flags is to turn bit nr 5 to a 0, it doesn't matter if it was a 1 or 0 before.

    Bitwise operators are also used in many "checksums" and encryption methods.

    A simple rotating key encryption would do something like have a key, often determined at run-time from something else(such as your current IP), say 0xff2416ab. Then shift the entire 32 bits left and set the first bit to the value of the last one that was shifted out to the left. Every 32 steps the key repeats. When sending data that to someone and you both know the key you XOR the key with 4 bytes of data(if it's a 4 byte key) then send the data and cyclically shift your key one step to the left as above, XOR or with data and send etc. The receiver knows what key you started with and is shifting it the same way you are, to get the message back from the data he XORs it with the key.

    Now, if you know that you are receiving the same data every time and what the data is you can easily figure out the key, this might be the case if rotating key encryption is used to make cheating in multiplayer games harder or something, so if someone is doing simple encryption like this they will usually do something a bit more fancy to prevent this, preveting sending the same data several times in a row.

    Another, very simple, way to encrypt things:

    Sharing a seed value for a decently speedy random number generator that has at least nearly equal probabillity for each bit to be 1 or 0. Then XORing each 32 bits with this random number(if the random number is 32 bits long), the reciever will be able to calculate the same series of random numbers and XORing the message back to it's original form as he has the same random number algorithm and seed value(you could use something like your IP number or your CD-key or whatever as a seed).

    XOR is very usefull because it's reversable if you know what something was originally XORed with.

    edit: I see lots of sloppy spelling errorrors but I'm too lazy to fix them so I'll just put a disclaimer instead <!--emo&:D--><img src='http://www.unknownworlds.com/forums/html//emoticons/biggrin.gif' border='0' style='vertical-align:middle' alt='biggrin.gif' /><!--endemo-->.
  • ZeroByteZeroByte Join Date: 2002-11-01 Member: 3057Members
    Eh, dunno about all the other uses, but I've found doing a &1 operation on an integer value is a nice and fast way of finding out if it's even or odd. The speed difference might not be very appreciable but if you're really out to optimize your program, it's a nice tidbit of information to know about.

    Say I wanted to test if 3 is an odd number, I'd check the value of 3&1.

    <!--c1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->
    if (3&1) { echo "3 is an odd number"; }
    <!--c2--></td></tr></table><div class='postcolor'><!--ec2-->

    3&1 will return a 1, which is evaluated as true.
  • tankefugltankefugl One Script To Rule Them All... Trondheim, Norway Join Date: 2002-11-14 Member: 8641Members, Retired Developer, NS1 Playtester, Constellation, NS2 Playtester, Squad Five Blue
    <!--QuoteBegin-Jim has Skillz+Jul 30 2004, 07:21 AM--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (Jim has Skillz @ Jul 30 2004, 07:21 AM)</td></tr><tr><td id='QUOTE'><!--QuoteEBegin--> Its used a lot in Assembly aswell. <!--QuoteEnd--> </td></tr></table><div class='postcolor'> <!--QuoteEEnd-->
    Who does not get goosebumps when that language is mentioned? Rrrr! Sexy!

    <!--emo&:p--><img src='http://www.unknownworlds.com/forums/html//emoticons/tounge.gif' border='0' style='vertical-align:middle' alt='tounge.gif' /><!--endemo-->
  • [WHO]Them[WHO]Them You can call me Dave Join Date: 2002-12-11 Member: 10593Members, Constellation
    <i><b>a<span style='font-size:9pt;line-height:100%'>s</span>s</b></i>embly...sexeh
  • TheWizardTheWizard Join Date: 2002-12-11 Member: 10553Members, Constellation
    edited July 2004
    Bitwise calculations worthless??
    Heresy.

    Then again, I am a hardware guy and my favorite programming tasks have been in assembly.

    Besides, pretty much every calculation in hardware is some sort of add/shift operation.

    Binary Multiplication is teh sexay

    110010
    x 101
    ---------
    101 ADD + SHIFT
    101 ADD + SHIFT
    000 SHIFT
    000 SHIFT
    101 ADD + SHIFT
    000 SHIFT
    _________
    =11111010

    or in silly comp sci speak: 50x5=250
  • Jim_has_SkillzJim_has_Skillz Join Date: 2003-01-19 Member: 12475Members, Constellation
    Aside from Assembly taking 5x longer to program than in C++ or Java, its a nice language since you work directly with the memory registers.
  • GeminosityGeminosity :3 Join Date: 2003-09-08 Member: 20667Members
    If you want to program anything with a yaroze (playstation 1) bitshift is a lifesaver as the PSX suffers horrendously from multiplication or division; I literally speeded up my uni project about 5 or 6 times changing all the stuff to bit-shifting =3
    Who'd think an RPG Smash TV with secret of mana-style inspired 'ring' inventory system would tax a poor PSX so much ^^;
  • BlobbyBlobby Join Date: 2004-06-11 Member: 29234Members
    Bit shifting is useful.

    That's all I have to say. <!--emo&:)--><img src='http://www.unknownworlds.com/forums/html//emoticons/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif' /><!--endemo-->
  • SoulSkorpionSoulSkorpion Join Date: 2002-04-12 Member: 423Members
    It's usually fairly low-level, though.

    I wouldn't lose sleep over it.
  • pielemuispielemuis Join Date: 2002-01-25 Member: 72Members, NS1 Playtester
    Make it work first, then worry about optimising.
  • BlobbyBlobby Join Date: 2004-06-11 Member: 29234Members
    Oh, and other bitwise operations are useful too. A simple example is the "XOR swap"

    int x = 4;
    int y = 7;
    x ^= y;
    y ^= x;
    x ^= y;
    // Now x == 7 and y == 4 (TRY IT! I SWEAR IT WORKS!)

    And how about calculating the pitch (the number bytes between each row in a bitmap)?
    int pitch = ( ( bitmap_width * 3 ) + 3 ) & ~3 );
  • TheWizardTheWizard Join Date: 2002-12-11 Member: 10553Members, Constellation
    edited August 2004
    The nice thing about shifting bits in hardware, is that a fixed position shifter can be one of the fastest components around.

    Course, I never get to deal with fast. My stuff normally looks like this: <img src='http://www.personal.psu.edu/users/j/a/jam544/c477/final/Original%20CAM/comp_layout.GIF' border='0' alt='user posted image' />

    Though, I did get it working on a 1ns clock pulse (not bad for a first try at designing memory)

    10 points to the first person who can figure out where the shifters are.
    EDIT: ugh, NM there are no shifters in it. Don't post at 4 am and try to be coherent.
Sign In or Register to comment.