In my view, knowledge of binary number systems is very important to programmers, especially C/C++ programmers. Newcomers to C/C++ should benefit from this little discussion. This is not a very detailed tutorial, just to give you some idea. Obviously if you want to find out about one or more of the topics presented, search the net or get a book or ask a friend or better yet post in a forum. Let's get started.

Ok so they say all the information in computers is stored in 1s and 0s. On and Off. True or False. Why? Because of the way electric devices work. Computers are made of circuits. Beneath all the high level software stuff, there are circuits built into the processor which do most basic routine the HARDware way. For example, there is an Adder circuit built into each processor, which ... ADDS! also there is a comparison circuit which Compares, etc. so how do the circuits do this? A circuit is nothing but a wire with transistors along the way which combine to act as logic gates. What is a transistor? Basically, it is a tiny little switch which has two input lines and an output line and a switch. One of the input lines is called a "control", and the other input line is called "IN" and output line is called "OUT". now remember it's a wire with a switch between it. the current is flowing in through one direction (the "IN" line), to the other end (the "OUT" line). But the circuit is not complete because switch is off. this is where the Control comes in. By applying enough force say +5 volts to the control, you push the switch, which completes the Circuit, thus allowing the current to pass thru "IN" to "OUT". Then you have some device at the "OUT" end to read the current. If the current is passing, it detects the current! Which means TRUE or 1 or ON. and say you don't want current passing through, then you simply cut off the voltage to the "Control" which will disengage the switch, thus making the circuit incomplete. The device won't read any current, which will be OFF, or FALSE, or 0. Phew all that work.

--ON a side note, transistors were invented by Dr. William Shockley, a brilliant scientist who put "silicon" and "valley" in the "silicon valley". However he later "SHOCKED" the world with his "inferiority" racial genetic theory. Something about blacks being genetically intellectually inferior to whites.--

Ok so let's continue.... So by arranging several transistors in a circuit, you can create logical gates, which takes in two inputs and gives out one output. Basic gates are AND, OR and NOT. All logical complicated logical statements can be created using AND, OR and NOT. Furthermore, according to DeMorgan's law, all logical statements can be represented just using AND and NOT or OR and NOT. However, all three are used. so what are these AND, OR and NOT? These are logical evaluators which operate on TRUE and FALSE: 1 and 0. George Boole invented this system of logic.

There is an entirely different branch of mathematics which was created by a brilliant mathematician George Boole, and is named Boolean Algebra in his honour. --George Boole dropped out of school at a very very young age, in 3rd grade or something. He self taught himself mathematics and very many logical things from books. talk about self home-schooling!--

Getting back, I wanna point your attention to an earlier question. Why 1 and 0? 1 and 0 number system is called binary number system, because it has 2 digits: 1 and 0. The number system us humans use is called decimal number system because we use 10 digits: 0 - 9 .

-- According to historians, we use decimal number system because we have 10 fingers (to be technical, 8 fingers, 2 thumbs) or digits. Don't believe me? COUNT! Don't forget to count the finger you're counting with! Those of you who have only 2 fingers, I envy you. In addition to having machines obeying your way of counting, you also have a term "two finger typist" named in your honor! Those with 16 fingers, you're lying! nobody has 16 fingers!

Ok so why not design machines to work with decimal number system? Because of the nature of electrical devices. As you may or may not know, as a device gets older, it's capacity to hold voltage decreases. Let's imagine we had a device to process decimal number system. What would we need? Well basically the device would need to detect different voltage level coming to it through a circuit. so no current would be 0, +5 voltage would be 1, +10 would be 2, +15 would be 3 and so on.... till +45 which would be represented as 9. Overtime, voltage holding capacity would drop, and +45 voltage coming in, would turn to +42 or something and so on. So is +42 8 or 9? Furthermore, if the capacity were to drop more to +39, then a 9 would be unintentionally converted to 8! Not good! Destroys the entire purpose! So thats why we have On and OFF. Either the voltage is coming through, or it isn't! Doesn't matter if you read +10 or +7 or +5 or +3.
Make sense so far? If not, do some research!

Ok so back on track: logical gates: AND, OR, NOT. logical gates(except NOT) have 2 inputs, 1 output. so based on combination of values passed to a gate, you get a specific ouput. We use truth tables to look at all the possible inputs and outputs of a logical operation. I'm not going to cover truth tables. Too much explaining. Just look them up. So to give you an example,
False AND False gives you FALSE
so 0 AND 0 gives you 0
1 AND 0 = 0
1 AND 1 = 1

