Cheat Engine Forum Index Cheat Engine
The Official Site of Cheat Engine
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 


Bitwise operations in C

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming
View previous topic :: View next topic  
Author Message
benlue
Moderator
Reputation: 0

Joined: 09 Oct 2006
Posts: 2142

PostPosted: Sat Mar 17, 2007 7:47 pm    Post subject: Bitwise operations in C Reply with quote

I have quoted this from my website as i'm changing hosts .

Well enjoy this

This is a simple tutorial on bitwise operations in C . NOTE !: p stands for power of . like 2p2=4

Number Representation

A number is a very abstract concept. Unlike physical objects, which are easily recognizable on sight, a number can be represented in an infinite number of ways. The representation we are used to is called decimal, or base 10. The first time is pretty familiar, but if you're reading this section, the second term may be new to you. To see why we use the term "base 10," let's take a look at an arbitrary number, say 5346. Read aloud, this is five thousand, three hundred, forty-six. We hear numbers like that so often that it's not immediately obvious, but this sounds a lot like a formula. Specifically:

Code:
5346 = (5 * 1000) + (3 * 100) + (4 * 10) + (6 * 1)


Or, if we write it another way, we see that a decimal number is actually the sum of its digits multiplied by successive powers of 10:

Code:
5346 = (5 * 10p3) + (3 * 10p2) + (4 * 10p1) + (6 * 10p0)


Do you see why the term "base 10" is used to describe the way we normally write numbers? Any integer can be written this way. Suppose we call the least significant digit (the digit in the ones place) "digit 0," and each successively higher digit is digit 1, digit 2, and so on. Then the full number is represented by digit 0 times 100, plus digit 1 times 101, and so on, up through digit n times 10n. The shorthand for the general case of an n-digit number is:

Binary

The binary, or base 2, number system is the one that computers use to represent numbers in memory. Since we're dealing with base 2, there are only two digits available, namely 0 and 1. Each digit is multiplied by successive powers of two to obtain the number's overall value. For example, consider the binary number 100101. The value of this number is:

[code]100101 = (1 * 25) + (0 * 24) + (0 * 23) + (1 * 22) + (0 * 21) + (1 * 20) = 32 + 4 + 1 = 37[code]

So, why do computers use binary instead of just using decimal like we do? In computer hardware, a binary digit is represented by the presence of electric current. If the level of electricity is above a certain level, the digit is regarded as a 1. Otherwise, the digit is a 0. Obviously, building hardware that can differentiate between ten levels of current would be considerably more difficult and more expensive than this simple two-digit model. Hence, computers store everything in binary.

A single binary digit is usually called a bit, and eight bits make a byte, which is the fundamental unit of storage in memory devices. Because a byte has eight bits, and each bit can take one of two values (0 or 1), the number of distinct values a byte can hold is 28 = 256. Two bytes together are called a word, which is a 16-bit value. A word can have 216 = 65,536 distinct values. Finally, two words together are called a double word or dword, which is a 32-bit value. Most processors in common use today are 32-bit, meaning they are built to normally operate on 32-bit numbers. This is why the int data type currently defaults to 32 bits in Win32 compilers, whereas an int is 16 bits in a realmode DOS compiler.

Sometime in the not-too-distant future, we'll be writing 64-bit code instead, where the default size for an integer will be a quad word or qword. But for now, the dword is the standard. To see how a dword is broken up, take a look at the following diagram.

Hexadecimal

The hexadecimal number system uses base 16, which means that there are sixteen distinct digits. Obviously we're only used to having ten, 0 through 9. In hexadecimal, the character A has a value of 10, B has a value of 11, and so on through F, which has a value of 15. Let's see an example of determining the value of a hexadecimal number:

[code]3FC = (3 * 16p2) + (F * 16p1) + (C * 16p0) = (3 * 16p2) + (15 * 16p1) + (12 * 16p0) = 768 + 240 + 12 = 1020[/code]

The reason hexadecimal is so frequently used in programming is that it's very easy to translate between hexadecimal and binary, whereas converting from decimal to binary and back is kind of a pain. The reason it's so easy to convert between base 16 and base 2 is that 16 is a power of two. Specifically, 16 = 24. Why is this significant? Well, a group of four binary digits can take exactly 24 values, which means that each hexadecimal digit corresponds to exactly four binary digits. Since ten is not a power of two, the conversion is not so easy in decimal. Thus, when programmers want to use a specific binary number, they write it in hexadecimal. In C, you can recognize a hexadecimal number because it is always prefixed by "0x." For example, this C statement assigns the value 1020 to a variable, by using its hexadecimal equivalent:

[code]nValue = 0x3FC;[/code]

There is no such prefix that will allow you to write a binary number directly, which is why hexadecimal is used is used. The following table shows the binary equivalents for each of the sixteen hex digits. You should try to internalize this. At first you'll have to think about what you're doing as you convert binary to hex and back, but after awhile it will become second nature.

