Note of Math For Programmers

Math For Programmers

Virtual Memory from 0 to n, map fromm virtual memory to physical memory

####Inside of Memory Location bit: 1/0

Memory Location: 8bits = 1byte Registers 64bits = 8bytes

8bits = 2^8 =256 values
16bits = 65536 values
32bits = 4.3billion values
64bits = 18million trillion values

1/0

- Boolean
- Signed Integer(- + 0)
- Unsigned Integer(+ 0)
- Floating Point Number

Mapping High Level Data Types

Bool
- Bool
Signed Integer
- Int
- short
- long
- sbyte
Unsigned interger
- uint
- ushort
- ulong
- byte
- object (reference of memory location(from 0 to int))
- char
Floating point
- float (32bits)
- double (64bits)
?decimal (not sure)

Demo: Characters as Integers

    A : 65
    B : 666
    a : 97

Working in Binary

Computers count in 2's

Base 2 Binary Base 10 Decimal

b10 = 2^1+0=2
b11 = 2^1+1=3
b100 = 2^2+0+0=4

b11 + b1 = b200 = 4

Little-Endian (Intel chip)

Big-Endian

Capacity

p binary bits => 2^p unique values
(0,2^p-1)
so biggest number in 3bits = 7

Units

kilo (K) = times 1000 ≈ 2^10 = 1024 (Thousand)
mega (M) = times 10^6 ≈ 2^20 = 1048576 (Million)
giga (G) = times 10^9 ≈ 2^30 = 1073741824 (Billion)
Tera (T) = times 10^12 ≈ 2^40 = 1099511627776 (Trillion)

Hexadecimal

Base 16 is called hexadecimal

A = 10
B = 11
C = 12
D = 13
E = 14
F = 15

x14 = 16+4 =20
x2b = 2*16+11 = 43

Important because gives good way to view binary numbers

eg. When looking at memory locations during debugging
    01100100

Bianry to Hexadecimal

b 1 1011 = 2^4+2^3+0+2+1 = 27
b 10 0110 1111 = 623
b 1011 1001 1001 = 2969
x  B    9    9   = 11*2^8 + 9*2^4 + 9

Converting the Other Way

Binary to Hex

x 1    A    9    F
b 0001 1010 1001 1111

0000 = 0    1000 = 8
0001 = 1    1001 = 9
0010 = 2    1010 = A
0011 = 3    1011 = B

0100 = 4    1100 = C
0101 = 5    1101 = D
0110 = 6    1110 = E
0111 = 7    1111 = F

0x0000ff = 15*16^1 + 15*16^0

Octal

o 144 = 100 = 1*8^2 + 4*8 + 4 = 100

Octal, Hex and Binary

b 1011 1001 1001 = 2969
x  B    9    9   = 11*2^8 + 9*2^4 + 9
b 101 110 011 001 = 2969
o  5   6   3   1  = 5*8^3 + 6*8^2 + 3*8 +1 = 2369

####Converting: Decimal to Hex

20 => how many 16's are in this number?
20/16 = 1 remainder 4 => o 14

2969/16 = 185 remainder 9
185/16 =11 remainder 9
2969 = o B99

Use Windows Calculator

Calculator =>  "view" => "Programmer"

Integers

Understanding Overflows

Might cause overflow

+
*
- (100 - (-100) = 200)
left shifting
?

Won't cause overflow

%
other bitwise ops

####Preventing Overflows

b 1111 1111 * b 1111 1111 = 255 * 255
= b 1111 111 0 0000 0001 = 65025
- Operand word sizes m,n: Need word size m+n in result
- 8bits + 8bits =>need 16 bits

b 1111 1111 + b 1111 1111 = 255 + 255
= b 0000 0001 1111 1110 = 510
- Operand word sizes m,n: Need word size max(m,n)+1 in result
- 8bits + 8bits =>need 9 bits

###Negative Numbers

Sign-and-Magnitude

b 0111 1111
  0: Sign bit
   111 1111: Magnitude

Lose 1 bit to the sign => Only half magnitude left Store 0->127 and 0->-127 instead of 0->255