NOT just flips the statement. Turns 1 into 0, 0 into 1. NOT gate only takes 1 input.

1 OR 1 = 1
1 OR 0 = 0
0 OR 0 = 0.

These operators actually make sense. for example if i say: I am 23 AND I am a billionaire, the statement is false, because even though I am 23, I am not a billionaire.

The OR operator is used in the inclusive sense,as opposed to the exclusive sense in regular English. We say in English: You can have a cookie OR a candy to say to a child (or a grownup) that they may either have a cookie or a candy. But in mathematical language OR means, you can have either a cookie or a candy or both if you so choose! So next time someone tells you you can either have this or that, take both because you are a mathematician( a greedy one) and you speak the universal language which is math!!!
There is an exclusive operator which is called XOR, but it can be created from basic AND, OR and NOT.
1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 0 = 0
Means you can have either one or the other, but not both. Obviously you must have one or the other, you can't say no to both either!

Imagine choosing between Death by starvation or Death by overeating! I'd choose starvation, since then I won't take up much coffin space! Also I won't ruin my pants after I die, so I'll die with some dignity!

Ok so using these basic gates and circuits, we can build mighty complicated things such as a comparison circuit or an adder into a processor! Pure hardware! These things take a lot of transistors. But higher level things are done with software, which is built on low level things. imagine taking quarks, then building nucleus with neutrons and protons and building an atom out of neutrons and protons and electrons then building molecules, then building chains and chains of molecules to form every thing! well you get the idea. If you are trying to build a chair, you don't care about things at molecular level. That doesn't mean things don't happen at molecular level. You should have some appreciation of little things! Ok so I hope this little article added a little bit to your vast database of knowledge. More to come on binary number system. I am just getting started!

__________________
spasms!!!

OK! So lets investigate binary numbers a little bit more.

To recap - Decimal = base 10, hexadecimal (or simply hex) = base 16 and binary = base 2.

So how do we represent numbers beyond 0 and 1 in binary number system? Just like we do in decimal, or any other system.


Let's say we have number 1023 in decimal

3 X 10^0 = 3 x 1 = 3
+
2 X 10^1 = 2 x 10 = 20
+
0 X 10^2 = 0 x 100 = 0
+
1 X 10^3 = 1 x 1000 = 1000

= 1000 + 20 + 3 = 1023

so as you know, you represent binary numbers with strings of 0s and 1s

let's say you have a number 1011 in binary:
you'd dissect it just like you'd a decimal number from right to left but this time multiplying each digit by successive powers of 2:
1 x 2^0 = 1 x 1 = 1
+
1 x 2^1 = 1 x 2 = 2
+
0 x 2^2 = 0 x 4 = 0
+
1 x 2^3 = 1 x 8 = 8
= 1+2+0+8 = 11 in decimal! 1011 in binary is 11 in decimal
go on try a few: 10111, 100011, 10001110

Just keep in mind, no matter what the representation system of numbers, they represent the same value: 1011 binary = 11 decimal = B hex and so on, the meaning doesn't change.

Here's a question: how do you tell in decimal number system if the number with multiple digits is even or odd?
we know that 0=even and 1 = odd. you keep adding 2 to each of them and you get evens or odds: 0,2,4,6,8 are even digits, 1,3,5,7,9 are odd digits
So any decimal number that ends in even digits is even, and any that ends in odd digits is odd. simple. furthermore, any number evenly divisible by 2 (remainder 0) is even and any number which has remainder 1 after dividing by 2 is odd.

So how do we tell a number is odd in binary system? Simple. 0 is even, 1 is odd. any number with multiple digits that ends in 0 is even, any number ending in 1 is odd.

Ok let's do some binary addition:

1001 = 9
+0110 = 6
------
1111 =15

Heres the process: add from right to left.
1+0 = 1
0+1 = 1
0+1 = 1
1+0 = 1

let's do another one:
1111 ---> carry row
1101 = 13
+ 1011 = 11
-------
11000 = 24

Just like in decimal, when addition of 2 digits exceeds the value that can be contained in a digit, you need a carry. in binary, you carry 1 over to the next column.
Rules for binary addition:
1+0 = 1 with no carry
1+1 = 0 with a carry to next column
1+1+1 = 1 with a carry
1+1+1+1 = 0 with a carry