[code]3FC = 0011 1111 1100 = 1111111100[/code]

The AND Operator

There are two kinds of AND operators in the C language: the logical AND, and the bitwise AND. The former is represented by the && operator, and the latter uses the & operator. You've probably seen the first one numerous times, as it's often used in if statements. Here's an example of the logical AND in action:

[code]if ((x == 5) && (y == 7))
DoSomething();[/code]

In this case, you would expect that the function will only be called if x is 5 and y is 7. The bitwise AND works very much the same way, except that it works with two bits instead of two expressions. The bitwise AND operation returns 1 if and only if both of its operands are equal to 1. In other words, we have the following truth table for the bitwise AND:

[code]0 AND 0 = 0
0 AND 1 = 0 x AND 0 = 0
1 AND 0 = 0 x AND 1 = x
1 AND 1 = 1[/code]


The first column shows the result of a bitwise AND when combining explicitly defined bits. But it's the second column that's interesting. It says that if you AND any bit with 0, the result is 0; and if you AND any bit with 1, the result is the original bit. This little piece of information will be the key to making the bitwise AND work for us later, so keep it in mind. To finish up, let's see an example of combining two words using the bitwise AND operator:

[code]0110 1011 1000 0101
& 0001 1111 1011 1001
---------------------
0000 1011 1000 0001[/code]

Do you see why we get the result we do? There is a 1 in the result only in the positions where the corresponding bits in both operands are also equal to 1. That's all there is to the bitwise AND operation. Let's move on.

The OR Operator

Just as with the AND operation, there are two different types of OR in the C language. The logical OR uses the || operator, and the bitwise OR uses the | operator. A use of the logical OR might look something like this:

[code]if ((x == 5) || (y == 7))
DoSomething();[/code]

In this example, the function will be called if x is 5, if y is 7, or both. The only way the function is not called is if both of the conditions are false. The bitwise OR is very similar, in that it returns 0 if and only if both of its operands are 0. To illustrate this, we have the following truth table:

[code]0 OR 0 = 0
0 OR 1 = 1 x OR 0 = x
1 OR 0 = 1 x OR 1 = 1
1 OR 1 = 1[/code]

Once again, the second column is the interesting one. Note that whenever you OR a bit with 0, the result is the original bit, and whenever you OR a bit with 1, the result will always be 1. This will be the key to using OR effectively a little later on. For now, let's just look at an example of using the bitwise OR operation on two words:

[code]0110 1011 1000 0101
| 0001 1111 1011 1001
---------------------
0111 1111 1011 1101[/code]

Here you can see that the result contains a 0 only when the corresponding bits in both of the operands are also 0. Now we've got just one more combinational operator to look at, and that's XOR.

The XOR Operator

The XOR is a little strange because there is no logical equivalent for it in C, even though many languages include one. The XOR operation is symbolized by the ^ character in C. The term XOR stands for "exclusive OR," and means "one or the other, but not both." In other words, XOR returns 1 if and only if exactly one of its operands is 1. If both operands are 0, or both are 1, then XOR returns 0. To see this, take a look at the truth table for XOR:

[code]0 XOR 0 = 0
0 XOR 1 = 1 x XOR 0 = x
1 XOR 0 = 1 x XOR 1 = ~x
1 XOR 1 = 0[/code]


The truth table here is interesting. Note from the first column that anything XORed with itself returns 0. This fact will lead to an interesting application of XOR later on. In the second column, we see that any bit XORed with 0 yields the original bit, and any bit XORed with 1 yields the complement of the original bit. This is something you may not have seen before: the bitwise NOT. It is a unary operator, meaning that it only takes one operand, like a negative sign. A bitwise NOT simply inverts all the bits in its operand, meaning that all 0s are changed to 1s, and vice versa. Now, let's take a look at an example of using XOR on two words:

[code]0110 1011 1000 0101
^ 0001 1111 1011 1001
---------------------
0111 0100 0011 1100[/code]

So there you have it, the last of the combinational operators, plus the only unary bitwise operator, the NOT. Before we can look at any applications of these, there is one other class of bitwise operator I need to show you, called shifts. Don't worry, this will go pretty quickly, and then we can get on to the interesting stuff.

Bitwise Shifts

There are two bitwise shift operators, namely shift left and shift right. In C, they are represented by the << and >> operators, respectively. These operations are very simple, and do exactly what they say: shift bits to the left or to the right. The syntax for a shift operation is as follows:

[integer] [operator] [number of places];

A statement of this form shifts the bits in [integer] by the number of places indicated, in the direction specified by the operator. Probably the best way to visualize this is with an example. Take a look at the following code, which demonstrates a shift left.

