Skip to content

Instantly share code, notes, and snippets.

@panfeng

panfeng/Note_of_Math_For_Programmers.md

Last active August 29, 2015 14:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save panfeng/d5e0ad8402ec88924398 to your computer and use it in GitHub Desktop.
Save panfeng/d5e0ad8402ec88924398 to your computer and use it in GitHub Desktop.
Download ZIP
Note of Math For Programmers
Raw
Note_of_Math_For_Programmers.md

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)

00000101
00000000
00000000
00000000

Big-Endian

00000000
00000000
00000000
00000101

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

Fractions in Binary

    b 0.1 = 1/2
    b 0.1000 =  0x 0.8 = 1/16 * 8 = 1/2

    b 0.11 = 3/4
    b 0.1100 = 3/4
    0x0 C =  12/16 = 3/4

Most numbers can't be exactly represented

1/3 = 0.333333...

In decimal:

  • 1/n can be represented exactly if the only prime factors of n are 2 and 5 because 10 = 2*5

      1/20 = 0.05 (because 20 = 2*2*5)
  1/50 = 0.02 (because 2*5*5)
  1/6 = 0.16666.. (can't represented exactly)

  • Can't represent 1/n exactly then you can represent 2/n, 3/n etc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment