Computer Science
0%

发表于 更新于 本文字数： 461 阅读时长 ≈ 1 分钟

这里是对计算机感兴趣的物理专业毕业生学习的小小天地。我主要对计算机图形学和计算机系统软件比较感兴趣，所以决定自学这些东西。 本科比较混，除了打游戏，翘课和考试临时抱佛脚啥也没学会。毕业之后才知道知识的重要性，遂决定花一到两年的时间补足自己在这两个领域的基础知识，这博客主要记录我的计划和学习笔记，因为我不知道自己能学到什么高度，所以，如果你无意中发现这个博客，我只是希望这些东西能帮助到你。学海无涯，山高路远，愿作攀登的苦行僧。

已经完成的课程：

  • CS61A

正在进行的课程：

  • CSCI0300 @lecture12
  • CS61B @Week 12
  • MATH 1A @Chapter2
  • CS110L @Week2
  • CS106B @Week2

未来规划的课程：

  • CS61C
  • CS184
  • 南京大学计算机基础
  • 南京大学操作系统

已经读完的书

正在读的书

  • 《概率论基础》，第三版，李贤平 @第二章
  • 《Introduction to computing system (Patt & Patel)》 @Chapter3
  • 《Crafting interpreters》 @Chapter4

未来想读的书

发表于 分类于 ， 本文字数： 3.8k 阅读时长 ≈ 6 分钟

Content

Main content

  • Bits and Datatypes
  • Integer Datatype
    • Unsigned Interagers
    • Signed Interages with 1's and 2's complement code
  • Conversion between Binary and Decimal
  • Operation on bits
    • Arithmmetic operation
    • Logical operation
  • Other Representation
    • Float number
    • ASCII code
    • Hexadecimal Notation

Exercise

Made by myself. I'm not sure if it's correct.

2.1

there are \(2^n\) .

2.2

\(log_2 26 = 4\)
If we need both lowercase and uppercase we need 1 more bit, totally 5.

2.3

  1. \(log_2 400 = 9\)
  2. \(2^9 - 400 = 112\)

2.4

There are \(2^n\) unsigned intager numers,ranged from 0 to \(2^n - 1\).

2.5

number 2's complement signed magnitude 1' complement
-7 11001 10111 11000
7 00111 00111 00111

2.6

10000

2.7

number 2's complement
-8 1000
-7 1001
-6 1010
-5 1011
-4 1100
-3 1101
-2 1110
-1 1111
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111

2.8

  1. \(2^7 - 1 = 127\), binary: 01111111
  2. \(2^7 = 128\), binary: 10000000
  3. \(2^n - 1\)
  4. \(2^n\)

2.9

\(log_2 6.02 * 10^{23} = 591\)

2.10

  1. -6
  2. 90
  3. -2
  4. 14800

2.11

  1. 0110 0110
  2. 0100 0000
  3. 0010 0001
  4. 1000 0000
  5. 0111 1111

2.12

It can divided by 4.

2.13

  1. 1111 1010
  2. 1111 1000
  3. 0001 1001
  4. 0000 0001

2.14

  1. 1100
  2. 1010
  3. 1111
  4. 1011
  5. 0000 (overflowed)

2.15

elimate the last digit and divide by 2.

2.16

number 2's complement 1's complement magnitude
7 + -7 0111 + 1001 = (1)000 0111 + 1000 = 1111 1111 + 0111 = 0110

2.17

index binary dexcimal
a 1100 -4
b 0101 1000 84
c 0011 3
d 11 -1

2.18

index binary dexcimal
a 1100 12
b 0101 1000 88
c 1011 11
d 11 3

2.19

-27 to binary : 1110 0101 (8 bits)
1111 1111 1110 0101 (16bits)
1111 1111 1111 1111 1111 1111 1110 0101 (32 bits)
sign-extension helps bit-extension and don't change its value.

2.20

  1. 1111
  2. 0000
  3. 1000 (overflow)
  4. 0111
  5. 0000

2.21

When 2 number add with the same sign, but result in the other sign.

2.22

1000 0000 0000 0000 + 1000 0000 0000 0000

2.23

The sum is smaller than one of the origin.

2.24

1000 0000 0000 0000 + 1000 0000 0000 0000

2.25

Because the sum of them is in the range of the original one.

2.26

  1. seven
  2. 011 1111 63
  3. 111 1111 127

2.27

Yes. Sum of two positive numbers presents a negetive one. Overflow.

