# C語言複習
## C語言標準函式庫
```c
#include <string.h>
char * strcpy(char * destination, const char * source);
char * strncpy(char *dest, const char *src, size_t count);
void * memcpy(void *dest, const void *src, size_t length);
void * memset(void *dest, int value, size_t num);
int strcmp(const char *str1, const char *str2); // return 0 if str1 == str2 else 1
int strlen(const char *str1); // not include '\0'
```
特定大小
```c
// In <stdint.h>
typedef signed integer type int8_t; // optional
typedef signed integer type int16_t; // optional
typedef signed integer type int32_t; // optional
typedef signed integer type int64_t; // optional
typedef unsigned integer type uint8_t; // optional
typedef unsigned integer type uint16_t; // optional
typedef unsigned integer type uint32_t; // optional
typedef unsigned integer type uint64_t; // optional
```
```c
// In <limits.h>
INT_MIN //整型最小值：-2147483648，即 -(231)
INT_MAX //整型最大值：+2147483647 ，即231 - 1
```
找出結構偏移位置
```c
#include <stdio.h>
#include <stddef.h>
struct containers {
char c;
int i;
};
int main(){
struct containers s;
printf("%ld", (size_t)((char *)&s.i - (char *)&s));
printf("%ld", (size_t) &((struct containers *)0)->i);
printf("%ld", offsetof(struct containers, i));
}
```
---
```c
struct __attributed__(packet){
char a;
int b;
char c;
};
```
## Bitwise operation
```c
uint32_t a = 0x00000001;
printf("%x", a); // 16 進制可用 %x 來輸出
```
### 計算絕對值不使用 branch
```c
int v;
unsigned int r;
int const mask = v >> sizeof(int) * CHAR_BIT -1;
r = (v+mask)^mask;
or
r = (v ^ mask) - mask;
```
### Max function 不使用 branch
```c
uint32_t Max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
### 返回 A or B 中的最大值:
```c
int max(int a, int b){
return (a+b+abs(a-b))/2;
}
```
### 最大公因數計算
```c
uint32_t gcd32(uint32_t u, uint32_t v)
{
if(!u || !v) return u | v;
int shift;
for (shift=0; !((u | v) & 1); shift++){
u/=2; v/=2;
}
while (!(u & 1))
u /= 2;
do{
while (!(v & 1))
v /= 2;
if (u < v){
v -= u;
}
else{
uint32_t t = u - v;
u = v;
v = t;
}
}while(v);
return u * (1 << shift);
}
```
### Detect NULL
```c
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
```
偵測是否為 0
### XOR swap
交換兩個記憶體空間的數值
```c
void xorSwap(int *x, int *y){
*x ^= *y;
*y ^= *x ;
*x ^= *y;
}
```
### counting leading zero
iteration version
```c
int clz(uint32_t x){
int n =32, c = 16;
do{
uint32_t y = x >> c;
if(y)
{n -= c; x = y;}
c>>=1;
}while (c);
return (n - x);
}
```
binary search technique :
```c
int clz(uint32_t x){
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF){ n += 16; x <<= 16; }
if (x <= 0x00FFFFFF){ n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF){ n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF){ n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF){ n += 1; x <<= 1; }
return n;
}
```
byte-shift version :
```c
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 1;
if ((x >> 16) == 0) { n += 16; x <<=16; }
if ((x >> 24) == 0) { n += 8; x <<= 8; }
if ((x >> 28) == 0) { n += 4; x <<= 4; }
if ((x >> 30) == 0) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
### Integer bits inverse
for loop 形式 :
```c
int func(unsigned int x) {
int val = 0; int i = 0;
for (i = 0; i < 32; i++){
val = (val << 1) | (x & 0x1);
x >>=1;
}
return val;
}
```
[bit-wise 形式](https://stackoverflow.com/questions/21511533/reverse-integer-bitwise-without-using-loop) :
```c
new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
```
### quicksort
```c
#define SWAP(a,b) \
do{ \
typeof(*a) _temp = *(a); \
*(a) = *(b); \
*(b) = _temp; \
}while(0)
// void quicksort(int *arr,int first,int last){
// int pivot = *(arr + first);
// int front = first + 1;
// int behind = last;
// if(first >=last)
// return;
// while(front <= behind){
// if(*(arr + front) <= pivot && front <= last)
// front++;
// if(*(arr + behind) > pivot && behind > first)
// behind--;
// if(front < behind)
// SWAP((arr + front),(arr + behind));
// }
// SWAP((arr + first),(arr + behind));
// quicksort(arr, first, behind-1);
// quicksort(arr, behind+1, last);
// }
void quicksort(int *arr, int *fr, int *be){
if(fr >= be)
return;
int *front = fr + 1;
int *behind = be;
int *pivot = fr;
while(front < behind){
while (*front < *pivot && front < be)
{
front++;
}
while(*behind > *pivot && behind >= pivot + 1)
behind--;
if (front < behind)
SWAP(front,behind);
}
SWAP(pivot,behind);
quicksort(arr,fr,behind - 1);
quicksort(arr,behind + 1,be);
}
```
### heapsort
## C 語言觀念
### 函式指標
函式透過宣告宣告成函式指標:
```c
void (*fptr)(type argv1, type argv2) = &func;
//or
void (*fptr)(type argv1, type argv2) = func;
fptr(argv1, argv2);
//or
(*fptr)(argv1, argv2);
```
常用地方:
* 函式 sort 時傳入判斷準位
* multithread 傳函式進入建立 thread 的 API 中
* callback function
### 指標判讀 & const
* a)一個整型數 (An integer)
* b)一個指向整數的指標 (A pointer to an integer)
* c)一個指向指標的指標，它指向的指標是指向一個整型數 (A pointer to a pointer to an integer)
* d)一個有10個整數型的陣列 (An array of 10 integers)
* e)一個有10個指標的陣列，該指標是指向一個整數型的(An array of 10 pointers to integers)
* f)一個指向有10個整數型陣列的指標 (A pointer to an array of 10 integers)
* g)一個指向函數的指標，該函數有一個整數型參數並返回一個整數 (A pointer to a function that takes an integer as an argument and returns an integer)
* h)一個有10個指標的陣列，該指標指向一個函數，該函數有一個整數型參數並返回一個整數 (An array of ten pointers to functions that take an integer argument and
return an integer)
:::info
陣列存取權限高於 * 位置存取， 因此解讀 (e) 為陣列元素有 10 個， 每個元素是一個整數指標。
而 (f) 可解讀為有一個指標，這個指標為有 10 元素的整數陣列。
:::
```c
int a;
int *ptr;
int **ptr;
int array[10];
int *array[10]; // e
int (*ptr)[10]; // f
int (*ptr)(int);
int (*ptr[10])(int);
```
```c
const int *foo; // 一個pointer 指向 const int 變數
int const *foo; // 同上
int * const foo; // 一個 const pointer 指向 int 變數
int const * const foo; //兩個都是 const
```
### inline 函式
inline 函式像巨集依樣將函式展開編譯，加速執行速度。
inline 與 #define 差別:
* inline 只對參數執行一次計算
* inline 參數型別會被檢查並做必要的型別轉換
* Macro 定義通常不使用於 複雜的函數
* 用 inline 後編譯器不一定會實作，僅為建議
### Struct 結構
簡單的定義結構:
```c
struct students{
int id;
char name[20];
int chinese;
int english;
int math;
int social;
int science;
};
//使用時:
struct students someone;
```
定義結構的同時宣告變數(全域變數共用一實體，可直接使用):
```c
struct students{
int id;
char name[20];
int chinese;
int english;
int math;
int social;
int science;
}someone;
//使用時:
someone.chinese = 10;
```
定義 struct 也宣告 struct 別名:
```c
struct students{
int id;
char name[20];
int chinese;
int english;
int math;
int social;
int science;
}
typedef struct students Student;
//使用時:
Student b_class;
```
定義 struct 時直接取別名:
```c
typedef struct{
int id;
char name[20];
int chinese;
int english;
int math;
int social;
int science;
}Student;
//使用時:
Student b_class;
```
### Union
聯合在同一時間同僅能儲存其中一個屬性，故以下程式會引發錯誤:
```c
#include <assert.h>
typedef union sample_t sample_t;
union sample_t {
float f;
int i;
char ch;
};
int main(){
sample_t s;
s.i = 3;
assert(s.i == 3);
s.f = 5.0;
assert(s.i == 3); // Error!
return 0;
}
```
* union 中的大小由最大的成員的大小決定
* 對某一個成員賦值，會覆蓋其他成員的值(若所佔字節不同，僅會覆蓋對應字節)
* union 的存放順序是全部成員都從低位置開始存放的。
### GNU extension 的 typeof
typeof 允許我們傳入一個變數，代表的會是該變數的型態，
typeof 通常會用在定義巨集上，因為巨集裡無法得知參數型態
```c
#define max(a, b) \
{(typeof(a) _a = a; \
typeof(b) _b = b; \
_a > _b ? _a : _b;) \
}
```
看以下程式碼:
```c
#define max(a, b) ({ \
typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; \
})
```
[來源](https://hackmd.io/@sysprog/linux-macro-minmax)，提到一樣是 GNU 的 extension ({}) 使得回傳的是最後一個敘述 ```_a > _b ? _a : _b;``` 的數值。
### Arraysize() 的錯誤
參考以下程式碼:
```c
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
int main(void)
{
int a[10];
int *a_ptr = a;
printf("%d\n", ARRAY_SIZE(a));
printf("%d\n", ARRAY_SIZE(a_ptr));
return 0;
}
```
若傳入的是 a ，則 arraysize = 10 正確。但若傳遞的是 a_pt 這個 pointer ，則會算出這個 pointer 的大小除以 *(pointer) 的型態大小，錯誤!
[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FS1maxCXMl)
[面試考古參考](https://hackmd.io/aXZ0ZLqoQVej8Le7MI6k3w?view)
https://www.dcard.tw/f/tech_job/p/239480651
Sign in with Wallet
Connect another wallet