basically for odd number of 1s in an addition column, your resultant digit is always 1 with(or without) a carry.
for even number of 1s, it's always 0 with a carry.

more to come

__________________
spasms!!!

Ok let's do subtraction now.
1
. 1001 =9
- 0101 =5
--------
. 0100 =4

subtraction is a little bit different, but nevertheless simple:
starting with the rightmost column,
1-1 = 0
0-0 = 0
0-1 = 1 (with a borrow from the column next to it)

so the leftmost column had a borrow of 1, and it's 1-1-0 = 0
you put the borrow on top of the column from which you end up borrowing.

so the rules for subtraction are:

0-0 = 0
1-0 = 1
1-1 = 0
0-1 = 1 with a borrow.

ok so what happens if you run out of borrows? let's see:

. 1101 = 13
- 1110 = 14
-------
. 1111 = 15

once again from the right:
1-0 =1
0-1 =1 (with a borrow)
1-1 =0; 0-1 = 1 (with a borrow)
1-1 =0; 0-1 = 1 (with a borrow)
Woops! on that last one, we ran out of the places to borrow from!

Ok so what's the solution?
Just like in decimal, instead of trying to subtract a larger number from smaller
we subtract smaller from larger and put a negative sign in front of it! voila!
so let's try it!

. 1110 = 14
- 1101 = 13
------
. 0001 = 1
ok we have a 1! do you see another problem? how do we make it negative? as we know, everything in machine language is represented in 0s and 1s. So how do we tell a computer that a number is negative?

Before we get into that, let's note something that is true about most computers today:

It's true that we can represent information in strings of 0s and 1s of any length, but in computers, that string has to be of a specific size: 8 bits.
a bit is 1 single binary digit. 0 or a 1. put 8 binary digits in a string, it becomes a byte. I've done operations 4 bits at a time till now to make things simple. But a computer will deal with operations no smaller than 1 byte at a time. Thats where 8 bit, 16 bit, 32 bit processing comes from. In old days, the processors that processed 8 bit chunks at a time were called 8 bit. and same for 16 and 32 bits. also modern processors with 64 bit processing have arrived. But we're getting ahead of ourselves.

So think of a byte as an atom. Indivisible? Well... Atom can be divided, but as soon as it is, we don't have the smallest unit of the same element anymore! An atom of gold will still be gold! but as soon as it's split, it's not gold anymore. Just like that, we know that a byte is comprised of single individual bits, but we have to deal with an entire byte at the very least. So to represent a 1 in a computer: 00000001 So what's the maximum number you can store in a byte? well calculate it! 1+2+4+8+16+32+64+128 = 255 = 11111111. How about 2 bytes?
1+2+4+8+16+32+64+128+256+512+1024+2048+4096+8192+1 6384+32768 =
65,535
You don't think I actually added that sequence of a number do you? Nope all I did was this: How many bits are in 2 bytes? 16. Whats the left most bit going to represent? 1 x 2^16 = 65,536. did you notice a pattern here? look at 1 byte. the left most bit in a byte represents 128. you add all 8 1s together in a byte you get 255. so 255 is the maximum you can represent with 8 bits. So what is the 9th bit going to represent? 255+1 = 256 =
1 0000 0000 so the maximum number any amount of bits lined up say b, can represent is 2^b - 1 so for 2 bytes = 16 bits, you have (2^16) - 1 = 65,535. To add just 1 more, you gotta move over to the next byte! and make everything else to the right 0. Same thing in decimal! you have the number 9999 9999 you add just 1 to it and it becomes 1 0000 0000. Whole another digit to it!

OK so back to representing negative numbers:
One way to represent negative numbers would be to make the left most bit a sign bit. if the bit is 1, the number is negative, if the bit is 0 the number is positive! so let's see what -15 looks like:
10001111
and 15 = 00001111. Pretty clear distinction eh? But heres' the thing. By using that bit for sign, now the maximum positive number we can represent is:
01111111: 127 instead of 255 before. What happens if we make the entire byte all 1s?: 11111111: -127.
Ok cool so it all makes sense eh? Ah but there's another problem. Can you think of it? how about if all bits are off? 00000000: well the answer's simple! it's a 0. well how about 10000000, ah well umm negative 0? Damn!
Yeah that's what a lot of the engineers said a long long time ago! You see 0 and -0 are the same thing. there's no such thing as a -0. it's 0! Well we don't have a problem with it, but processors do! They can't think! If they are told to compare 10000000 and 00000000, there's a problem. it will say that -0 is less than 0. which we know isn't true. -0 is equal to 0. let's just say, a lot of operations including looping, depend on comparisons, and many comparisons involve comparing a number with 0. so this doesn't work well. The solution is pretty damn brilliant.
However let's sidetrack here a moment. In C, you can have 2 types of numbers, signed and unsigned. if you have an unsigned char, it can represent values anywhere from 0 to 255. If you have a signed char, it can represent from -128 to 127. Wait but didn't we say it's -127 to 127??!! Patience! All will soon come forth! What about a short? -short is a 2 byte integer by the way- -32768 to 32767. So let's re-evaluate our little formula for representing the range of numbers from earlier:

