33 replies to this topic

[theoriginalbit]

Ok firstly I would like to apologise if any of this is too high level. I will go through it in the near future and definitely try to simplify it more if required.

EDIT: Oh also if you're wondering what this had to do with ComputerCraft, that is coming in the next instalment with Bit Operations, knowing binary and logics is essential to understanding it, but I can't finish this tonight, too tired, need sleep.

Data Representation

Modern technology are all digital devices, i.e. they work with binary (0 and 1). Before a computer can precess data, it has to be represented in binary.

Some terminology...

Spoiler

0 and 1 are known as 'bits'
A sequence of 4-bits is known as a 'nibble' (1 hexadecimal character is a nibble)
A sequence of 8-bits (or two nibbles) is known as a 'byte'
The modern desktop computer uses a 32-bit or a 64-bit processor (meaning they process data in chunks of 32 or 64 bits, 4 or 8 bytes at a time respectively)

Natural Numbers (Base-10)

Spoiler

Base-10 is the numbering system we are all familiar with... the decimal system...

Binary numbers (Base-2)

Spoiler

1001 is a number represented in binary, it is actually the decimal number 9, here is the method to calculate this number

Converting binary to decimal (the hard way)

1*8 [1*2^3] +
0*4 [0*2^2] +
0*2 [0*2^1] +
1*1 [1*2^0]
-------------
9 (decimal representation)

Converting binary to decimal (the easy way, I do it in my head this way)

First we have a table, starting at one, and doubles each time it goes up a column (right->left)

+-----+----+----+----+---+---+---+---+
| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
+-----+----+----+----+---+---+---+---+
|	 |	|	|	|   |   |   |   |
+-----+----+----+----+---+---+---+---+

NOTE: It can go higher than 128, however I'm just not showing it, to go higher just keep doubling the previous number

We then write our binary number into the spaces (lets put in 01001110)

+-----+----+----+----+---+---+---+---+
| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
+-----+----+----+----+---+---+---+---+
|   0 |  1 |  0 |  0 | 1 | 1 | 1 | 0 |
+-----+----+----+----+---+---+---+---+

Now we look at this table and each number that has a 1 to it, we add them together. So it becomes

64 + 8 + 4 + 2

which is decimal 78

this is the only base the above method will work with, for all other bases you must use the first method

A bit more about base numbers

Spoiler

Common Bases:

Base-2 — Binary — digital devices only understand this format
2 digits: 0, 1

Base-10 — Decimal — popular with modern humans.
10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

Base-16 — Hexadecimal — a lot of programmers like this format as it allows us to represent large numbers in a small way
16 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Is any base possible?
Yes, we can have a number in any base we wish, however impractical it is. Another common based that we do see is Octal or Base-8.

Converting from Base-10 to Binary

Spoiler

Now there are a few methods, one of the easiest is using a division technique detailed below.
If we wish to convert 23 into Binary we do it like so:

23 / 2 = 11 (remainder 1)  ^
11 / 2 = 5  (remainder 1)  |
5 / 2 = 2   (remainder 1)  |
2 / 2 = 1   (remainder 0)  |
1 / 2 = 0   (remainder 1)  |
0 / 2 = 0   (remainder 0)  |

put all the remainders together in the direction of the arrow and we get
010111 ... we have just successfully converted 23 into binary

Now before you say "Hang on BIT, since when is 23/2 give you 11, or 5/2 give you 2" well we round down, since there is only 0 and 1 in binary we cannot represent 0.5, so we round down so we have a remainder of 1.

An easy way to convert from decimal to hexadecimal (well the way I find easiest)

Spoiler

Ok so if we have a number that is 15 or less then it is nice and easy, 1-9 is 1-9 and 10-15 is A-F, however when we deal with larger numbers, lets say 78, it becomes a little harder to do in our head.

So this is a nice and easy method of doing it. Convert the decimal number (78) into binary (01001110) then split that number into chunks of 4 bits, that gives us

0100 1110

now we deal with these 4 bits as if they were their own, so we now in decimal we have

4 and 14 respectively

we know that 4 in hex is 4 and 14 in hex is E so

78 in hex is 4E

Binary Arithmetic

Spoiler

Given any number we can perform the following simple operations on them:

• Addition
  
• Subtraction
  
• Multiplication
  
• Division

Virtually everything works off these fundamental operations

What can computers do?
Fundamentally computers are built to perform the following operations:

• Addition

Yep, thats about all they can really do, even subtraction is treated as an addition ( a-b —> a + -b )
The hardware in computers is built to perform additions, all other operations are built on top of this basic capability

Binary addition

Spoiler

Just like natural (or real) numbers you can add Binary numbers using the following rule

1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
1 + 1 = 10

So now a practical example

01001 (9)  +
10001 (17)
------------
11010 (26)

Just like normal addition, we have to carry over the "1"
What happen if we add two 4-bit numbers and the result cannot fit (assume 4-bit computer)
Example:
1100 + 0011 = 1111 [OK]
1110 + 0010 = 0000 [Should be 10000]

