C++ Bitwise ... Stuff
archer1662
Join Date: 2004-03-30 Member: 27610Members
Join Date: 2004-03-30 Member: 27610Members
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 ?
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
*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.
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
Like everyone else has said, its used in extremely specialized cases. Don't bother. Just know that it exists.
<!--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.
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."
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-->
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-->.
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.
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-->
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
Who'd think an RPG Smash TV with secret of mana-style inspired 'ring' inventory system would tax a poor PSX so much ^^;
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-->
I wouldn't lose sleep over it.
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 );
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.