b 0001 1101 = 29
0x 1D
b 1001 1101 = -29
0x 9D

Why we don't use Sign-and-Magnitude not used in int but float

Two ways to store 0
```
  b 0000 0000 = 0
  b 1000 0000 = 0
```
We've lost a unique value b 1000 0000 = 0
Basic arithmetic more complicated
- b 0001 1101 + b 1000 0110 = 29 - 6 \neq 33

One's complement

To make a number negative, reverse every bit

b 0001 1101 = 29 (0x 1D)
b 1110 0010 = -29 (0x E2)

Two's complement

Only one representation of 0: 0x 00
Range -2^n to 2^n-1 (for 8bits -128 to 127)

Arithmetic 'Just Works'

  b 0111 1111 = 127 (0x 7F)
  b 1000 0000 = -128 (0x 80) |8>7 therefore \-
  b 0000 0000 = 0 (0x 00)
  b 1111 1111 = -1 (0x FF) |F>7 therefore \-

Overflow on Division

8-bit integers:
-128/-1 = 128 (for 8bits -128 to 127)

Changing Sign

b 0000 0011 = 3
b 1111 1100 = -4
b 1111 1101 = -3 (0x FD)

Changing Word Size

Value in large word ===> Narroing ===> Value in small word
Value in large word <=== Widening <=== Value in small word

sbyte b1 = 30;
sbyte b2 = -3;
sbyte sum = (sbyte)(b1 + b2);

#####Widen positive number:

Pad with zero's:
`0x 1E => 0x 001E`

#####Widen negative number: More complicated

    Widen -3 : 8 to 16 bits:
    zero-extend:
    8bits : 1111 1101 = -3
    16bits : 0000 0000 1111 1101 = -3 (Wrong)
    16bits : 1111 1111 1111 1101 = -3 (Padding with 0)

Sign-extension

    Widening: Sign bit = 1? Pad with 1 : Pad with 0;

Narrowing

If excess bits and new sign bit are all zero: 0000 0000 0001 1011 can truncate: 0001 11011 = 27

If excess bits and new sign bit are all one: 1111 1111 1111 1101 = -3 can truncate: 1111 11011 = -3

If excess bits plus the new sign bit contain 1's and zero's: 0000 0001 1111 1111 = 511 can't truncate - value is too big: 1111 1111 = -128

Integer Division

'True' divsion often often gives a fractional answer 8/2 = 2.5 only store as 2. 8/3 = 2.67 approx. only store as 2.

Integer Division 'Gotchas'

Exception if divide by zero
Dividing by -1 might cause overflow
Answer is language-dependant

Shifting

How do you multiply by 10? 5*10 = 50 add (0 and left shift) How do you divide by 100? 1300/100 =13 (Remove two zeros and right shift)

Multiply by 10^n Add n zero's and left-shift Integer-divide by 10^n Remove last n digits and right-shift

Multiply by 2^n Add n zero's and left-shift Integer-divide by 2^n (But only true for positive numbers) Remove last n digits and right-shift

    1111 1010 = -6 = 0x FA
    1111 1101 = -3 (right shift and pad with 1)


    1111 1001 = -7 = 0x F9
    1111 1100 => -4 (right shift and pad with 1)

Should You Use Shift Operators

Compilers will do it for you if appropriate
Shifting harder to understand

int result = x/8; int result = x >> 3;

Selecting Integer Types

Shorter words better for Performance? Unlikely - will be sign-extended for most operations

    for (byte i = 0; i<10; i++){
        DoSomething();
    }

Use a standard 32-bit or 64-bit unsigned integer unless there's a specific reason not to.

Best Practices - Integers

Be wary of mising different integer types
Prefer arithmetic over shifting operations
Be on guard for overflow errors
For very large integers

Floating Point Numbers

Types of Number

Real Numbers : all numbers on the lin
- Rational Numbers
- Irrational Number

Understanding Decimals

Fractions in Binary

    b 0.1 = 1/2
    b 0.11 = 1/2 + 1/4 = 3/4