for unsigned numbers: we can represent, where bits = b, 2^b - 1.
so for a byte: it's 2^8 - 1 = 255
for 2 bytes or a short: it's: 2^16 - 1 = 65,535
for 4 bytes or an int(on 32 bit systems): 2^32 - 1 = 4294967295

However for signed numbers: -(2^b-1) to (2^b-1) - 1
byte: -(2^8-1) to (2^8-1 - 1) = - 2^7 to 2^7 - 1 = -128 to 127
short: -32768 to 32767
and so on.

Ok so now for the solution: it's called Twos complement numbering system.
In 2s complement the left most bit is still signed. 0 for positive, 1 for negative.
so 127 is still represented as 01111111. All positive numbers are represented exactly as before, with the leftmost bit or the 7th bit(counting from right to left with the rightmost bit as 0th bit) or if you prefer to say 8th bit(counting the rightmost bit as 1st bit), as 0. In other words, as long as the leftmost bit is 0, the numbers are positive and everything is represented exactly as before. However, in order to represent negative numbers, things change.
In general, the formula for representing Twos complement number is:
2^8 - N, where N is the magnitude of a negative number.
let's take -6, magnitude of which is 6 = 00000110.
2^8 - 6 = 250 = 11111010 = -6 in twos complement.

You might say what??!! so then how do you represent 250? Remember, we can't represent 250 in a signed number on a byte anymore! the range for signed 1 byte numbers is -128 to 127. so there's no 250 on a signed byte. It's -6.

Well how does a computer know if a number is signed or unsigned? We tell it! by declaring it signed or unsigned! if you declare a char as unsigned char, then 11111010 will be treated as 250. but if you declare it as just char, then 11111010 will be treated as -6. same with signed int and unsigned int.

When do we declare a number as unsigned? when you know that the number can't be negative! Speed can't be negative, (although velocity can be), so you declare it unsigned. Population can't be negative. Weight can't be negative. Volume can't be negative. if you don't declare a number unsigned, then it's no big deal, you just won't get that range of values that you otherwise would.

For example if you were using a variable to store the volume, and you don't declare it unsigned, then you are only limited to storing volumes upto 32767, if the variable is short. the volume will never be negative, so you will be wasting memory! so to make it unsigned would mean now you can store volumes up to 65,535! In the end it's upto you. If you have a good reason to use a signed number to store volumes, then you can do so.

Ok so back to twos complement. Remember, all positive signed numbers are represented exactly as before, with 0 as the leftmost bit. If the number you want represented is negative, then you use the little formula. which guarantees that the leftmost bit is 1, and the computer must now treat that number as twos complement so it will know that 11111010 is -6. Well is there a shortcut to the formula? you bet!
let's take -6 again. 6 = 00000110. now to make it -6, you invert all the bits and add 1 to the result. so 0 becomes a 1 and 1 becomes a 0 and then you add 1.
00000110 inverted = 11111001
then you add 1
let's do addition!
. 11111001
+00000001
-----------
. 11111010 = -6
make sense?
let's take -7 this time. its magnitude 7 = 00000111.
invert all bits: 11111000
add 1: 11111001.
this time adding one was simple, since the last digit turned out to be 0. so there was no carry! Well this sure beats that formula earlier! It works the same way for multiple byte numbers. just remember the leftmost bit is the sign bit in signed numbers. so for 2 byte numbers, the 15th bit (or 16th bit if you start counting with 1, which is bad in C/C++!!!) is the sign bit. so you'd make the formula 2^16 - N, where N is the magnitude of the negative number.
and so on for multiple bytes.