2.28

All the input is one.

2.29

X Y X AND Y
0 0 0
0 1 0
1 0 0
1 1 1

2.30

  1. 0101 0111
  2. 100
  3. 1010 0000
  4. 0001 0100
  5. 0000
  6. 0000

2.31

one of the input is 1.

2.32

X Y X OR Y
0 0 0
0 1 1
1 0 1
1 1 1

2.33

  1. 1101 0111
  2. 111
  3. 1111 0100
  4. 1011 1111
  5. 1101
  6. 1101

2.34

  1. 0111
  2. 0111
  3. 1101
  4. 0110

2.35

Use for change a specific bit.

2.36

  1. AND 1111 1011
  2. OR 0100 0100
  3. AND 0000 0000
  4. OR 1111 1111
  5. First we need a mask operation : And 0000 0100 Then times 32.
    If we add the final pattern, we always get a 0.

2.37

A1 = n AND 1000
A2 = (NOT n) AND 1000
B1 = m AND 1000
B2 = (NOT m) AND 1000
C1 = (NOT s) AND 1000
C2 = s AND 1000
RESLUT = (A1 AND B1 AND C1) OR (A2 AND B2 AND C2)

2.38

Using the symbol defined above.
RESULT = A1 AND B1 AND C1

2.39

a.3.75 = \(1.111 * 2^1\) , So the representation is 0 100 00000 1110 0000 0000 0000 0000 000
b. \(55\frac{23}{64} = 1.10111010111 * 2^5\) , So the representation is 1 100 00100 1011 1010 1110 0000 0000 0000
c. \(3.1415927 = 1.10010010000111111011010110100111111011010001100101110011 * 2^1\)
So the representation is 1 100 00000 1001 0010 0001 1111 1011 010 , not so precious
d. \(64000 = 1.1111010 * 2^{15}\) So the representation is 0 100 01110 1111 0100 0000 0000 0000 0000

2.40

  1. 2
  2. -17
  3. INF
  4. -2.25

2.41

  1. 127
  2. -149

2.42

He use the ASCII code of the number 5 and 8.
Actually ACSII code of 5 and 8 is 53 and 56. The sum of them is 109 which represents the character m in the ACSII code.

2.43

  1. Hello!
  2. hELLO!
  3. Computers!
  4. LC-2

2.44

Add, because the number in ASCII is continous. We just add some bias to get the ASCII number.

2.45

  1. 0xD1AF
  2. 0x1F
  3. 0x1
  4. 0xEDB2

2.46

  1. 1 0000
  2. 0100 0000 0001
  3. 1111 0111 0011 0001
  4. 0000 1111 0001 1110 0010 1101
  5. 1011 1100 1010 1101

2.47

  1. -16
  2. 2047
  3. 22
    d.-32768

2.48

  1. 0001 0000 0000
  2. 0110 1111
  3. 0111 0101 1011 1100 1101 0001 0101
  4. 1101 0100

2.49

  1. 0x2939
  2. 0x6E36
  3. 0x46F4
  4. 0xF1A8
  5. c and d is overflow

2.50

  1. 5468
  2. BBFD
  3. FFFF
  4. 32A3

2.51

  1. 0x644B
  2. 0x4428E800
  3. 0x48656c6c6f

2.52

rules 0x434F4D50 0x55544552
Unsigned binary 1,129,270,608 1,431,586,130
1's complement 1,129,270,608 1,431,586,130
2's complement 1,129,270,608 1,431,586,130
IEEE 754 floating point 207.302001953125 14587137097728
ASCII string COMP UTER

2.53

A B \(Q_1\) \(Q_2\)
0 0 1 0
0 1 1 1
1 0 1 1
1 1 0 1

\(Q_2\) = A OR B

2.54

X Y Z \(Q_1\) \(Q_2\)
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0

2.55

  1. \(4^{3} - 1 = 63\)
  2. \(4^n -1\)
  3. 023 + 221 = 310
  4. \(222|_4\)
  5. 11011.11
  6. 0 100 00011 1011 1100 0000 0000 0000 000
  7. I don't know what's the question means. From my point of view, depends on the number of operations. Basically there are arithmetic operations like multiply and add and logical operations like AND, OR, NOT,XOR.

2.56

0xE5 = 1110 0101
sign : 1-> -1
exp: 8 + 4 - 7 -> 5
fraction: 101 -> 1.101 = 1.5625
totally: \(1.5625 * -1 * 2^5 = 52\)(shift first maybe faster)

