Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations TouchToneTommy on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Binary for Beginners

Programming

Binary for Beginners

by  Zyrenthian  Posted    (Edited  )
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[sub]1[/sub]*sv[sub]1[/sub]) + (bv[sub]2[/sub]*sv[sub]2[/sub]) + (bv[sub]3[/sub]*sv[sub]3[/sub])à + (bv[sub]n-1[/sub]* sv[sub]n-1[/sub]) + (bv[sub]n[/sub] * sv[sub]n[/sub])

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:
Code:
Left Shift: 	<<
Right Shift: 	>>
Bitwise And: 	&
Bitwise OR:	|
Bitwise Not:	~
Bitwise Xor:	^


Truth Tables:

Code:
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

Code:
00100110
00010111

Now it is a bit easier to see... With the bit comparisons we get

Code:
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:

Code:
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)

Code:
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






Register to rate this FAQ  : BAD 1 2 3 4 5 6 7 8 9 10 GOOD
Please Note: 1 is Bad, 10 is Good :-)

Part and Inventory Search

Back
Top