Donate to us via Paypal!
Imagination is more valuable than knowledge - Albert Einstein
Thursday, July 09, 2020
Home
Find:
Information:
Learn
Communicate
Submit
Shop
Challenges
Exploit:
Programming:
Think:
Track:
Patch:
Other:
Need Help?
Other
Members Online
Total Online: 63
Guests Online: 63
Members Online: 0

Registered Members: 127057
Latest Articles

# Binary, Booleans, and Bitwise Operations

## A more advanced look at how the computer is thinking and representing numbers

================Binary, Booleans, and Bitwise Operations===============

Binary:
I guess I should start by explaining binary representation for those of you who don�t understand it yet. As you hopefully know, binary is a number system of base 2. That means it uses only the numbers 0 and 1. Each digit represents a power of 2.

Take a look at the decimal number system that you ought to be familiar with:
1234 is a number in base 10. The 4 on the right represents the 1�s digit (4*10^0) the 3 is in the 10�s place (3*10^1) the 2 is in the 100�s place (2*10^2) and the 1 is in the 1000�s place (1*10^3).

Binary works the same way:
00101101 is a number in binary. The one on the far right is 1*2^0 which is 1 + 0*2^1 which is 0 + 1*2^2 which is 4 �etc. So we end up with 1+4+8+32=45.

Also, you should know that a bit is a binary digit,
8 bits=1byte
1024 bytes=1 kilobyte
1024 kilobytes=1 megabytes
1024 megabytes=1 gigabyte
1024 gigabytes=1 terabyte
1024 terabytes=1 petabyte
There�s more after that, but you probably won�t need to know about those for long time.
Note that 1024=2^10

--------------------------------------------------------------------------------------------------------------------------------------
Now, I�ll give a brief explanation of a few different methods of signed binary integer representation that have been used in the past. Note that signed means that it includes both positive and negative values whereas unsigned is only positive.

-Sign magnitude: where the first bit means negative if 1 and the rest of the bits are the magnitude. The downside with this representation is that there are two ways to make zero 1000 (-0) and 0000 (0).

-One�s compliment: first bit represents negative if 1. To make a number negative, you flip every bit. So 01011 (eleven) negative is 10100. This method also has two ways to make zero.

-Two�s Compliment: This is the method that is used in most modern computers. Example: Seven=0111 and negative seven=1001. To convert to from positive to negative, flip the bits and add 1. In this method, the first bit (on the far left) represents -2^(n-1) where n is the number of bits and all the rest of the bits represent positive numbers. So in the case of -7 (1001), the value is (-8)+0+0+1 which equals -7.

-Excess Bias: you first set a bias to make everything in the positive range.
So you would bias by (2^(n-1))-1, so assuming a 3 bit number, you would have a bias of 3
You then off set all of the numbers by the bias, so
111 =4
110 =3
101 =2
100 =1
011 =-0
010 =-1
001 =-2
000 =-3
This might seem like a pain in the ass to use, but we�re going to come back to this later when we get into floating point representation, so don�t just brush it off.

-----------------------------------------------------------------------------------------------------------------------------------------

Next I�ll explain floating point numbers. A floating point number is a number with a decimal point (well, I guess it wouldn�t be a �decimal point� in binary). So as you know, the digits in binary go by powers to 2 for integers, and they also go by powers of 2 for decimals too.

Say you have this number in binary: 1.111 the first digit on the left is going to be 1 (2^0) and to the right you have .111 well from here we just keep subtracting 1 from the exponent as we move to the right. So we had 2^0, then 2^-1 then 2^-2 �and so on. So the number 1.111 will be 1+.5+.25+.125 which is 1.875.

But we can�t just represent decimals like that since we have a limited number of bits that we can use. Thus the idea of the floating point number was created. In this, you use something similar to scientific notation to move the decimal point around so that you can represent larger numbers.

Floating point representation uses a sign-magnitude representation for the fractional part, and an excess bias representation for the exponent part. The numbers are represented in this format: Sign * fraction * 2^exponent
So say you have this number in binary: 0 1011 010 you are told that the exponent has 4 bits and the fraction has 3 bits.
-The sign is 0, so positive
-The exponent=1011. Since there are 4 bits, the bias=2^(4-1) -1=7, so the exponent, 1011=11-7 = 4
-The fraction=010. In floating point representation, if the number is normalized (I�ll explain that in a bit (no pun intended)) then you always assume it leads with a one, so the fraction is going to be 1.010 which equals 1.25
-so your floating point number equals 1.25*2^4

If the number has an exponent of all zeroes or all ones, the number is considered �denormalized� otherwise it is �normalized�.
-If the exponent is all zeroes, the fraction starts with a leading zero.
-If the exponent is all ones and fraction is zero, you get infinity (positive infinity if the sign is positive, and negative infinity if the sign is negative). If fraction is not zero you get �not a number� (NaN)
==========================================================================

