 MillerAdministratorDin: Bucharest
Postari: 134
|
|
Finally finished perfecting and debugging some of the code in this tutorial. Just thought you guys might like to see it. Feel free to post any critisms. (sorry those who noticed I had to post this twice before realising why one of my descriptions wasn't displaying properly).
Bitwise Operators
I'm just writing this tutorial for anyone who needs some more help understanding those bitwise operators, for it took me the longest time to finally figure out what one can use them for, etc. So, this is probably a complete waste of time because most of you probably understood everything about them from the start, but just in case, I'll explain them to you on this page as simply and plainly as I can.
Binary and Hexadecimal
Before we start on the uses and such of the actual operators, we need to learn a little more about binary and its representation. What binary is, as you might already know, is just another way to express a number, albeit with a different base. The base of binary is 2, and everything in binary is subsequently based on powers of 2, unlike decimal, which is based on powers of 10.
Now I just went on and on about how there's nothing super special about binary, but in the fact that a binary digit (or bit) can be in only one of two states, that makes it an excellent language for computers and machinery, for a '1' can be represented with an on position and an off position can represent a '0', thus eliminating the need for more than two conditions. Everything in your computer and mine is represented as binary, including both characters and numbers.
Binary digits, within computers, are usually grouped within bytes (spelled with a 'y' to avoid confusion with bits), which each contain 8 bits. The typical ASCII character is one byte, thus represented with 8 bits (7 actually, for the left-most bit is never used). A long integer is represented with 4 bytes, thus 32 bits and the long long int is represented with 8 bytes, or 64 bits. A short is 2 bytes.
Just as with decimal numbers, there is usually a clear format for representing binary numbers. In decimal, writing 3,452,000 is much easier to read than just 3452000, so in binary, it is customary to put a space or hyphen between each chunk of four bits, called a nibble. Ie. 10011100 can be easier on the eyes when written 1001 1100. Chunks of four bits is also a good number because of its relation with hexadecimal, bringing us into the next subtopic.
Within C, you cannot represent numbers with their binary equivalents, so if you wanted to check to see if the 3rd bit of a set of four is set (1 not 0), you cannot just put 1000, but you must represent it with either its decimal or hexadecimal equivalent. Now, while conversion between decimal and binary is possible, it is very cumbersome and is rarely used when dealing with bits inside numbers (ie. using the binary digits 1010, you must add 2 to the power of 1 and 2 to the 3 power, which, as simplistic as it is now, can be very slow when reaching the larger powers). Instead, we use hexadecimal numbers, which are extremely easy to convert.
Hexadecimal, like binary, is another way of expressing number, except everything is based on base 16. To cover for those extra 5 digits beyond the decimal standard, we use the alphabetical letters A-F. What makes hexadecimal so special is its relation to binary, as I've previously mentioned. If you haven't noticed yet, there are 16 total possibilities within a chunk of 4 bits, and since there are a total of 16 hexadecimal digits (including zero), converting between the two is a snap, as one hexadecimal digit can represent 4 bits. The table is shown below:
BinaryHexadecimalDecimal
000000
000111
001022
001133
010044
010155
011066
011177
100088
100199
1010A10
1011B11
1100C12
1101D13
1110E14
1111F15
So if you wanted to represent the binary number 0100 1110 in hexadecimal, it is simply 0x4E.
AND - &
The AND bitwise operator (& compares two numbers or, in the case of logic gates, bits, and does so in the following way: if both digits of the same placement are 1, the resulting bit is 1, else the resulting bit is 0. It might be clearer to express it in the form of a table:
Resulting bit values
| 0 1 <-first input bit value
--------
0 | 0 0
1 | 0 1
^
second input bit value
Thus, as an example, if you had the number 0xf0 and you compared it in such a way with the number 0xaa, the output would be as shown:
1111 0000 = 0xf0
1010 1010 = 0xaa
________________
1010 0000 = 0xa0
You'll notice that the whole second half of the bit was eliminated in the answer, because no matter what the bit value, the comparing bit was 0, resulting in a zeroed bit. This was an example of using a mask to extract values; with the AND operator you can obtain a certain segment of a number, in this case the high-order nibble. To complete such an extraction, though, you'd have to also use the shift operators, which will be covered later.
Expanding upon such a concept, another possible usage of the AND operator is that of flags. While it is perfectly possible use a char or int by itself to represent a boolean value, it is a much more efficient use of space to utilize the bits themselves (also eliminating the need for multiple different variables floating around the program's scope). The method of setting bits has not yet been touched upon, but one can easily use the AND operator to check if a bit is set by using a mask. This snippet of code might illustrate my point more effectively.
char error_codes = 0x35; // = 0011 0101, the 0, 2, 4 and 5 error codes are set
//compare with only 0000 0001 to see if the 0 error code is set
if((error_codes & 0x01) != 0) printf("Error Code 0 is setn";
//now compare with 0010 0100 to see if 5 and 2 error codes are set
if((error_codes & 0x24) != 0) printf("Error Codes 2 and 5 are setn";
//now check to see if error code 7 is set (1000 0000)
if((error_codes & 0x80) != 0) printf("Error Code 7 is setn";
Yet another possible usage of is in adding of bits. You'll notice that when adding binary digits, the carry bit is the same as the AND operator. In other words, when both digits are one, the resulting digit for that place is zero and one is added to the next digit forward.
Carry bit AND
| 0 1 | 0 1
--------- --------
0 | 0 0 0 | 0 0
1 | 0 1 1 | 0 1
But we'll cover that in more detail when we get to the XOR operator.
Note: The bitwise AND operator (& and the logical AND operator (&&, although both compare two values in similar ways, should not be confused, as the logical AND works on the operands as a whole while the bitwise AND looks at each bit individually.
OR - |
The OR operator (|) also compares two numbers, but in a different style. The resulting bit, when two bits are compared with OR, is always 1 unless both compared bits are 0. In a table, the results would look like so:
Resulting bit values
| 0 1 <-first input bit value
-------
0 | 0 1
1 | 1 1
^
second input bit value
In example, if we were comparing 0x64 and 0x5D, the result would look like so:
0110 0100 = 0x64
0101 1101 = 0x5D
________________
0111 1101 = 0x7D
One of the uses of the OR operator is to set bits, or flags sometimes, in a number or character. Take, for instance, the code in the AND operator explanation which checked to see if bits are set. What if you wanted to set one of those bit after an error? You can use the OR operator like so:
char error_codes = 0x00; //no error codes are set
//let's say that if the strings aren't equal, the error code is 3
if(strcmp(in1, in2)) error_codes |= 0x08;
//now if the string length of the first string is bigger than 10, the error code is 1
if(strlen(in1) > 10)) error_codes |= 0x01;
//if the second string contains no spaces, the error code is 7
if(strchr(in2, ' ') == NULL) error_codes |= 0x80;
Note: As with the AND operator, the bitwise OR (|) and logical OR (||) operators should not be confused.
XOR - ^
The XOR operator (^), standing for Exclusive OR, acts much like the OR, with the exception that if both bits are 1, the consequent bit is 0. As can be shown within a table:
Resulting bit values
| 0 1 <-first input bit value
--------
0 | 0 1
1 | 1 0
^
second input bit value
Interestingly enough, the function the XOR operator achieves can alternately be achieved (and is achieved in the case of logic gates) like so:
(operand1 | operand2) & ~(operand1 & operand2)
The little ~ sign stands for the NOT operation, which basically reverses the bit values. More on that later.
As I've mentioned in the AND operator explanation, you can use AND in conjunction with XOR to add bit values. I'll provide some code to do that later, as it uses the shift operator, but basically, you can XOR the two bits then the carrying bit from earlier (if one exists) to get the current bit value, then AND them to get the carrying bit. In example:
01
01
__
??
01 ^ 01 = 00 <--consequent bit value
01 & 01 = 01 <--carrying bit, we need to shift it though
01 << 1 = 10 <--shift carrying bit to the left
10 ^ 00 = 10 <--answer
The answer in the above example was essentially the beginnings of the process a second time, and, indeed, one would need to continue the process for some numbers (until nothing's left in the carrry), but the basic concept's there.
NOT - ~
NOT, unlike AND, XOR and OR, only has one operand and is used as such: ~operand. Its function is basically, as mentioned before, to reverse the bit value. Now you've already seen one usage of the NOT operator, but that's a little useless because we have XOR. Another possible function is calculating the two's complement of a number.
What is the two's complement, you ask? Since you can't represent -1 in binary as -0000 0001, there's a way around it. Basically, if the left-most digit is set (in a signed number, that is), it's negative. You can have the same system for decimal, where if the left-most digit is 5, 6, 7, 8 or 9 the number is negative; then it would be called the ten's complement, though.
What you do is split the possible number range (for a char, that would be 255), into two. The bottom half (ie. 0000 0001 - 0111 1111) is positive, and anything above that would start at the bottom of the negatives (1000 0000 - 1111 1111). The counting in a signed number would be like so:
BinaryDecimal
1000 0000-128
1000 0001-127
1000 0010-126
...
1111 1110-2
1111 1111-1
0000 00000
0000 00011
0000 00102
...
0111 1110126
0111 1111127
Going higher than 127 would just start over again at -128. The way it works out may seem a bit strange to you (why 1111 1111 as -1 and 1000 0000 as -128?), but it's actually quite logical once you stop to think about it. Imagine starting at 127 (0111 1111) and counting all the way down to zero. You're now at 0000 0000, what do you do when you go one lower? Start all over again at 1111 1111.
Now, back where we were before we started going off track. You can calculate a number's negative equivalent by calculating the one's complement (essentially what you'd get if you subtract the number from 1111 1111; alternately, in base 10, you can get a numbers nine's complement by subtracting the number from pow(10, digits in number) - 1, eg. 9999 - 1223) then adding 1. Since the one's complement in binary is the exact same as simply reversing all the bits, we can just use the NOT operator to reverse the bits then add one.
Don't believe me? Let's take an example. How about 126 (0111 1110):
~0111 1110 = 1000 0001 + 1 = 1000 0010 = -126
Yet another function the NOT operator can perform in conjuction with the AND is that of removing bits, or 'error codes'. If you have the number 1001 0010, say, and you wanted to remove the first bit (second from right), you could reverse the bits in the bit you wanted to remove (ie. 0000 0010 -> 1111 1101) and then compare it with the number with the AND operator. This would effective remove the bit because, as discussed earlier, the resulting bit can only be '1' if both input bits are '1', this would mean that no matter what state the bit's in you wanted to remove, you'd be comparing it with zero, thus the resulting bit would be zero. It would also not have any effect on the surrounding bits because of the way AND compares the bits, thus whatever the bit is, it will stay that way if it is compared with '1'. This code snippet might clarify things a bit more:
#define NUMBER_ERROR_CODE 0x08 //0000 1000
char error_codes = 0x48; //0100 1000
int i;
//let's say that if the user enters a number, we can remove the error code
if(isnum(getchar())) error_codes &= ~NUMBER_ERROR_CODE;
//Now let's print those error codes
if(error_codes & NUMBER_ERROR_CODE) puts("Number error code is set";
Shift - <</>>
The shift operator does as it says, it shift bits within a number as many times as you specify. It can shift left (<< or right (>>, and they are equivalent to multiplying and dividing that number by 2 to the power of the shift, respectively. That means the a shift of 4 digits to the left is the same as multiplying the operand by 2 to the 4th power, or 16. The same can be said of the right shift operator except it will divide the number by 2 to the power of 4. Example:
4 << 4 = 4 * (2 * 2 * 2 * 2) = 4 * 16 = 64
64 >> 5 = 64 / (2 * 2 * 2 * 2 * 2) = 64 / 32 = 2
Since shifts are faster than multiplying or dividing, and as such would be a quicker alternative to multiplying or dividing by powers of 2, but since most modern day compilers recognize instances where this would be applicable, doing so would only obfuscate your code.
I know before I even started on the actual operators I mentioned one can use hexadecimal as an easier way to represent bits, but another way one can use to represent single bit values is via the shift operator. By simply shifting 1 to the left however many times its place should be, one can end up with that bit set in a number. So if you wanted to represent the 3th binary digit in a number (0000 1000), you would put 1 << 3. This is especially useful if you are looping through the bits, because you can use 1 << [incrementing int] to represent the current bit.
The shift operator can also be used to finish off a masking with the AND operator. Using the example provided in the AND explanation:
1111 0000 = 0xf0
1010 1010 = 0xaa
________________
1010 0000 = 0xa0
But we still haven't completed the masking process, for the value is still in the same location; to truly isolate the value we must shift is to the right 4 bits:
0xa0 >> 4 =
0000 1010 = 0x0a
Notice the 0s that pad the area to the left. One thing to note is that this can be different (only on the right shift) depending on if the number is signed or unsigned and if the operand is negative or not. If the number is signed and positive, the bits are filled with 0s; if the number is signed and negative, the bits may be filled with either 0s or 1s depending on the compiler, but most compilers choose the arithmetic right shift (fills with 1s) over the logical one (fills with 0s); and lastly, if the number is unsigned, the bits are filled with 0s. A chart may display this more efficiently:
| Signed Positive Char | Signed Negative Char | Unsigned Char
-----------------------------------------------------------------------------
Fill | 0 | 1 or 0, usually 1 | 0
Miscellaneous
Within the XOR operation explanation, I talked a little about the shift operation in relation to adding binary numbers. An example of this would be a small snippet of coding that adds two integers via their bit values.
unsigned long add(unsigned long in1, unsigned long in2)
{
unsigned long bit, carry, tmp;
carry = in1 & in2; //Get the carry bits
bit = in1 ^ in2; //Get the answer bits
while(carry) //Loop until we have rid ourselves of the carry bits
{
carry <<= 1; //shift carry bits one so they really will 'carry'
tmp = bit ^ carry; //Exclusive OR the carry and answer to get the next answer
carry &= bit; //Get rid of any carry bits that were used and gain any new ones
bit = tmp;
}
return bit;
}
This can be simplified into a definition, which would be faster:
//in1, in2 = ints to add
//carry, tmp = temporary ints
//bit = out int
//All int sizes should be the same
#define bit_add(in1, in2, carry, tmp, bit)
do {
carry = in1 & in2;
bit = in1 ^ in2;
while(carry)
{
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
} while(0)
And the same concepts apply.
To demonstrate this, let's try adding the numbers 103 and 29 using this method.
103 = 0110 0111
29 = 0001 1101
XOR 0111 1010 taking first XOR and the shift result...
AND 0000 0101 > XOR 0111 0000 ...and again...
<<1 0000 1010 / AND 0000 1010 > XOR 0110 0100 ...
<<1 0001 0100 / AND 0001 0000 > XOR 0100 0100 ...
<<1 0010 0000 / AND 0010 0000 > XOR 0000 0100 ...
<<1 0100 0000 / AND 0100 0000 > XOR 1000 0100
<<1 1000 0000 / AND 0000 0000
AND = 0, break
The final result is 1000 0100, as you can see at the last Exclusive OR. Does this compare?
1000 0100 = 132
29 + 103 = 132
Yep. You can try it for any number and it should work out. Of course, there's a limit to the amount of bits an integer on the computer can store, but that's what a carry flag could come in handy for. If that most significant bit is set in the carry integer (and since the carry's not empty, it will get shoved off the edge in the shift), you can set a flag, which could come in handy if you were, say, adding two arrays as two integers. An adding function that also looks at the carry flag might look like this (theoretically):
#define LARGEST_ULONG_BIT (1 << 31)
char add_carry_bit = 9;
unsigned long add(unsigned long in1, unsigned long in2)
{
unsigned long bit, carry, tmp;
carry = in1 & in2;
bit = in1 ^ in2;
add_carry_bit = FALSE;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) add_carry_bit = 1;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
return bit;
}
unsigned long addwithcarry(unsigned long in1, unsigned long in2)
{
unsigned long bit, carry, tmp;
if(add_carry_bit)
{
add_carry_bit = FALSE;
carry = add((in1 & in2), 1);
}
else carry = in1 & in2;
bit = in1 ^ in2;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) add_carry_bit = 1;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
return bit;
}
As you can see, the second addwithcarry() is basically the same as the add(), except it looks to see if the flag is set and, if so, adds one more to the carry. You'll also notice how we set the flag, we test to see if the carry flag contains a '1' in the left-most bit which, since it contains more than one it will be shifted, will be shoved off into infinity, to be lost otherwise.
Some of you (rather, who've read this before I redid the addition) might be wondering why I don't (still) have two flags. Well, this is because the only way for a bit to be pushed into oblivion when one is added is if the original number is all ones, ie. 1111 1111. If one is added, all of those ones turn into zeros and a bit (should) be in the left-most place plus one, ie. (1) 0000 0000. No matter what else we add to that, it will still be within the limits, ie. (1) 0000 0000 + 1111 1111 = (1) 1111 1111, so we don't need anymore than one flag.
Now onto subtraction. Because the concept of borrowing is rather messy in its back-and-forthness, if you will, it would be rather hard to implement such a way of subtracting two numbers with only bitwise operators in our toolbox. Nor would it be as efficient as another way. Thankfully, another way does exist to subtract without borrowing. To demonstrate this, let's walk through a subtraction of two numbers, say 345 and 78, decimal style.
345 - Minuend
- 78 - Subtrahend
___
??? - Difference
First, we need to calculate the ten's complement of the subtrahend, or the number that we're subtracting. Normally, we could just subtract that number from its nine's complement plus one, but since that would require borrowing (1000-78, we need to borrow to complete this), we must instead subtract it from its nine's complement then add one (like in the explanation of the NOT operator), requiring no borrowing in the process.
999
-78
+ 1
__
922
The next step in this process of subtraction is to then add the Minuhend, or the number from which we're subtracting.
922
+345
____
1267
Then, to get rid of that extra digit on the end, we must subtract 1000, or however many digits there are in the number, to get the final result:
1267
-1000
____
267
And our answer is left. Pretty cool. The basic formula was this:
operand1 + nine's complement of operand2 + 1 - pow(10, digits in result)
Now, because we're trying to implement this using only bitwise operators, we can use a few shortcuts and thus eliminate a lot of extra work. One of these is the fact that calculating the equivelent of the nine's complement, the one's complement, can be done with just using the NOT operator, as explained above, instead of actually subtracting it. Adding one to that will reveal the two's complement of the number. Another little advantage we have is the fact that we don't need to worry about subtracting that last little bit because the very bit we wanted to eliminate was pushed over the edge in addition process. So, we can basically widdle our formula down to this:
operand1 + (~operand2 + 1)
Which could be implemented into code like so:
//Note that we're using signed values so it can represent negatives
signed long sub(signed long in1, signed long in2)
{
signed long bit, carry, tmp;
//NOT the second operand and add it to one (in other words, find the two's complement)
carry = ~in2 & 1;
bit = ~in2 ^ 1;
while(carry)
{
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
//Now add that result to the first operand
tmp = bit;
carry = in1 & tmp;
bit = in1 ^ tmp;
while(carry)
{
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
return bit; //and we have our answer
}
So, we've successfully created a subtraction function that doesn't use any subtraction. Some may stop here, but I'm continuing to try and make it possible to, like in the addition one, add two arrays of numbers like one. This complicates things slightly, for, just like in addition, we'll be carrying, so we need to establish an extra flag to tell the subwithborrow() function will know when to add another 1 to the next chunk or not. You'll notice another difference is the fact that we're not adding one extra to the NOTed operand, because we already did that in the first chunk.
#define LARGEST_ULONG_BIT (1 << 31)
char sub_borrow_bit = 0;
signed long sub(signed long in1, signed long in2)
{
signed long bit, carry, tmp;
carry = ~in2 & 1;
bit = ~in2 ^ 1;
sub_borrow_bit = FALSE;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) sub_borrow_bit = TRUE;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
tmp = bit;
carry = in1 & tmp;
bit = in1 ^ tmp;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) sub_borrow_bit = TRUE;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
return bit;
}
signed long subwithborrow(signed long in1, signed long in2)
{
signed long bit, carry, tmp;
if(sub_borrow_bit)
{
carry = ~in2 & 1;
bit = ~in2 ^ 1;
sub_borrow_bit = FALSE;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) sub_borrow_bit = TRUE;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
tmp = bit;
}
else tmp = ~in2;
//Note that we're not adding one to this by default because this is assuming that it is
//subtracting the high-word of the number, not a different low-word
carry = in1 & tmp;
bit = in1 ^ tmp;
while(carry)
{
if(carry & LARGEST_ULONG_BIT) sub_borrow_bit = TRUE;
carry <<= 1;
tmp = bit ^ carry;
carry &= bit;
bit = tmp;
}
return bit;
}
That was very theoretical, so it might work and it might not, but the basic concept's there.
Well, that's it. I hope this tutorial was somewhat educational and was at least slightly enjoyable.
_______________________________________
#WashingtonDC Channel Manager
|
|
