INTELLIGENT WORK FORUMS FOR COMPUTER PROFESSIONALS
Log In
Come Join Us!
Are you a Computer / IT professional? Join TekTips Forums!
 Talk With Other Members
 Be Notified Of Responses
To Your Posts
 Keyword Search
 OneClick Access To Your
Favorite Forums
 Automated Signatures
On Your Posts
 Best Of All, It's Free!
*TekTips's functionality depends on members receiving email. By joining you are opting in to receive email.
Posting Guidelines
Promoting, selling, recruiting, coursework and thesis posting is forbidden. Students Click Here

Programming
Binary for Beginners by Zyrenthian
Posted: 5 Mar 02

I have noticed a lot of questions lately regarding binary operations. The first step to understanding binary, in my opinion, is how to think in binary. The ability to look at a number in binary representation and know what its' value is. Take 100110 for instance. A quick look at it and you may say it is one hundred thousand, one hundred and ten. Retraining the way you look at it is the first step. One method of reading binary is to remember the following sequence (1,2,4,8,16,32,64,128...) which is a very easy sequence to remember. All it consists of is multiplying the current number by 2 to get the next number. With the bits, however, we have to retrain our eyes to read from right to left rather then the left to right we are used to. The above sequence will also be reversed and here is how to apply it.
Notice the bold character in the binary string. The rest of the sentence will describe that single bit 100110 represents the number 1 100110 represents the number 2 100110 represents the number 4 100110 represents the number 8 100110 represents the number 16 100110 represents the number 32
Now we can take the bit value and multiply it with its corresponding number in the sequence. For this we will use the formula ((Binary Value A) * (Sequence Value A)) + ((Binary Value B) * (Sequence Value B)).
Expanding on this we could represent any number of bits as (bv_{1}*sv_{1}) + (bv_{2}*sv_{2}) + (bv_{3}*sv_{3})à + (bv_{n1}* sv_{n1}) + (bv_{n} * sv_{n})
Applying this to the above we get
(0*1) + (1*2) + (1*4) + (0*8) + (0*16) + (1*32) OR (1*2) + (1*4) + (1*32) simplified.
2+4+32 = 38 = 100110 in binary.
Now, onto the C/C++ aspect of this FAQ.
Binary Operations: Left Shift: << Right Shift: >> Bitwise And: & Bitwise OR:  Bitwise Not: ~ Bitwise Xor: ^
Truth Tables:
NOT
X  Q  0  1 1  0
AND NAND
X Y  Q X Y  Q   0 0  0 0 0  1 0 1  0 0 1  1 1 0  0 1 0  1 1 1  1 1 1  0
OR NOR
X Y  Q X Y  Q   0 0  0 0 0  1 0 1  1 0 1  0 1 0  1 1 0  0 1 1  1 1 1  0
XOR XNOR
X Y  Q X Y  Q   0 0  0 0 0  1 0 1  1 0 1  0 1 0  1 1 0  0 1 1  0 1 1  1
For the rest of this FAQ, the generic binary value variable will be known as bv and will be equal to 38 or 100110 in binary as shown above. A second binary value will be used in some examples and will be obv for other binary value. obv will be equal to 23 or 10111 in binary. For simplicity purposes, we will only be using 8 bits representation but the methods shown here can be applied to shorts (16 bits), ints (32 bits on most systems), longs (32 bits) and 64 bit values as well if your machine supports them. However, you must realize that these binary operations are only supported by integer types (i.e. (signed / unsigned) char, short, int, long and other types supported by your current compilier).
Definition of NOT (~): NOT is the easiest of the binary operations to visualize. All that happens when you NOT a value is all ones in the binary representation of the number become zeros and all zeros become ones.
Example of NOT (~)
~bv = ~(00100110) = 11011001 = (1*1) + (1*8) + (1*16) + (1*64) + (1*128) = 217
Definition of AND (&): AND compares the respective bits of the values and if and only if (iff) both bits are a one, a one is set in the specific bit being compared in the value being computed.
Example of AND (&)
bv & obv = 100110 & 10111
Not very easy to see when side by side... Lets look at it in full 8 bit representation with one value above the other
00100110 00010111
Now it is a bit easier to see... With the bit comparisons we get
00100110 00010111  00000110 = (1*2) + (1*4) = 6
Definition of NAND (NOT AND): Once the definition of AND is understood, this is very easy to understand. All this means is you compute the AND value and once you have that value you apply the NOT operation to it.
Example of NAND: ~(bv & obv) = ~(100110 & 10111) = ~(00000110) = 11111001 = 249
Definition of OR (): This compares each bit of the two values and if either bit is a one, a one is set in the corresponding bit of the value being computed.
Example of OR ()
bv  obv = (00100110  00010111) and once again this will be displayed as:
00100110 00010111  00110111 = 1+2+4+16+32 = 52
Definition of NOR This is like NAND in a way except the AND is replaced with an OR
Example of NOR
~(bv  obv) = ~(100110  10111) = ~(00110111) = (11001000) = 8+64+128 = 200
Definition of XOR(^) This is know as the exclusive OR. What it means is iff one of the two bits being compared is a one then set the corresponding bit in the result to a 1, otherwise set it to zero.
Example of XOR(^) bv ^ obv = (100110 ^ 10111)
00100110 00010111  00110001 = 1+16+32 = 49
Definition of XNOR This follows the examples above, simply NOT the result of the XOR
Example of XNOR
~(bv ^ obv) = ~(00110001) = 11001110 = 2+4+8+64+128 = 206
The Shift (<< >>) Operations Now onto shifting. Above we see << and >> as left shift and right shift respectively. What the shift does is shift the bits to the left or right the desired amount of bits. That definition is not too clear but the example should clarify things.
bv << 1 will shift the bits left by 1 so:
bv << 1 = (100110) << 1 = 1001100 = 76 bv << 2 = 10011000 = 152
NOW THINGS BECOME INTERESTING... remember we are working with ONLY 8 bits.
bv << 3 = 00110000 = 48
Think of a cliff. There is a line 8 feet away from the edge of the cliff. Think of the 1's in bv as lemmings standing on the cliff. Think of the LEFT shift operation as a move command to the lemmings to move left x number of feet where x is the value on the right of the shift opperation.
00100110 represents a Lemming that is 3 feet away from the edge, 6 feet away from the edge and 7 feet away from the edge. When we command them to move 3 feet to the left, one of them jumps off the edge, never to be seen again. The other two have moved 3 feet to the left leaving them at their final position of 3 feet away and 4 feet away from the edge.
The right shift operation behaves exactly like the above except the cliff edge is on the right instead of the left.
bv >> 1 = 100110 >> 1 = 10011 = 19 bv >> 2 = 1001 = 9
I don't know if the pattern was clear but for every left shift of a value when NO LEMMINGS jump, we are actually multiplying by 2 and for every right shift we are dividing by two (Even when lemmings jump off the cliff)
Well, I hope this clarified how binary operations work. Thanks for reading it.
Matt

Back to C FAQ Index
Back to C Forum 


