# 2024q1 Homework1 (lab0)
contributed by < [Niclas3](https://github.com/Niclas3) >
## 开发环境
```shell
$ gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-1235U
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 4
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 4992.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detect avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req hfi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize arch_lbr ibt flush_l1d arch_capabilities
Virtualization: VT-x
L1d cache: 352 KiB (10 instances)
L1i cache: 576 KiB (10 instances)
L2 cache: 6.5 MiB (4 instances)
L3 cache: 12 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
```
## 读文章所得
### [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)
#### 从问题开始
第二次读文章时候，我带了一个问题。“为什么计算机编码使用的是补码（也就是二补数）？”
我尝试回答一下这个问题。要回答上述问题，首先要回答，
:::info
1. 编码是什么？
2. 为什么计算机需要编码？
3. 计算机编码是在给什么编码？
:::
回答第一个问题，[编码](https://dict.concised.moe.edu.tw/dictView.jsp?ID=1549)是资讯从一种形式或格式转换成另一种形式的过程。知道了编码的含义之后第二和第三个问题就迎刃而解，计算机需要编码是因为计算机只能用二进制处理数字而现实世界和计算机使用的“资讯形式”不同，我们需要用编码来把现实世界的“数字”形式映射到计算机可以处理“数字”形式。
回答完这三个问题，我就知道给计算机编码是在给现实中的“数字”找到一种二进制形式可以表达的形式。这种形式常见的如阿拉伯数字，罗马数字等编码方式。
文章的第〇部分展示了一种凭借直觉的编码设计，即符号与值的形式。
这引出了下一个问题。
:::info
4. 计算机的编码需要什么性质？
:::
符号与值的形式由于符号位不参与运算和```0```有2种表示方式，加减法分别需要进位和借位，这几个主要原因导致电路复杂。
由于这些原因，我们就需要一个既能表达符号又能参与运算，最好有唯一单位元的表示法。
#### 一补数
我尝试从问题入手能不能倒推出反码出现的原因。我们由问题4得出，如果想要加强符号与值这种形式的编码，首先需要处理符号位不参与运算的问题。直接用文章中的例子```-43```($43_{10} = 00101011_{2}$)
反码形式是 $11010100_2$
```
11010100
+ 00101011
---------------
11111111
```
这样编码首先的把符号位不参与运算处理了。
我们再看单位元有唯一表示法吗？上述 `-43+43 = 0` 零的表示为 $11111111_2$ 我尝试使用 `43-43 = 0` 零的表示为 $00000000_2$
可见作为单位元的数字零并没有统一表示。
文章中着墨较多的x的补数的性质，事实上替代了减法的借位。之前的进位也变成了循环进位。
反码为了符号可以参加运算，增加了“循环进位”(end-around carry)确保数值正确。直觉来看，循环进位的引入和补数的性质有关。
::: warning
这里反码的循环进位的引用，我没有想到特别好的解释，如果感兴趣，希望可以跟我讨论谢谢。
:::
回顾一下怎么利用补数节省运算资源
以原文的例子
```
253 [x, minuend]
- 176 [y, the subtrahend]
---------------------------
746 [nines' complement of x = 999 - x]
+ 176
---------------------------
922 [999 - x + y]
077 = 999 - (999 - x + y) = x - y
```
::: success
首先取得被减数(minuend) `253`的9补数。把`253-176`转化为它的九补数，即`746`，加上减数(subtrahend)`176`的形式。这里把减法转化为加法。得到的数值再取一次9补数就可以得到正确的答案。
使用这种技巧就可以删除减法的电路
:::
整理一下，编码变成反码后解决了
1. 符号位不参与运算。
2. 减法被补数运算的加法替代
没有解决的是
1. 单位元 零依然有两个表示方式
#### 二补数
我们依然尝试从问题出发，试着解决反码所没有解决的问题，单位元编码不唯一问题。
二补数的出现显得其实理所当然。自然的照着[循环群](https://en.wikipedia.org/wiki/Cyclic_group)构造出了补码。这样出现的编码显然的解决了单位元编码不唯一的问题。
#### 总结
编码是一种对应关系。这篇文章全片的编码都是为了寻找一种可以映射整数域的以二进制数字为基础的编码方式。目前寻找到工程上最广泛使用的解是二补数。
二补数，在数的表达上天然的呈现了2种情况。二补数形式上可以分为给负数编码和不给负数编码。给负数编码的部分一半编码空间冗余给已经被编码的正数
----
### [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
本文开篇提到由于思维模式不同导致程序设计时有完全不同的"taste"，其以对于[Linked lists](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/linked%20lists.html)中元素删除的函数作为例子，给出了2个例子，我分别命名为模式1与模式2。
模式1：
```c
void remove_list_node(List *list, Node *target)
{
Node *prev = NULL;
Node *current = list->head;
// Walk the list
while (current != target) {
prev = current;
current = current->next;
}
// Remove the target by updating the head or the previous node.
if (!prev)
list->head = target->next;
else
prev->next = target->next;
}
```
模式2：
```c
void remove_list_node(List *list, Node *target)
{
// The "indirect" pointer points to the *address*
// of the thing we'll update.
Node **indirect = &list->head;
// Walk the list, looking for the thing that
// points to the node we want to remove.
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
```
直观来编写函数```void remove_list_node(List *list, Node *target)```着眼点第一时间会在列表的节点上，通过走访列表中各个节点找到相应的节点，删除，连接前后节点。这样势必会需要一个指针保存上一个走访的节点的地址，得到的代码就和模式1中代码相同。这样就出现了分支情况，头节点并没有上一个节点自然头节点需要认为添加一个```NULL```来特殊表示。
以目标函数抽象出的操作物是形如一个节点附带上一个节点指针的构造，来观察模式2的代码。模式2引入一个指针的指针```indirect```以指向头节点的地址。这样就让每一个节点都凑出了“一个节点附带上一个节点指针的构造”
模式1中，头节点的上一个节点是NULL。 模式2中,头节点的上一个节点是```indirect```（只是形式相同）
indirect是上一个节点的next成员的指针的指针。对indirect解引用等效上一个节点的next成员解引用（是一个指针）这个指针指向下一个节点（即本节点）。
## 作题思路
### 考慮以下程式碼: char s[64]; 試問 s == &s 是否成立？
:::warning
全文佐以[标准](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
:::
#### 拆解问题
1. 如下程序片段是什么？
```c
char s[64]; // 它是一个Array declarators(6.7.5.2)
```
2. `s == &s` 中`s`、`==`和`&s`分别是什么？
根据 6.3.2.1 `s`是被转化成 `pointer to type`这个指针指向的是数组第一元素而且`s`并不是lvalue
简单来说`&s`是指向s数组第一个元素的**指针**。
> Except when it is the operand of the sizeof operator or the unary & operator, or is a
> string literal used to initialize an array, an expression that has type ‘‘array of type’’ is
> converted to an expression with type ‘‘pointer to type’’ that points to the initial element of
> the array object and is not an lvalue. If the array object has register storage class, the
> behavior is undefined.
根据规格书（C99 6.3.2.1）s作为一个array type,这种情况会被转换成“pointer to type”，查看规格书（C99 6.2.5-20)一个“array type”的类型是和它其中的元素类型一致（并没有特别说明是和第一个元素一致）这样s它的类型就是一个char*。右侧依据（C99 6.5.3.2）"Otherwise, the result is a pointer to the object or function designated by its operand."这一句作为证据右侧的type是a pointer to the object，这里的object是array object，右侧的类型则为char(*)[64]。最后依据（C99 6.5.9）equality operator 左右两侧都是指针的情况下，指针指向的都是元素的第一个元素的地址他们指向同一个object
Sign in with Wallet
Connect another wallet