[code]// Precondition: x == 0000 0110 1001 0011
// Postcondition: y == 0000 1101 0010 0110
x = x << 1;[/code]

From this example, you should be able to see what's going on. Every bit in x is shifted to the left by one place. When you do this, the MSB (most significant bit, remember?) of x is lost, because there isn't another place to shift it to. Similarly, after a shift left, the LSB of x will always be 0. There is no position to the right of the LSB, and so there's nothing to shift into the LSB, so it's assigned a value of 0. Just to make sure you've got the idea of this, let's take a look at a shift right:

[code]// Precondition: x == 0110 1111 1001 0001
// Postcondition: y == 0000 0110 1111 1001
x = x >> 4;[/code]

Here, the bits are being shifted right by four places. Got it? Good. That finishes out the set of bitwise operators, so now we can finally get around to seeing what they're good for.

Extracting and Clearing Values

A perfect example for when you'd want to combine multiple values into a single variable is if you're doing graphics work with 32-bit color. In a 32-bit color dword, there are four distinct values. The low byte (bits 0 through 7) is the value for blue. The next most significant byte is a value for green, then a byte for blue, and finally, the high byte is an alpha (transparency) value. So the color dword looks like this in memory:

[code]AAAA AAAA RRRR RRRR GGGG GGGG BBBB BBBB[/code]
Now, suppose you have a 32-bit integer called dwColor, and you want to extract the value for green. How would you do it? What you need is a way to eliminate the other three bytes, and leave the red byte untouched. Recall the truth table for the bitwise AND. If you remember, ANDing any bit with 0 yields 0, and ANDing any bit with 1 yields the original bit. So what you do here is define a value called a mask, which has 0s where you want to erase information, and 1s where you want to save information. Since you want to extract the red byte, your mask would look like this:

[code]0000 0000 1111 1111 0000 0000 0000 0000[/code]
Of course, you can't write binary numbers directly into C code, so you have to convert it into hexadecimal. But that's easy, remember? In this case, the hex equivalent is 0x00FF0000. If we use the bitwise AND on dwColor and our mask, we get the following result:

[code]dwColor: AAAA AAAA RRRR RRRR GGGG GGGG BBBB BBBB
mask: & 0000 0000 1111 1111 0000 0000 0000 0000
-----------------------------------------
result: 0000 0000 RRRR RRRR 0000 0000 0000 0000[/code]

That's great, but there's just one problem. To use the red byte by itself like we want, it would have to be the low byte. But it's not -- it's 16 bits up in the dword. So, what do you think we learned those shift operators for? All we need now is a shift right by 16 places, and we're all set:

[code]Previous: 0000 0000 RRRR RRRR 0000 0000 0000 0000
Shift: >> 16
---------------------------------------
Result: 0000 0000 0000 0000 0000 0000 RRRR RRRR == RRRR RRRR[/code]

We've done exactly what we wanted to do: we extracted the red byte from the full color dword. This example can be applied to virtually anything that uses bit fields to store a number of values in a single variable. All you have to do is make sure your masks are set correctly, and you shift by the correct number of places. The mask should contain a 1 wherever you want to keep information, and a 0 wherever you want to clear it. As one more example, I'll show you how you would come up with the masks for a 16-bit color word.

[code]Color word: RRRR RGGG GGGB BBBB
Red mask: 1111 1000 0000 0000 == 0xF800
Green mask: 0000 0111 1110 0000 == 0x07E0
Blue mask: 0000 0000 0001 1111 == 0x001F[/code]

Note that instead of clearing all the fields but one so you can use that by itself, you can also use AND to leave all the fields except one as they are, clearing only that one. For example, you could alter a 32-bit color dword by clearing its green byte. But, then what happens if you want to set that value to something else without altering the rest of the color word? You could accomplish that with the bitwise AND operator and a number of shifts, but it wouldn't be the most efficient way. To easily splice new values into a larger variable, we need to employ the bitwise OR.

Inserting and Combining Values

Now our situation is the reverse to what we were just doing. Instead of extracting a byte from a color dword, suppose we want to reset one. Maybe we have a color dword that represents the color (214, 53, 240), and we want to change it to (214, 166, 240). The first step is to clear the green byte to 0, which we learned how to do in the last section. To see how to rewrite that byte, consider the truth table for the bitwise OR. Remember that any value ORed with 0 is that value. So we must create a new mask to use. It will have zeroes wherever the color dword is already defined, and it will have an actual color value wherever the color dword has a 0. If you didn't follow that, this should clear it up:

[code]dwColor: AAAA AAAA RRRR RRRR 0000 0000 BBBB BBBB
mask: | 0000 0000 0000 0000 GGGG GGGG 0000 0000
-----------------------------------------
result: AAAA AAAA RRRR RRRR GGGG GGGG BBBB BBBB[/code]