Now extremely perceptive of the bunch might ask, ok twos complement is neat and all, but how did this solve our original problem of -0 and +0?
AH! Try it! Whats 00000000 in twos complement? 0
whats 10000000 in twos complement? it's not -0
give up?
well what's +127 look like in binary? 01111111. So what's -127?
10000001. It's all bits inverted plus 1! ah but we said the range was -128 to 127. so where's -128??? well 128 would be 10000000, but we can't represent it in signed numbers. However, if you just had 10000000 in twos complement, why not just make it represent -128? Can't confuse it with anything else can we? Hmm... Another question, how do we represent -1 in twos complement?
take 1 = 00000001, flip all bits = 11111110, add 1 = 11111111. so -1 = all 8 bits turned on! so try reversing our twos complement on 10000000. subtract 1 first.
. 1 <---- borrow
. 10000000
- 00000001
-----------
. 01111111 and then invert all the bits giving you, 10000000.
Pretty unique! trying our little conversion trick on 10000000, gives the same thing both ways around! Why? because 256 - 128 = 128! We may not be able to represent 128 in a signed byte, but we sure as hell can represent -128. so now it makes sense! 256 different combinations for 256 different numbers on a byte! if it's unsigned then its 0 - 255, if it's signed, then it's -128 to 127, with 0 having only 1 unique combination! Pretty neat! If it doesn't make sense, just know that there's no way to represent 128 on a byte, because of the sign byte. positive numbers can't have the leftmost bit 0. but negative numbers can and must!
Oh by the way, the naive method which was introduced earlier, which resulted in +0 and -0 is called 1s complement. Most processors today use 2s complement.

__________________
spasms!!!

few corrections/updates:

in the last post in the end I said something like signed positive numbers can't have the leftmost bit 0, but negative numbers can and must! Sorry that was wrong! how stupid!
correction:signed postive numbers can't have the left most bit 1, but negative numbers can and must.

also waltp pointed out that in order to convert a signed twos complement value such as -6, back to positive, you just invert bits again and add a 1, instead of subtracting 1 and then inverting bits. The latter method works fine, but adding is easier than subtracting don't you think?!

Also note that earlier somewhere in my post I said that computers must take the string of 0s and 1s 8 bits or 1 byte at a time. However, right before that sentence I said that "note something about most computers today". So just know that computer manufacturers in past have tried making bit width or Cell Size 6 bits, 24 bits, 32 bits and whole lot of other combinations. However today they've set a standard of 8 bits per cell or 1 byte per cell.

Any other mistakes, plz forgive me and message me so I can rectify them. "rectify" a funny word isn't it?

__________________
spasms!!!

Reading through your tutorial and your example for "or" I don't think is correct. "1 or 0 = should be 1 not 0. I've always thought of Or as a parallel circuit. If you turn on one switch or both you get current flow.

Its a great thread - very knowledgeable indeed I confess.

Don't know how many people read through it but there is one error though which I think everyone missed:
I've highlighted the error: 1 OR 0 = 1 (and not 0)


Yes it has, and thanks for the complement!!

The more easy process of converting numbers from one base to another are as follows :

converting (121) to binary

121/2 remainder= 1 quotient=60
60/2 remainder= 0 quotient=30
30/2 remainder= 0 quotient=15
15/2 remainder= 1 quotient=7
7/2 remainder= 1 quotient=3
3/2 remainder= 1 quotient=1
1/2 remainder= 1 quotient=0

in above mentioned example we have divided a decimal number repeatedly by 2 because we want it to be converted into binary and baso of binary is 2.
the process of division continues till the quotient becomes 0 and each time the quotient is divided

therefore binary equivalent of 121 is 1111001 please remember that while writing binary equivalent the remainders should be written from bottom to top.

now converting it in octal whose base is 8

121/8 remainder=1 quotient=15
15/8 remainder=7 quotient=1
1/8 remainder=1 quotient=0

so octal equivalent will be 171 again we write from bottom to top

now try to convert it into hexadecimal and also try some more questions

converting decimal numbers in binary

121.25

first convert 121 normally and for .25 follow this procedure

.25 * 2 = 0.5 integer part =0
0.5 * 2 = 1.0 integer part =1

here the decimal part becomes zero in second time so we need not to go further just write answer as follows

121.25 = 1111001.01

in decimal part we start writing from top to bottom follwo the similar technique for octal and hexa conversion



feel free to ask any query if u have from my post i am ready to answer it

__________________
*Labor omnia consent*** Hardwork conquers all*