7508 posts
Australia
Posted 03 May 2013 - 02:18 PM
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…
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)
Binary numbers (Base-2)
Converting binary to decimal (the hard way)
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)
We then write our binary number into the spaces (lets put in 01001110)
Now we look at this table and each number that has a 1 to it, we add them together. So it becomes
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
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
If we wish to convert 23 into Binary we do it like so:
An easy way to convert from decimal to hexadecimal (well the way I find easiest)
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
Binary Arithmetic
What can computers do?
Fundamentally computers are built to perform the following operations:
The hardware in computers is built to perform additions, all other operations are built on top of this basic capability
Binary addition
So now a practical example
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
Example (assume 4-bit computer):
We literally move the bits either left or right.
Do bits fall off?
Assume we have an 8-bit computer
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
One's Complement
Zero -> One
One -> Zero
We just literally flip the bits
Example:
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
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
An exercise:
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
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
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
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
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
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…
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 numberConverting 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 |
+-----+----+----+----+---+---+---+---+
| | | | | | | | |
+-----+----+----+----+---+---+---+---+
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
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
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 11104 and 14 respectively78 in hex is 4EBinary Arithmetic
Spoiler
Given any number we can perform the following simple operations on them:- Addition
- Subtraction
- Multiplication
- Division
What can computers do?
Fundamentally computers are built to perform the following operations:
- Addition
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 shiftingExample (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
One's Complement
Spoiler
The one's complement form of binary number is the complement of the digitsZero -> 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)
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 AlgebraAND (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 on 04 May 2013 - 09:30 PM
