User:Saul/cs and math

From Organic Design wiki
< User:Saul
Revision as of 06:05, 3 August 2019 by Saul (talk | contribs) (Boolean Algebra)

Bases

Binary

Unsigned

Unsigned binary can represent numbers from 0 to 2bits - 1, eg. 4 bits of unsigned binary can represent numbers from 0 to 15.
In unsigned binary all numbers are positive.
Here is a few conversions from decimal to binary:

Binary : Decimal
000 : 0
001 : 1
010 : 2
011 : 3
100 : 4
101 : 5
110 : 6
111 : 7

One's Compliment

One's compliment was an old way of specifying signed binary.

The way of specifying a number as negative in binary was to set the most significant bit (The left most bit) to a 1.
0XXX would be a positive number and 1XXX would be a negative number.

In one's compliment negative numbers are represented by setting the most significant bit (The left most bit) and flipping all the other individual bits to the opposite.
For example to get -2 in binary:

010 (+2 in decimal)
-> 110 (Set the most significant bit to 1)
-> 101 (flip all other bits, -2 in decimal)

Here is a few conversions from decimal to binary (one's compliment):

Binary : Decimal
1000 : -7
1001 : -6
1010 : -5
1011 : -4
1100 : -3
1101 : -2
1110 : -1
1111 : -0
0000 : +0
0001 : +1
0010 : +2
0011 : +3
0100 : +4
0101 : +5
0110 : +6
0111 : +7

The issue with one's compliment is that there are two zeros - 000 = +0, 111 = -0 and adding one's compliment numbers together does not always correctly sum, for example:

5    + -3  = 0 (Decimal)
0101 + 1100 = 10001 = 0001 (drop the left most bit as it is out out of the 4-bit scope)

Two's Compliment

Two's compliment can represent numbers from -2bits - 1 to 2bits - 1 - 1, eg. two's compliment in 4 bits can represent numbers from -8 to 7
Two's compliment is a solution to the problems that one's compliment has.
To turn a binary number to its negative, start by doing the same thing as one's compliment, then just add 1 to the result for example:

0101 (unsigned binary : 5 in decimal)
1010 (one's compliment)
1011 (two's compliment : -5 in decimal)

To turn a binary number from its negative to its positive just do the same process!

Examples

Here is a few conversions from decimal to binary (two's compliment):

1000 : -8
1001 : -7
1010 : -6
1011 : -5
1100 : -4
1101 : -3
1110 : -2
1111 : -1
0000 : +0
0001 : +1
0010 : +2
0011 : +3
0100 : +4
0101 : +5
0110 : +6
0111 : +7
Other Notes

Two's compliment is like the standard way of looking at binary but the most significant bit now represents the negative version of itself as this table shows:

-8 4 2 1 Calculation Result (Decimal)
1 0 0 0 1x-8 + 0x4 + 0x2 + 0x1 -8
1 0 0 1 1x-8 + 0x4 + 0x2 + 1x1 -7
1 0 1 0 1x-8 + 0x4 + 1x2 + 0x1 -6
1 0 1 1 1x-8 + 0x4 + 1x2 + 1x1 -5
1 1 0 0 1x-8 + 1x4 + 0x2 + 0x1 -4
1 1 0 1 1x-8 + 1x4 + 0x2 + 1x1 -3
1 1 1 0 1x-8 + 1x4 + 1x2 + 0x1 -2
1 1 1 1 1x-8 + 1x4 + 1x2 + 1x1 -1
0 0 0 0 0x-8 + 0x4 + 0x2 + 0x1 0
0 0 0 1 0x-8 + 0x4 + 0x2 + 1x1 1
0 0 1 0 0x-8 + 0x4 + 1x2 + 0x1 2
0 0 1 1 0x-8 + 0x4 + 1x2 + 1x1 3
0 1 0 0 0x-8 + 1x4 + 0x2 + 0x1 4
0 1 0 1 0x-8 + 1x4 + 0x2 + 1x1 5
0 1 1 0 0x-8 + 1x4 + 1x2 + 0x1 6
0 1 1 1 0x-8 + 1x4 + 1x2 + 1x1 7

Addition

Unsigned

To add binary numbers together you add the digits together from the right to the left and if you add two 1's together the result is 0 with a carry.

Example

Add 110100102 (21010) and 011001112 (10310).

1   11
 11010010
+01100111
---------
100111001

Note: This overflows the 8bit context!
110100102 (21010) + 011001112 (10310) = 1001110012 (31310)

Signed

Adding signed binary is the same as unsigned but the overflow must be removed!

Example

Add 110100102 (-4610) and 011001112 (10310).

(Using the unsigned working for this number)
110100102 + 011001112 = 1001110012

Remove the overflow from the 8 bit scope in the result:
110100102 (-4610) + 011001112 (10310) = 001110012 (5710)

Subtraction

To subtract a binary number from another convert the second number to the two's compliment and add them together as usual.

Example

Subtract 00102 (210) from 01012 (510).

0101 - 0010
-> 0101 + (-0010)

Find the two's compliment of 0010:

0010
-> 1101 (Flip bits)
-> 1110 (add 1)

0010 two's compliment is 1110.
Substitute two's compliment to as the negative second number:

-> 0101 + 1110

Add them together:

1
 0101
+1110
-----
10011

Remove the bits that exceed the scope (4bit scope in this case).

10011
-> 0011 (removed overflow)

Therefore 01012 (510) - 00102 (210) = 00112 (310)

Full Working
0101 - 0010
-> 0101 + (-0010)

Convert (-0010) to two's compliment:
-> 1101 (Flip bits)
-> 1110 (add 1)

-> 0101 + (-0010)
-> 0101 + 1110 = 10011
-> 0011

Octal

Octal is base 8 and is easy to convert from/to binary due to its special property, that which is having 2 as one of its roots, eg. 23 = 8
Octal digits never exceed 7, 8 is represented by 10.

Binary to Octal

Number to convert:

01010101000111

Since octal is 23 we can separate the binary digits in sets of threes from the right to the left.

01 010 101 000 111

Since the first set of numbers has only 2 numbers in it we add leading zeros as necessary.

001 010 101 000 111

Convert these sets of threes into Decimal or Octal (Same thing since a single octal (8) digit does not exceed decimal (10)):

1 2 5 0 7

Concatenate the results together and you have your Octal representation:

12507

Hexadecimal

Hexadecimal is base and is favoured in computing due to it being a larger base than Octal or Decimal and it has the property of having 2 as one of its roots, eg. 24 = 16
Hexadecimal digits represent the decimal numbers from 0-15 where digits above 9 are represented by letters.
Here is few conversions from Hexadecimal to Decimal:

Hexadecimal : Decimal
0 : 0
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 8
9 : 9
A : 10
B : 11
C : 12
D : 13
E : 14
F : 15

Binary to Hexadecimal

Number to convert:

01110101000111

Since hexadecimal is 24 we can separate the binary digits in sets of fours from the right to the left.

01 1101 0100 0111

Add leading zeros if necessary:

0001 1101 0100 0111

Convert the groups into decimal (from binary):

1 13 4 7

Convert the sections into hexadeimal (from decimal):

1 D 4 7

Concatenate the results together and you have your Hexadecimal representation:

1D47

Other Bases

Convert to Decimal

To convert a number of a different base to decimal sum the total of each digit times the base to the power of its position (starting at 0).
Pseudo code representation:

d = digit;
b = base;
p = position;

sum = 0;
for every digit in number
	sum  += d*b^p;
Example

Convert 601252067 to decimal:

Number: 60125206
Base: 7

Multiply each number by the base to the power of position (starting at 0):

6x7^7 + 0x7^6 + 1x7^5 + 2x7^4 + 5x7^3 + 2x7^2 + 0x7^1 + 6x7^0

Calculate:

6x823543 + 0x117649‬ + 1x16807‬ + 2x2401 + 5x343 + 2x49 + 6x1
4941258  + 0        + 16807   + 4802   + 1715  + 98   + 6

4964686‬

Therefore 601252067 is 496468610

Convert from Decimal

To convert a number from decimal you have to recursively divide it by the base and set the remainder as the digit.
Pseudo code representation:

n = number;
b = base;
i = current iteration;
d = digit string;

d = "";
i = n;

do
	d.append(i % b);
	i = floor(i / b);
while floor(i / b) > 0

d.reverse();
Example

Convert 28310910 to base 17.

Number: 283109
Base: 10

Recursively divide by base and take the remainder like so:

283109 / 17 = 16653	r 8
 16653 / 17 =   979	r A (10)
   979 / 17 =    57	r A (10)
    57 / 17 =     3	r 6
     3 / 17 =     0	r 3

Read the remainders from bottom to top:

36AA8

Therefore 28310910 is 36AA817


Boolean Algebra

Boolean algebra is usually used in circuit design.

Table

Programming, Engineering and Mathematics often use different symbols to represent Boolean expressions as this table shows:

English Programming Engineering Mathematics
AND &&
OR +
XOR (Exclusive Or)
NOT ! ¬
TRUE true 1
FALSE false 0

Precedence

The order in which Boolean algebra are completed are: Brackets -> NOT -> AND -> OR

Laws

Here is a list of 15 laws when working with Boolean algebra equations: (Note the Engineering notation is used except in the case of not where programming notation is used due to HTML entity limitations)

  1.  !(A+B) = !A • !B
  2.  !(A•B) = !A + !B
  3. A + A = A
  4. A + 0 = A
  5. A + 1 = 1
  6. A + !A = 1
  7. A + A • B = A
  8. A • A = A
  9. A • 0 = 0
  10. A • 1 = A
  11. A • !A = 0
  12. A + !A • B = A + B
  13. A • (B + C) = (A • B) + (A • C)
  14. A + (B • C) = (A + B) • (A + C)
  15. A = A