We cannot always fit the result, so the carry over is pretty much ignored
NOTE: You can test this on older calculators, add two really large numbers

Binary Multiplication and Division

I will not be covering these in this tutorial as it is quite a bit more complicated and out of the scope of this tutorial. I may however later change my mind and add these in

Bit Shifting

Spoiler

Given a binary number, we can shift the bits either LEFT or RIGHT - this process is known as bit shifting

Example (assume 4-bit computer):

12 = 1100
Shift RIGHT (1 bit) = 0110
Shift RIGHT (2 bits) = 0011
Shift LEFT (1 bit) = 1000

We literally move the bits either left or right.

Do bits fall off?

Assume we have an 8-bit computer

The number 54 = 00110110 (8-bits)
Bit Shifting right (1-bit) = 00011011
Bit Shifting right (1-bit) = 00001101

Since we only have 8-bits, the digits at the end are lost. (this is the way computers work, don't worry)

The same applies when bits are shifted left

Negative Numbers

Spoiler

We can represent negative numbers using a number of different ways

• Using a sign-bit
  
• One's complement
  
• Two's complement

With the sign-bit the leading-bit is used to indicate sign, the rest is for numbers, for example 5 would be 0101 but -5 would be 1101

One's Complement

Spoiler

The one's complement form of binary number is the complement of the digits
Zero -> One
One -> Zero
We just literally flip the bits

Example:

01000110
10111001 [One's complement of the above number]

This operation is also known as a bitwise NOT

The one's complement technique was used by early computers to represent negative numbers
Assuming a 4-bit computer, it can capture 16 different numbers 0000 (0) to 1111 (15)
However, if we want to capture negative numbers we will get the following range
-7 to +7, 16 different numbers because we have +0, -0
One's complement can be used for encoding these different states

Two's Complement

Spoiler

One's complement notation has +0 and -0, which is not really optimal. So two's complement solves this problem.
Two's complement algorithm:
Take the One's complement of the binary representation
Treating this as an unsigned binary integer add 1
The two's complement of a positive number gives us a negative number

Example:
Lets get the two's complement of -10 in binary

1010 (binary representation of 10)
0101 (one's complement)
  +1
0110 (two's complement)

REMEMBER: 1 + 1 = 10

An exercise:

9 - 5
9 + -5

0000 0101 (5)
1111 1010 (one's complement)
	  + 1
1111 1011 (two's complement, i.e. -5)
-------------------------------------
0000 1001 (9)  +
1111 1011 (-5)
-------------------------------------
0000 0100 (4)

Two's Complement Range

If there are 'n' bits then the following rule applies:
Range is: -2^(n-1) to (+2^(n-1) - 1)

Example:
For a 4-bit integer the range is -8 to +7 (replace n with 4 in the above equation)

A table showing the integer representation in 4-bit (http://en.wikipedia....tation_4bit.png)

Boolean Algebra/Logic

Spoiler

We have the following basic operators used in Boolean Algebra
AND (Formal symbol: ⌃) ← conjunction operator
OR (Formal symbol: ⌄) ← disjunction operator
NOT (Formal symbol: ¬ and ') ← negation operator

We also have a complex operator
XOR (Formal symbol: ⊕)

NOTE: Basic statements in programming languages such as if statements and while loops (to name two) use boolean algebra (sometimes refered to as 'boolean logic') to evaluate their conditional

Boolean Algebra — AND
The following is the outcome of the conjunction operator

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

NOTE: AND operator is very similar to multiplication, in hardware this is achieved by using an AND gate (i.e. multiplication uses AND gates)

Boolean Algebra — OR
The following is the outcome of the disjunction operator

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

NOTE: OR operator is very similar to binary addition, in hardware this is achieved using an OR gate (i.e. addition uses OR gates)

Boolean Algebra – NOT
The following is the outcome of the negation operator

NOT 0 = 1
NOT 1 = 0

NOTE: NOT operator is used to flip the bits, this is used to perform the One’s complement (again NOT gates are provided)

Bit Operations

Spoiler

Coming soon...
Will cover the topics of:
Bitwise AND
Bitwise OR

Thank you for reading... Feel free to leave a comment or send me a PM if you're still not quite understanding and I will attempt to help you understand better and also (if required) update this post to reflect accordingly...

Edited by theoriginalbit, 04 May 2013 - 10:30 PM.

[superaxander]

This helped me a lot with understanding binary thanks!

[Mads]

This is a good tutorial, but it doesn't really explain how to use the basic logic gates for arithmetic etc.

[Dlcruz129]

Awesome! All I knew about binary was counting until now.

[theoriginalbit]

superaxander, on 03 May 2013 - 01:58 PM, said:

This helped me a lot with understanding binary thanks!

Dlcruz129, on 03 May 2013 - 07:44 PM, said:

Awesome! All I knew about binary was counting until now.

Cool. I'm glad your learnt something.

Mads, on 03 May 2013 - 02:14 PM, said:

This is a good tutorial, but it doesn't really explain how to use the basic logic gates for arithmetic etc.

Thanks for the feedback, I was too tired to finish it last night but I was planning on revisiting arithmetic after the boolean algebra.

[InputUsername]

Thanks! I now understand binary Also great you explained some hexadecimal too.

[M4sh3dP0t4t03]

Great tutorial even if its not exactly related to computercraft. I have known how binary works but it seems like a nice tutorial for beginners.
Edit: I'm currently working on a little API for converting numbers between binary, decimal and hexadecimal but I'm not sure if I should release it

[theoriginalbit]

KingOfNoobs, on 04 May 2013 - 04:33 AM, said:

Great tutorial even if its not exactly related to computercraft.

Not yet, didn't you read the edit

KingOfNoobs, on 04 May 2013 - 04:33 AM, said:

it seems like a nice tutorial for beginners.

That's what I was aiming it for I based it all off my knowledge but the format and flow inspiration came from the Computer Logics and Essentials class I had to take at university, because sadly I could not provide professional evidence of knowledge in binary to get it exempted

[Orwell]

This is a good tutorial, I believe it's written in an educative manner. I have a few suggestions that you could add that are still not too high level and useful. You could cover the rules of precedence of logical operators. Also, covering the setting (and not), resetting (or), toggling (xor) and checking (and) of bits could give some insight in the practical usage of the logical operators. You could also give De Morgan's laws as this helps with simplifying boolean expressions.

[theoriginalbit]

Orwell, on 04 May 2013 - 11:38 AM, said:

This is a good tutorial, I believe it's written in an educative manner.

Thank you. It was what I was aiming for

Orwell, on 04 May 2013 - 11:38 AM, said:

You could also give De Morgan's laws as this helps with simplifying boolean expressions.

Yeh I was considering this, but I was afraid that it was going to be too high level and/or confusing for most people.

[Pharap]

Good to see another binary tutorial. That makes 2 lol.

I think yours was a lot less wordy than mine.

[theoriginalbit]

Pharap, on 04 May 2013 - 12:06 PM, said:

Good to see another binary tutorial. That makes 2 lol.

Would you believe that I planned on doing this when you did yours ... yes it has taken me this long to get around to it

Pharap, on 04 May 2013 - 12:06 PM, said:

I think yours was a lot less wordy than mine.

Yeh I was/am trying to provide the content in a way that doesn't overload the reader with big and technical terms, but instead provide it in an easy to understand manner.

[diegodan1893]

Nice tutorial, but I think you made a mistake, in binary addition, you said 1+0=0

[Pharap]

theoriginalbit, on 04 May 2013 - 12:48 PM, said:

Pharap, on 04 May 2013 - 12:06 PM, said:

Good to see another binary tutorial. That makes 2 lol.

Would you believe that I planned on doing this when you did yours ... yes it has taken me this long to get around to it

Pharap, on 04 May 2013 - 12:06 PM, said:

I think yours was a lot less wordy than mine.

Yeh I was/am trying to provide the content in a way that doesn't overload the reader with big and technical terms, but instead provide it in an easy to understand manner.

In mine I was just trying to be as thorough as possible.

[theoriginalbit]

diegodan1893, on 04 May 2013 - 03:02 PM, said:

Nice tutorial, but I think you made a mistake, in binary addition, you said 1+0=0

Ah yes, thank you for picking that up. It was really late when I wrote that particular section.

Pharap, on 04 May 2013 - 03:28 PM, said:

In mine I was just trying to be as thorough as possible.

You can be thorough while not being over technical though. Which is what I am aiming to do.

[Symmetryc]

I didn't read the whole thing yet, but really nice tutorial! You might want to explain how to convert from any base to any base, though rather than providing only examples for specific bases.

[Mads]

Symmetryc, on 05 May 2013 - 09:30 AM, said:

I didn't read the whole thing yet, but really nice tutorial! You might want to explain how to convert from any base to any base, though rather than providing only examples for specific bases.

The same rules apply to every numeral system you can imagine.

[Symmetryc]

Mads, on 05 May 2013 - 12:49 PM, said:

Symmetryc, on 05 May 2013 - 09:30 AM, said:

I didn't read the whole thing yet, but really nice tutorial! You might want to explain how to convert from any base to any base, though rather than providing only examples for specific bases.

The same rules apply to every numeral system you can imagine.

I'm not talking about the nature of the bases, I'm talking about converting the bases from one base to another . But I guess it's not very good to implement because it might confuse the viewer if they're a beginner.

[theoriginalbit]

Symmetryc, on 05 May 2013 - 03:02 PM, said:

I'm not talking about the nature of the bases, I'm talking about converting the bases from one base to another . But I guess it's not very good to implement because it might confuse the viewer if they're a beginner.

well I think it wouldn't be too confusing to the beginner if I detailed the long and lazy way (the way I actually do it, since most my math I do in my head and this way is easier, and I'm generally very lazy)
<source-base> —> <base-10> —> <target-base>

[Engineer]

This saves you a lot on time on skype