发表于 分类于 ， 本文字数： 2.6k 阅读时长 ≈ 4 分钟

Content

Overview of the book

  1. Encode information by binary code and relative operation
  2. Physical layer (electron to transistor) and combine them to form the more complicated device
  3. Combine these structure to von Neanamm machine (in this book: LC-3 aka. little computer 3)
  4. program in LC-3 using our own language
  5. program in LC-3 using assembly language
  6. program in LC-3 using data structure
  7. deal with the I/O in LC-3
  8. C/C++ language

Two core notion in this book

  • The notion of abstraction
  • Don't treat hardware and software sperately

Two very important ideas

  • All computer can do the same things if enough memory is given
  • Problem should be transformed for computers to solve

Exercise Solution

Made by myself. I'm not sure if it's correct.

1.1

  • All computer can do the same things if enough memory is given
  • Problem should be transformed for computers to solve

1.2

No, no matter what language you use. You can't express more than the ISA.

1.3

It's difficult to premote the precision.

1.4

maybe, yeah, It's maybe.

1.5

  1. a and x to the x-box, their output to the +-box with b.
  2. 4 +-box with ordered input w,x,y,z.then their output along with 1/4 to the x-box.
  3. One +-box with input a and b, then, their output to the x-box along with itself.

1.6

I do like him.
I do/ like him. I do what he does.
I do like/ him. I really like him and I can't lose him:(.

1.7

When there is only one airport in the city, it saves time.
When there are lots of airports and we don't want to the nearest airport. It cause negative consequences

1.8

  • I use telescope to see the man in the park.
  • I see a man in the park and he take a telescope with him.
    It doesn't meet the property of definiteness

1.9

Yes, but it should be definiteness finteness and effective computability.

1.10

Finiteness : the process should end in the finite time.
Effect computablity : all the step of the process should be computable
Definiteness : the step should be describe in the precisious way.

1.11

Finiteness:
if you reach a, then go to b, if you reach b then go to a.
Effect computablity :
she is a girl
Definiteness :
select the best one in the candidate

1.12

a.not Definiteness
b.not finiteness
c.yes
d.no maybe infinite
e.yes

1.13

The same. Subtract = add and negetive

1.14

a.120
b.C++, x86, x86-microArch1,2,3
c.still the same

1.15

More readable but less efficient

1.16

opcode, oprand, address mode

1.17

ISA define the code and it's operation. Microarchitecture implement the opearation.

1.18

One, Infinite

1.19

Problem (Sort) ->Alogrithm (Quick Sort) ->Program (QuickSort.cpp) ->ISA (x86) ->microarchitechture (Intel i7-7700H) ->Logic circuit (.....) ->Device (......)

1.20

Yes. The above layer don't need know the details of the lying layer to work.

1.21

High-level language if we buy the source code, we need compile the source code to the real program we can use. If we just buy the software, we just buy the ISA code.

1.22

The first, It's always difficult to solve the problem :(.

1.23

When you update the hardware, we don't need to change our software.The higer layer of the ISA don't need to change, because the ISA works fine at the new microarchitechture.

发表于 更新于 分类于 ， 本文字数： 436 阅读时长 ≈ 1 分钟

随机现象和统计规律性

随机事件

概率论是研究随机现象的数量规律的数学分支。

必然发生的事叫做必然事件。

必然不会发生的事叫做不可能事件。

他们被合并称为决定性现象。除了决定性现象之外，我们还有另一类现象：在基本条件不变的情况下，一系列随机试验或观察会得到不同的结果，我们称之为随机现象。这些随机的结果我们称之为随机事件。

频率稳定性

随机事件A在N次试验出现了n次，我们定义A出现的频率为：

\(F_N(A)=n/N\)

在大量试验中，频率出现明显的规律性，称之为频率稳定性。一个随机事件出现的频率在某个固定的常数周围摆动，称之为统计规律性，这两种性质说明随机事件发生的可能性大小是个固有属性，我们用概率P(A)来度量。

频率和概率

概率的一些性质：

  • \(F_N(A) >= 0\)
  • 如果\(\omega\)是必然事件，则\(F_N(\omega) = 1\)
  • 如果A和不同时发生，则\(F_N(A+B) = F_N(A) + F_N(B)\),称之为频率可加性

当试验的次数变得很大的时候，频率就会趋近于概率。