So in this case, the mask is the green byte, located at the appropriate position so that it merges correctly with the color dword. As before, we can use a bitwise shift to shift the green byte into the position we want it in. In the example above, the green byte is located eight bits above the low byte, so the shift operation you'd use would look like this:

[code]Previous: 0000 0000 0000 0000 0000 0000 GGGG GGGG == GGGG GGGG
Shift: << 8
---------------------------------------
Result: 0000 0000 0000 0000 GGGG GGGG 0000 0000[/code]

And that's it! What we've done so far with the bitwise AND and OR operations is enough for you to fully manipulate any values divided into bit fields, such as color words. The other place this comes in handy is when you're designing a function that can take a number of flags as arguments, and you want to combine all of those flags into a single parameter to the function. The only thing you need to do is make sure you define the various flags so that their binary values don't have any 1s in common. Then you can OR them together to create a unique combination of flags. For example, take a look at the following function call:

[code]Animate(lpdds, 8, ANIM_LOOP | ANIM_MAXSPEED | ANIM_LINK);[/code]
This is an example of a function call you might use to start an animation in a game engine. Note that the last parameter to the function has three constants combined using the bitwise OR operator. The definition of those constants might look like this:

[code]#define ANIM_LOOP 1 // (0000 0001)
#define ANIM_ONCE 2 // (0000 0010)
#define ANIM_MAXSPEED 4 // (0000 0100)
#define ANIM_MINSPEED 8 // (0000 1000)
#define ANIM_CUSTSPEED 16 // (0001 0000)
#define ANIM_LINK 32 // (0010 0000)
#define ANIM_LINKALL 64 // (0100 0000)[/code]

Note that the constants are defined as successive powers of 2, so that each has only one bit set to 1. This is so any combination of these values will yield a unique result. If you defined them as consecutive integers, you would get repeated values. For example, 1 OR 2 is 3, but 1 OR 3, 2 OR 3, and just 3 by itself all come out to 3 as well. So the function receives a value of 3, it won't know what combination you mean. To test to see if one of the flags is present, you just try to extract it with an AND. If the result is nonzero, the flag is set. So the body of the function might look like this:

[code]int Animate(LPDIRECTDRAWSURFACE lpdds, int nFrames, DWORD dwFlags)
{
// test for looping
if ((dwFlags & ANIM_LOOP) > 0)
anim.bLoop = TRUE;

// test for maximum speed
if ((dwFlags & ANIM_MAXSPEED) > 0)
anim.nSpeed = MAX_SPEED;

// ...and so on
}[/code]

As I mentioned before, the Win32 API and DirectX both have a great number of functions that let you combine flags in this way, and this is how they accomplish it. If you look through your Windows headers, you'll find those flags defined as powers of 2 for that very reason. Very useful stuff.

Swapping Variables

If you're ever writing some code that needs to fit in a very tight amount of memory (such as a piece of assembly language), you might come across a situation where you want to swap two variables without having to use a third. The XOR operator provides a very cool way to do this. This works based on two facts. First, the XOR operation is commutative. That is, X ^ Y is the same thing as Y ^ X. Second, as we saw earlier, anything XORed with itself yields 0. With that in mind, suppose we have two constants, called CONST_A and CONST B. Take a look at the following code fragment:

[code] // Value of x Value of y
// -----------------------------------------------
int x, y; // 0 0
x = CONST_A; // CONST_A 0
y = CONST_B; // CONST_A CONST_B
x = x ^ y; // CONST_A ^ CONST_B CONST_B
y = x ^ y; // CONST_A ^ CONST_B CONST_A ^ CONST_B ^ CONST_B == CONST_A ^ 0 == CONST_A
x = x ^ y; // CONST_A ^ CONST_A ^ CONST_B CONST_A
// == 0 ^ CONST_B == CONST_B CONST_A
// CONST_B CONST_A
[/code]
Look this over for a minute so you can see exactly what's going on. The two variables begin as CONST_A and CONST_B, respectively. With two XOR operations, y becomes CONST_A ^ CONST_B ^ CONST_B, but CONST_B ^ CONST_B is of course 0, and CONST_A ^ 0 is simply CONST_A. Another XOR operation does the reverse to x, and in three quick statements, you have swapped the values of two variables, without using a third. Is that cool or what? Also, note that there is a ^= operator similar to the += and -= operators in C, so the code for swapping x and y comes down to this:

[code]x ^= y;
y ^= x;
x ^= y;[/code]

Bitwise operations are extremely fast for the processor to handle, so this is nice and quick, as well as a way to rid yourself of a temporary variable, which can be very nice. All right, we're almost done. The last thing we can do is replace a few arithmetic operations with bitwise ones.

Copied and paste .
Credits ME ! ( since it's my website and tutorials )
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group

CE Wiki   IRC (#CEF)   Twitter
Third party websites