Boolean Logic
There are these things called �gates� that your computer�s integrated circuits uses to make certain things happen. These gates are AND, OR, NOT, XOR, NAND, and NOR.
The symbols used to represent these can vary, but the ones that I will be using are:
And = &
Or = |
Not = !
Xor = ^
Nand = !&
Nor = !|

You can write �truth tables� to see what the outcomes will be for each of the logic gates:

A B A&B
0 0 0
1 0 0
0 1 0
1 1 1

A B A|B
0 0 0
1 0 1
0 1 1
1 1 1

A B A^B
0 0 0
0 1 1
1 0 1
1 1 0
note that xor is �exclusive or�. It works like an OR gate except it only returns true (1) if only a or b is true, not if both are true.
I won�t write out the truth tables for the rest, but I�ll define them for you.
NOT just returns the opposite of the value. So !1=0 and !0=1
NAND is basically just �not and�. It gives the opposite value that an AND gate would give.
NOR is just �not or�. It gives the opposite value that an OR gate would give.
=========================================================================

Bitwise Operations

Bitwise operations are very much like Boolean logic operations.
The bitwise operators are:
&=and
|=or
!=not
^=xor
~=one�s compliment
&gt;&gt;=right shift
&lt;&lt;=left shift

You already know how the and, or, not, and xor operators work, but you probably didn�t know that you can apply them to full strings of binary. For example, if you have 10100101|10110111 it would be the same as apply or to each corresponding digit for the two.
10100101 OR
10110011 Equals
10110111
The same goes for all the and and xor operators.
The NOT operator works slightly different than you may expect. If you have any non zero number, the NOT of it will give zero, and the NOT of zero will give one.

Now, if you remember back to the beginning of this article, I briefly explained what one�s compliment was. So basically, if you use the ~ operator on a number, it will flip all of the bits, so 1011 would become 0100.

Right shift does exactly what it sounds like. It shifts the bits to the right. So, if you have the binary number 0101000, and you use the right shift operator on it like this: 0101000&gt;&gt;3, it will shift all of the bits to the right 3 places, so you will get 0000101. This is the same as dividing by 2^3 (that�s 2 to the third power, not 2 xor 3)
So x&gt;&gt;n is the same as x/2^n
Note that the right shift does preserve sign. So if you have a number like 1011 (this number is negative since the sign bit on the far left is one) and you shift it to the right, it will fill in the leading bits with ones. So 1011&gt;&gt;2 will be 1110. Also note that since these are integers, there will be a round-off error.

Left shift works the same way as right shift. It shifts the numbers to the left. This always fills in the new bits with zeroes though. Left shift (x&lt;&lt;n) is the same as x*2^n.

You can create all of the operators used in programming with these and the plus operator.
For example:
To make a number negative, you can do this: (~x +1)

To see if two numbers are equal, you can do this:
Given int x and int y, the is equal operator is: !(x ^ y)
To see if a number is positive, you can do this: !(x&gt;&gt;31) & !!x; (note an integer is 32 bits)

There are many more things that you can do with these, but you are probably thinking �why the hell would I waste my time doing that crap when I can just use an if statement?� Well I was thinking the same thing until I learned that using bitwise operators is actually much faster and more efficient as far as processing time than using for loops and if statements. So if you are in dire need of efficiency, this might be the way to go.

well, i hope you enjoyed this article, and maybe you learned something.
-ynori7

 on February 25 2008 - 23:23:37Well written, well explained. And i learnt something! Definitly Awesome! :ninja: on February 26 2008 - 00:15:56You weren't kidding when you said you knew what you were talking about. Great job, man. on February 26 2008 - 01:18:16Nice job, Great content and layout. Kept my attention. 10/10 on February 26 2008 - 06:26:28Great article, was debating about writing an article on hex/dec/binary and pos/neg, but you completely beat me to the punch, AND outdid what I was planning. Kudos! on February 27 2008 - 07:35:53Very interesting and well written. Rated awesome :love: on March 04 2008 - 13:24:14Good article. I also like it is going more in depth the matter than other articles here. For the ones, who are wondering were the xor operator in C is... [offtopic] There isn't one. Funny enough this is one of the most important operations. Why? If you have a xor operator (or a controlled not as it is called sometimes, find out why!), you can build all the other operators. So if a physicist can build a controlled not port in some quantum system, he can build a simple computer out of it. Well of course if he is able to build more than one and able to preserve it long enough. [/offtopic] A boolean XOR operator is easy to make (a + b)%2. on March 06 2008 - 23:16:10there's an xor operator in C. you use the little carrot key (^). on December 04 2009 - 01:42:38Awesome Article.Loved how you explained it. on March 26 2011 - 05:15:16Amazing article, well done. You always seem to impress me ynori.