# 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


## Integers

#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;      
}

$ ./num 
-9223372036854775808



## Signed vs. Unsigned in C


* 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 而言，會是最大的數

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



## Extension and Truncation




## Addition, negation, multiplication, shifting











## 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.


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




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

#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;
}

./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

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




## Representations in memory, pointers, strings







#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;
}

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


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