---
# System prepended metadata

title: CSAPP 閱讀筆記
tags: [linux2022]

---

# CSAPP 閱讀筆記

###### tags: `linux2022`

## Logic Operation
### Contrast to Bit-Level Operators
* Logic Operations: &&, ||, !
	* View 0 as "False"
	* ==Anything nonzero as "True"==
	* Always return 0 or 1
	* ==Early termination==
* Examples
	* !0x41 -> 0x00
	* !0x00 -> 0x01
	* !!0x41 -> 0x01
	* 0x69 && 0x55 -> 0x01
	* 0x69 || 0x55 -> 0x01
	* p && *p (avoid null pointer access)
	
### Shift operations
* Undefined Behavior
	* Shift amount < 0 or >= word size

![](https://i.imgur.com/F6PiHLn.png)

## Integers
![](https://i.imgur.com/fBWkS57.png)
![](https://i.imgur.com/RSGWyLV.png)
![](https://i.imgur.com/UExzWYp.png)

```c
#include <limits.h>
#include <stdio.h>

int main(){

    long a = LONG_MAX;
    long b = 1;
    long c = a + b;
    printf("%ld\n", c); 
        
    return 0;      
}
```

```shell
$ ./num 
-9223372036854775808
```

![](https://i.imgur.com/KiLfGmk.png)

![](https://i.imgur.com/QGVM2ph.png)

## Signed vs. Unsigned in C

![](https://i.imgur.com/7sgDdyy.png)

* casting 要很小心，從 unsigned 轉成 signed ，原本應該是很大的值，被轉換成小的值
* 在一個表示式當中，包含了 signed value 與 unsigned value ， signed value 會被隱性轉換成 unsigned value

在 [你所不知道的 C 語言: bitwise 操作] (https://hackmd.io/@sysprog/c-bitwise) 提到下面這個會產生無窮迴圈的例子

當 i = 0 時，i - 1 的結果會是 unsigned 的，因此 0 - 1 本該是 -1 但對於 unsigned 而言，會是最大的數

```c
int n = 10; 
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
    printf("i: 0x%x\n",i);
```

> The result of [sizeof](https://en.wikipedia.org/wiki/Sizeof) has an unsigned integer type that is usually denoted by size_t. 

以下 unsigned 的最後會標上 U

![](https://i.imgur.com/HU3MMH3.png)

![](https://i.imgur.com/yUtJrZU.png)

## Extension and Truncation
![](https://i.imgur.com/k27MXUH.png)

![](https://i.imgur.com/jXcsi2W.png)

![](https://i.imgur.com/pUnodGp.png)

![](https://i.imgur.com/jHAqZ7P.png)

## Addition, negation, multiplication, shifting

![](https://i.imgur.com/FCvkIGe.png)

![](https://i.imgur.com/Hy1PZNi.png)

![](https://i.imgur.com/PuGcpjw.png)

![](https://i.imgur.com/HIUHNhV.png)

![](https://i.imgur.com/juUnVyL.png)

![](https://i.imgur.com/0Cn9Ynt.png)

![](https://i.imgur.com/nDbaC1S.png)

![](https://i.imgur.com/39QoWA3.png)

![](https://i.imgur.com/OZiO1Hs.png)

![](https://i.imgur.com/TC14Qai.png)

## Dividing by Powers of Two
根據 [CS:APP3e](http://csapp.cs.cmu.edu/)

Integer division on most machines is even slower than integer multiplication requiring 30 or more clock cycles. 

The two different shifts—logical and arithmetic—serve this purpose for unsigned and two’s-complement numbers, respectively.

![](https://i.imgur.com/hbXV8T0.png)


對於有號數的負數進行除法，會有錯誤情形產生，因為正確版本是希望 [$x$ / $2^k$] 是 round toward 0 的

![](https://i.imgur.com/zUHubP5.png)

![](https://i.imgur.com/yZ8WUlV.png)

![](https://i.imgur.com/COVb77Y.png)

* tricky 的點就是 arithmetic right shift on a two’s-complement number (negative number)
* a logical right shift by k to an unsigned number 是沒有問題的

```c
#include <stdio.h>     

int main(){

    long a = -10;
    printf("a = %ld\n", a); 
    printf("Wrong case : a / 8 = %ld\n", a >> 3); 
    printf("Correct case : a / 8 = %ld\n", (a + (1<<3)-1) >> 3); 
    // (x < 0 ? x + (1 << k) - 1 : x) >> k
    return 0;
}
```

```c
./divide 
a = -10
Wrong case : a / 8 = -2
Correct case : a / 8 = -1
```

Let $x$ be two's complement integer 
$x = [x_{w-1}, x_{w-2},...,x_0]$
and k be in the range $0\leq k<w$

Let $x_1$ be the two's complement number represented by the $w-k$ bits
$x_1 = [x_{w-1}, x_{w-2},...,x_k]$
and $x_2$ be the unsigned number represented by the low order $k$ bits
$x_2 = [x_{k-1}, x_{k-2},...,x_0]$

Then we have
$x = 2^kx_1 + x_2$, and $0\leq x_2<2^k$, giving $x_1 = [\dfrac{x}{2^k}]$
the shifted bit vector is the two’s-complement representation of $[\dfrac{x}{2^k}]$, which is $[x_{w-1},..., x_{w-1}, x_{w-2},...,x_k]$

* For $x \geq 0$, or when on rounding is required ($x_2 = 0$), this shifted result is the desired value.
* For $x < 0$ and $y > 0$, the result of integer division should be $[x/y]$, where for any real number $a$, $[a]$ is defined to be the unique interger $a^{'}$ such that $a^{'} - 1 < a \leq a^{'}$. That is, integer division should round negative results upward toward zero.

$[x/y] = [(x+y-1)/y]$ for integers $x$ and $y$ such that $y > 0$. As examples, $x = -30$ and $y = 4$, we have $x + y - 1 = -27$, and $[-30/4] = [-27/4] = -7$. To see that this relation holds in general, suppose that $x = ky + r$, where $0\leq r < y$, giving $(x+y-1)/y = k + [(r+y-1)/y]$.

* When $r = 0$, $[(r+y-1)/y] = 0$
* When $r > 0$, $[(r+y-1)/y] = 1$

This analysis shows that for a two’s-complement machine using arithmetic right shifts, the C expression

```c
(x<0 ? x+(1<<k)-1 : x) >> k
```

![](https://i.imgur.com/j2V4VCU.png)

![](https://i.imgur.com/H75Ae3M.png)

![](https://i.imgur.com/YpTEvt7.png)

## Representations in memory, pointers, strings

![](https://i.imgur.com/6AHpUpY.png)

![](https://i.imgur.com/rjRGzGI.png)

![](https://i.imgur.com/G4NUulN.png)

![](https://i.imgur.com/K7qcowf.png)

![](https://i.imgur.com/K06jI8h.png)

![](https://i.imgur.com/FQlaadZ.png)

```clike=
#include <stdio.h>                               
	
typedef unsigned char *pointer;
void show_bytes(pointer start, size_t len){
    size_t i;
    for (i = 0; i < len; i++)
        printf("%p\t0x%.2x\n",start+i, start[i]);
    printf("\n");
}

int main(){
    int a = 15213;
    printf("int a = 15213;\n");
    show_bytes((pointer) &a, sizeof(int));
    return 0;
}
```

```shell
./show_byte 
int a = 15213;
0x7fffeaa58f84	0x6d
0x7fffeaa58f85	0x3b
0x7fffeaa58f86	0x00
0x7fffeaa58f87	0x00
```

![](https://i.imgur.com/sydzyfc.png)

對於 string 來說 : Byte ordering 不是問題

![](https://i.imgur.com/3cTLxUm.png)
