HackMD
面試考古
相關連結:
作業系統及考古、計算機結構及考古、linux kernel學習筆記、STM32學習筆記
Predict the output of below programs.
1.
#include<stdio.h>
int main() {
int n;
for(n = 7; n!=0; n--)
printf("n = %d", n--);
getchar();
return 0;
}
解答
上述輸出為:infinite loop因為在迴圈迭代時，n--不會等於0
2.
#include<stdio.h>
int main()
{
printf("%x", -1<<1);// 2's complement -1 = 0xfffc for 16 bits machine
getchar();
return 0;
}
解答
-1為1的二補數在16bits machine中為 0xfffc，left shift後為0xfffe，32bits machine為 0xfffffffe
3.
# include <stdio.h>
# define scanf "%s Geeks For Geeks "
main()
{
printf(scanf, scanf);
getchar();
return 0;
}
解答
preprocessor的展開，會直接印出 %s Geeks For Geeks
4-1.
#include <stdlib.h>
#include <stdio.h>
enum {false, true};
int main()
{
int i = 1;
do
{
printf("%d\n", i);
i++;
if (i < 15)
continue;
} while (false);
getchar();
return 0;
}
4-2.
#include <stdlib.h>
#include <stdio.h>
enum {false, true};
int main()
{
int i = 1;
do
{
printf("%d\n", i);
i++;
if (i < 15)
break;
} while (true);
getchar();
return 0;
}
解答
1.continue會直接進入do-while loop的檢查條件中，但因為while永遠都是false導致迴圈不會繼續執行下去，故只會印出1。
2.break會直接導致跳出迴圈不會執行do-while loop的檢查條件，故也只會印出1
5.
#include <stdio.h>
char *getString() {
char *str = "Nice test for strings";
return str;
}
int main() {
printf("%s", getString());
getchar();
return 0;
}
解答
string constant(字串字面常數)會被儲存於data section中的Read-Only data section中而不是儲存在stack中(函數呼叫完會自動釋放記憶體空間)，所以*str這個指標可以正確指向記憶體位址得到預期的輸出。
6.
#include<stdio.h>
char *getString()
{
char str[] = "Will I be printed?"; //str[] => *(str+0) 自動轉型成指標
return str;
}
int main()
{
printf("%s", getString());
getchar();
}
解答
str為陣列也是getString這個function的區域變數被儲存於stack裡，故當函式執行後return的pointer str因stack會自動釋放已執行完函式的記憶體空間會讓str成為dangling pointer，且在printf裡呼叫dangling pointer會導致undefined behavior。
dangling pointer:
A pointer pointing to a memory location that has been deleted (or freed) is called a dangling pointer. Such a situation can lead to unexpected behavior in the program and also serve as a source of bugs in C programs.
There are three different ways where a pointer acts as a dangling pointer:
7.
#include<stdio.h>
int main()
{
static int i=5;
if(--i){
main();
printf("%d ",i);
}
}
解答
有初始化的static變數為放入data section裡，在函數進入至main();後開始遞迴呼叫每次呼叫都會建議一個專屬於當時遞迴的stack frame直至其遞迴條件結束，本程式碼總共會遞迴四次，當if(--i)在第四次遞迴會從true->false，進而執行printf然後從第四次遞迴依序印出輸出至第一次遞迴。
8.
#include<stdio.h>
int main()
{
static int var = 5;
printf("%d ",var--);
if(var)
main();
}
解答
output:54321，先初始化static var，然後先print之後再進入遞迴，直至if statement不成立。
9.
#include<stdio.h>
int main()
{
int x;
printf("%d",scanf("%d",&x));
/* Suppose that input value given
for above scanf is 20 */
return 1;
}
解答
scanf的return value不是輸入本身，而是它成功讀取並轉換的輸入項目數量且printf("%d",scanf("%d",&x))會印出scanf的return value而不是其輸入數值。
10.
# include <stdio.h>
int main()
{
int i=0;
for(i=0; i<20; i++)
{
switch(i)
{
case 0:
i+=5;
case 1:
i+=2;
case 5:
i+=5;
default:
i+=4;
break;
}
printf("%d ", i);
}
getchar();
return 0;
}
解答
進入switch敘述時，因為沒有break所以會從case0一路走到case5，數值變化為:5(0)->7(1)->12(5)->16(default)，上述的原理為casefall thorugh，
第二次迭代為17->21(因為沒有上述case直接執行default)。
11.
#include <stdio.h>
int main()
{
printf("%p", main);
getchar();
return 0;
}
解答
在C語言中，函式名稱也是函式指示符會被complier認為是pointer to function，在compiler處理會隱性轉型為 address of pointer to function(也就是函式本身的位址)。
function designator
12.
#include <stdio.h>
int main()
{
printf("\new_c_question\by");
printf("\rgeeksforgeeks");
getchar();
return 0;
}
解答
/n、/r、\b都是printf跳脫字元故第一個output為:ew_c qusetiony，第二個為:geekforgeeks
13.
# include<stdio.h>
# include<stdlib.h>
void fun(int *a)
{
a = (int*)malloc(sizeof(int));
}
int main()
{
int *p;
fun(p);
*p = 6;
printf("%d\n",*p);
getchar();
return(0);
}
解答
上述程式碼不會有預期的output出來，在C中函式傳遞都是call by value也就是將原本變數的副本的值給予至被呼叫的函式中，當在main函式dereference pointer時其實只是改變指標指向的address位址，如果要達到更改pointer的位址應該使用pointer to pointer來去更改才能得到預期的結果，故上述執行結果在dereference時會有不如預期的結果指向的記憶體位址為未知使用undefined behavior且有可能會有segmentation fault
參考閱讀
How can I allocate memory and return it (via a pointer-parameter) to the calling function?
14.
#include <stdio.h>
int main()
{
int i;
i = 1, 2, 3;
printf("i = %d\n", i);
getchar();
return 0;
}
解答
輸出為:1，因為在complie過程中會被解釋成 (i = 1),2,3 ，這個是因為 assign operator 的運算順序大於 comma operator，故會有上面的輸出。
15.
#include <stdio.h>
int main()
{
int first = 50, second = 60, third;
third = first /* Will this comment work? */ + second;
printf("%d /* And this? */ \n", third);
getchar();
return 0;
}
解答
110，/**/會被complier略過不去進行編譯。
16.
#include‹stdio.h›
int main()
{
struct site
{
char name[] = "GeeksforGeeks";
int no_of_pages = 200;
};
struct site *ptr;
printf("%d",ptr->no_of_pages);
printf("%s",ptr->name);
getchar();
return 0;
}
解答
struct是一種資料型別宣告，代表它是創建一個新的資料型別而不能在此進行初始化，進行資料型別宣告時並進行初始化會導致complier報錯，初始化應該是要在定義結構變數後再進行初始化，可以採用逐個初始化或是用列表初始化。
17.
int main()
{
char a[2][3][3] = {'g','e','e','k','s','f','o',
'r','g','e','e','k','s'};
printf("%s ", **a);
getchar();
return 0;
}
解答
三維陣列有18個element的位址，上述程式碼初始化了其中13個，在char型別尚未被初始化的位址裡面會初始化成為/0，**a為指向陣列起始位址的指標。
18.
int main()
{
char str[]= "geeks\nforgeeks";
char *ptr1, *ptr2;
ptr1 = &str[3];
ptr2 = str + 5;
printf("%c", ++*str - --*ptr1 + *ptr2 + 2);
printf("%s", str);
getchar();
return 0;
}
解答
ptr1指向陣列第四個元素的位址，ptr2指向陣列第六個元素的位址，在這邊主要是要注意printf("%c", ++*str - --*ptr1 + *ptr2 + 2);，上述的pointer arithmetic都是透過ASCII encode去進行運算故 ++*str為g->k(g+1=k)， --*ptr1為 k->j(k-1=j)、 *ptr2 為 s、 ++*str - --*ptr1 + *ptr2 + 2 為 s(ASCII:115)故第一個printf會將字串更改為heejs\ngeeks第二個printf會印出heejs\ngeeks。
19.
#include <stdio.h>
int fun(int n)
{
int i, j, sum = 0;
for(i = 1;i<=n;i++)
for(j=i;j<=i;j++)
sum=sum+j;
return(sum);
}
int main()
{
printf("%d", fun(15));
getchar();
return 0;
}
解答
單純就是迴圈條件判斷和函式的理解，fun這個函式會有下列結果n(n+1)/2上述輸出為120
20.
#include <stdio.h>
int main()
{
int c = 5, no = 1000;
do {
no /= c;
} while(c--);
printf ("%d\n", no);
return 0;
}
解答
上述程式碼會這樣執行do-while loop會先做再檢查while的成立條件，
(1000/5 = 200)->(200/4=50)->(50/3 = 16(round off))->(16/2 = 8)->(8/1 = 8)
->(8/0 -> complier error)
因為有除以0所以compiler會報錯
21.
int main()
{
while(1){
if(printf("%d",printf("%d")))
break;
else
continue;
}
return 0;
}
解答
答案無法被預測，當 printf 函數使用格式化字串，但缺少對應的參數時，為undefined behavior這種情況下printf會在register或者stack隨便找一個值代入，外層printf獲取內層printf的返回值並打印出來，然後進入break讓看似無窮迴圈的地方變成只打印一次。
printf 函數返回的是 成功印出的字元數量。 即使印出的是垃圾值，printf 仍然會返回印出的字元數量，只要沒有發生錯誤。
22.
int main()
{
unsigned int i=10;
while(i-- >= 0)
printf("%u ",i);
return 0;
}
解答
在上述程式碼中會被執行打印為9->8->7->6->5->4->3->2->1->0(while(0)仍成立)->(-1)(原本是)但因為unsigned int沒有負數會導致underflow至unsigned int的最大值開始打印。
23.
int main()
{
int x, y = 2, z, a;
if (x = y % 2)
z = 2;
a = 2;
printf("%d %d ", z, x);
return 0;
}
解答
在程式執行過程中未被初始化的變數會被自動初始化為0，所以 x、z、a 一開始會初始化為 0，後續branch判斷也不成立所以printf打印出值為0 0。
24.
int main()
{
int a[10];
printf("%d",*a+1-*a+3);
return 0;
}
解答
因為dereference的運算符相較+-來說優先順序更高，所以應該會被更改成 (*a)+1 -(*a)+3且*a會被隱性轉型成指向陣列第一個元素的ptr但因為不知道陣列第一個元素為何?故用x來代替上述運算式會被轉換成(*a)+1 -(*a)+3->x+1-x+3->4，所以輸出為4
25.
#define prod(a,b) a*b
int main()
{
int x=3,y=4;
printf("%d",prod(x+2,y-1));
return 0;
}
解答
預期程式的結果會是5 * 3 = 15，但因為巨集會直接展開成3+2*4-1=10，這是巨集的副作用，如果要讓程式輸出符合預期應該會在marco上寫成 #define prod(a,b) (a)* (b) 以避免上述不符合預期的結果。
26.
int main()
{
unsigned int i=65000;
while ( i++ != 0 );
printf("%d",i);
return 0;
}
解答
迴圈進入點為 i = 65000；while loop 判斷會一直increment然後直到 while overflow 至 0時while loop會跳出並且 i 會 increment 為 1
27.
int main()
{
int i=0;
while ( +(+i--) != 0)
i-=i++;
printf("%d",i);
return 0;
}
解答
while loop 中的判斷式可以視為 +(+(i--)) != 0
28.
int main()
{
float f=5,g=10;
enum{i=10,j=20,k=50};
printf("%d\n",++k);
printf("%f\n",f<<2);
printf("%lf\n",f%g);
printf("%lf\n",fmod(f,g));
return 0;
}
解答
第一個錯誤是因為在第一個printf中嘗試更改k的值，k是enum，其實就類似整數常數，其值不容許更改，
第二個錯誤為f<<2，因為f為floating number，在c語言中<<運算子限用於int型別表示的number，故不符合語法設定，第三個錯誤為在c語言中%僅使用於int但f g為float故不符合語法設定
29.
int main()
{
int i=10;
void pascal f(int,int,int);
f(i++, i++, i++);
printf(" %d",i);
return 0;
}
void pascal f(integer :i,integer:j,integer :k)
{
write(i,j,k);
}
解答
在c語言中沒辦法使用pascal語言的語法及函數，因為可能現代c語言編譯器不支援此功能
30.
void pascal f(int i,int j,int k)
{
printf("%d %d %d",i, j, k);
}
void cdecl f(int i,int j,int k)
{
printf("%d %d %d",i, j, k);
}
main()
{
int i=10;
f(i++,i++,i++);
printf(" %d\n",i);
i=10;
f(i++,i++,i++);
printf(" %d",i);
}
解答
標準c語言並無pascal和cdecl兩個函數，並且兩個函數為分別為由左至右遞增及有右至左遞增，兩個函式對於相同變數進行重複操作且沒有明確的順序點導致結果不重合，這會導致未定義行為，且函數於定義時c語言不允同名同參數的overloading。
31.
int main()
{
int i = 0;
while (i <= 4)
{
printf("%d", i);
if (i > 3)
goto inside_foo;
i++;
}
getchar();
return 0;
}
void foo()
{
inside_foo:
printf("PP");
}
解答
呼叫的inside_foo這個label在這段程式碼並main函式中沒有定義，因為label的scope於函式中，故不能在其他函式中呼叫inside_foo這個label
32.
#define a 10
int main()
{
#define a 50
printf("%d",a);
getchar();
return 0;
}
#define a 10
int main()
{
printf("%d ",a);
#define a 50
printf("%d ",a);
getchar();
return 0;
}
解答
在兩段程式碼第一段程式碼，僅會印出50，但第二段會印出10、50。這是因為重新定義preprocessor時編譯器不會發出警告且會以最新數值做為基礎進行後續操作
33.
int main()
{
char str[] = "geeksforgeeks";
char *s1 = str, *s2 = str;
int i;
for(i = 0; i < 7; i++)
{
printf(" %c ", *str);
++s1;
}
for(i = 0; i < 6; i++)
{
printf(" %c ", *s2);
++s2;
}
getchar();
return 0;
}
解答
在上述程式碼兩種字元指標皆指向字元陣列str的第一個元素也就是g，在第一個loop中，printf函式會dereference str這個陣列取得其記憶體位址，但後續片段為++s1指s1在increment，故迴圈結束仍是指向str第一個元素會印出 ggggggg，
第二個迴圈derefernece s2並且increment by s2，所以會依序印出 geeksf。
34.
int main()
{
char str[] = "geeksforgeeks";
int i;
for(i=0; str[i]; i++)
printf("\n%c%c%c%c", str[i], *(str+i), *(i+str), i[str]);
getchar();
return 0;
}
解答
上述其實都是 *(arr+i)的一種形式 對於c語言中arr[i]其實就是*(arr+i)的語法糖故會印出四次gggg eeee eeee以此類推至印出整個陣列。
35.
int main()
{
char *p;
printf("%d %d ", sizeof(*p), sizeof(p));
getchar();
return 0;
}
解答
計算指標*p為 1 (char pointer)，計算指標變數p在常見編譯器實作為 4 or 8。
36.
#include<stdio.h>
int main()
{
int x = 5, p = 10;
printf("%*d", x, p);
getchar();
return 0;
}
解答
%*d為printf函式標準輸出的字元，會規定打印字串最小寬度以這裡為例為5故其值會是 10 (10只有兩個字元剩餘為空白字元)
37.
int main()
{
char arr[] = "geeksforgeeks";
char *ptr = arr;
while(*ptr != '\0')
++*ptr++;
printf("%s %s", arr, ptr);
getchar();
return 0;
}
解答
在c語言中postfix(left to right)優先順序大於prefix和dereference(right to left)故其程式碼行為會是
ptr++->*(ptr++)->++(*(ptr)++)故行為是ASCII值加1並指向下一個字元直至terminal character
38.
int main()
{
signed char i=0;
for(; i >= 0; i++);
printf("%d\n", i);
getchar();
return 0;
}
解答
因為是signed int故其範圍會是在-128~127以4 byte為編譯器實作定義的話，故迴圈結束後印出值為-128
39.
#include <stdio.h>
void fun(const char **p) { }
int main(int argc, char **argv)
{
fun(argv);
getchar();
return 0;
}
#include <stdio.h>
void fun(const char **p) { }
int main(int argc, char **argv)
{
const char **temp
fun(argv);
getchar();
return 0;
}
解答
函式傳遞參數時，fun需要的參數為const char但在main函式中傳遞值為char會造成compiler error，改為下列程式碼即可符合預期結果。
40.
int main()
{
int c=5;
printf("%d\n%d\n%d", c, c <<= 2, c >>= 2);
getchar();
}
Basic C concept
Q: Memory allocation
int global_var = 0; //global初始化區(data)
int *global_ptr; //global未初始化區(bss)
int main()
{
int local_var; //stack
char str[] = "1234"; //stack
char *p1; //stack
static int static_var = 0; //global初始化區(data)
p1 = (char *)malloc(sizeof(char *)); //heap
return 0;
}
Q: Compare Compile error, linker error, run time error
| Feature | Explain |
|---|---|
Complie error |
通常是syntax錯誤 |
linker error |
找不到外部include的function或是程式碼 |
run time error |
常見為錯誤使用指標導致OS或程式被kill掉 例如:Segmentation falut |
Q: Explain define, const, volatile, inline, extern
| Feature | Explain |
|---|---|
| define | 巨集的一種預編譯會直接展開不會做型別檢查，因為是展開所以要注意一些side effect |
| const | Read-only變數，通常在編譯階段使用 |
| volatile | 告知complier不要對其進行最佳化，通常使用在變數進行重複執行記憶體讀寫的操作常用於ISR和 Register |
| inline | 可以拿來修飾function, 主要用來加速執行速度, 參數類型會檢查, inline後編譯器不一定會實作 |
| extern | 可以引用外部的全域變數 |
Q: What is the output
define
#define A 2+3
#define B (2+3)
printf("%d\n", A*A); //2+3*2+3=11
printf("%d\n", B*B); //(2+3)*(2+3)=25
static v.s local
/* Call this function 10 times, a=?, b=? */
void fun()
{
static int a = 0;
int b = 0;
a++;
b++;
printf("%d\n", a); //10
printf("%d\n", b); //1
}
const
const int c = -5;
c++; //Compile error
printf("%d\n", c);
switch
switch(2) {
case 0:
printf("0\n"); //won't print
break;
case 1:
printf("1\n"); //won't print
case 2:
printf("2\n"); //will print
case 3:
printf("3\n"); //will print
}
linux
Q: 以下哪個Linux command可以列出當前目錄中的檔案?
(A) free
(B) top
© cd
(D) ls
free: 查看記憶體
top: 效能分析工具, 類似工作管理員
cd: 切換目錄
ls: 列出當前目錄的檔案
Q: 請說明tar的功能
Linux常用的壓縮或解壓縮command
參數有很多種組合, 都是用來壓縮或解壓縮不同的壓縮格式
Compare user space(mode) and kernel space(mode)
sudo 還是在 user space
Q: 用chmod更改file.txt的權限為 -rwxrwx–
$ chmod 770 file.txt
or
$ chmod ug+rwx file.txt
Q: 在linux中, kernel space如何傳遞資料給user space
有寫過kernel module的話應該會大概知道怎麼做
主要就是copy_to_user和copy_from_user這兩個function
https://www.jollen.org/blog/2006/12/linux_device_driver_io_3.html
Q: spin lock, mutex, semaphore在linux的差異
mutex同一時間只能讓一個process進入critical section, 有鑰匙的人可以進去
semaphore允許多個process進入critical section, 滿了就要等process出來才能進去, 沒有鑰匙
spin lock為busy waiting的機制, 比較適合在需要保護某一小段data時, 因為等待時間較長
Pointer
*: pointer, dereference (解指標)&: address-of**: pointer to pointer(指標的指標)call-by-value: caller and callee各自有自己的記憶體, C的function call都屬於這種call-by-reference: caller and callee使用相同的記憶體, C++才有
Basic
int a = 5;
int *p; // assign an pointer to int
p = &a; // assign the address of variable "a" to pointer p
printf("%d\n", *p); //dereferenec p:5
printf("%p\n",&a); //0xXXXXX
printf("%p\n", p) // same as address of variable a
int a[] = {1,2,3,4,5};
int *p1 = a ; // pointer p will point to the address of head of a
char c[] = "54321"
int *p2 = c;
/* array of pointer to int */
printf("%d\n", *p1); //a[0]=1
printf("%d\n", *p1+1);//a[0]+1=2
printf("%d\n", *p1++);//1, and the pointer move to next element
printf("%d\n", *++p1); // 3, the pointer moves first then dereference
printf("%d\n", ++*p1); // 4,dereference then plus one
/* array of pointer to char*/
printf("%c\n",*p2); c[0] = 5;
printf("%c\n",*(p2+1)); c[0+1] = 4;
printf("%c\n",sizeof(c)); // 6 byte, 5+1(end char)
*p++ = *(p++);
*++p = *(++p);
++*q = ++(*p);
Function Pointer
很少遇到, qsort函數的callback參數就有需要
// function define
void fun(char *str, int len);
// funtion pointer define
void(*fun_ptr)(char *, int )= &fun
Advanced usage
Q: 給一句話, 把那句話表達出來
// 1. A ptr to a ptr to an integer
// 2. an array of 10 integer
// 3. An array of 10 ptr to integer
// 4. A ptr to an array of 10 integer
// 5. A ptr to a function that take an integer as an argument and return an integer
// 6. An array of the pointer to function that take an integer argument and return an integer
int **p;
int a[10];
int *p[10];
int (*p)[10];
int (*p)(int);
int (*p[10])(int);
Q: What is the output (64-bits machine)
int main(void)
{
char *a[] = {"abc","def","ghijk","lmnop"}
};
char *b = a[2];
printf("%d\n", sizeof(a)); // 8 * 4 =32
printf("%d\n", sizeof(b)); // 8
printf("%d\n",sizeof(a[2])) // 8
printf("%d\n",sizeof(b[2])) //1
Q: Write two functions that are able to access a fixed memory location
/* 64-bits machine */
uint64_t *read_mem(uint64_t addr)
{
uint64_t *p = addr;
return *p;
}
void write_mem(uint64_t addr, uint64_t data)
{
uint64_t *p = addr;
*p = data;
}
Struct,union,enum
struct: 自定義的一種型別, 可以包含多個不同型別的變數, 每個成員都會配置一塊空間
union: 跟struct有點像, 主要差別是裡面的成員共用一塊記憶體, 所需記憶體由型別最大的成員決定
enum: 可以用來定義常數, 主要是可以提升程式可讀性, 裡面的值從值指定的值開始遞增, 預設為0
/* struct */
struct GPIO {
char name[12];
unsigned char direction;
unsigned int value;
struct GPIO *gpio_ptr;
//struct不能含有自己, 但可以有自己的pointer
};
int main(void)
{
/* normal */
/*
struct GPIO g = {
"GPIO_IO1",
0,
1,
NULL
};
*/
/* designated initializers(recommend) */
struct GPIO g = {
.name = "GPIO_IO1",
.direction = 0,
.value = 1,
.gpio_ptr = NULL
};
printf("%s\n", g.name); //GPIO_IO1
printf("%d\n", g.direction); //0
printf("%d\n", g.value); //1
printf("%p\n", g.gpio_ptr); //nil
return 0;
}
/* union */
union data {
unsigned char c; //1 byte
int val; //4 bytes
long int li; //8 bytes
};
int main(void)
{
union data d;
d.c = 255;
printf("%d\n", d.c); //255
return 0;
}
/* enum */
enum GPIO_NUM {
GPIO_IO0 = 0,
GPIO_IO1,
GPIO_IO2,
GPIO_IO3,
GPIO_IO4
};
int main(void)
{
enum GPIO_NUM G = GPIO_IO3;
printf("%d\n", G); //3
return 0;
}
struct pointer
typedef struct _GPIO {
char *name; //8 bytes
unsigned char direction; //1 byte
unsigned int value; //4 byte
} GPIO;
int main(void)
{
GPIO *ptr = (struct GPIO *)malloc(sizeof(struct GPIO));
ptr->name = "GPIO_IO20";
ptr->direction = 0;
ptr->value = 1;
printf("%s\n", ptr->name); //GPIO_IO20
printf("%d\n", ptr->direction); //0
printf("%d\n", ptr->value); //1
return 0;
}
typedef struct _GPIO1 {
char *name; //8 bytes
unsigned char direction; //1 byte
unsigned int value; //4 byte
} GPIO1;
typedef struct _GPIO2 {
unsigned char direction; //1 byte
char *name; //8 bytes
unsigned int value; //4 byte
} GPIO2;
int main(void)
{
printf("%lu\n", sizeof(GPIO1)); //16
//因為struct會被編譯器拿去做對齊最佳化,
//所以"direction"和"value"這兩個變數會被合在一起然後補滿(padding)8 bytes
printf("%lu\n", sizeof(GPIO2)); //24
//"direction"會補滿8 bytes, "value"也會補滿8 bytes, 所以加起來是24 bytes
return 0;
}
union and CPU endian
一般CPU都是Little-Endian, 也就是lowest bytes會放在最低的記憶體位子上
Big-Endian則相反
union data {
unsigned char c; //1 byte
unsigned int val; //4 bytes
};
int main(void)
{
union data d;
d.val = 0x12345678;
printf("0x%x\n", d.c); //Little-Endial: 0x78
d.c = 256;
printf("%d\n", d.c); //0
return 0;
}
判斷程式碼
#include <stdio.h>
typedef union {
unsigned long l;
unsigned char c[4];
} EndianTest;
int main() {
EndianTest et;
et.l = 0x12345678;
printf("本系統位元組順序為：");
if (et.c[0] == 0x78 && et.c[1] == 0x56 && et.c[2] == 0x34 && et.c[3] == 0x12) {
printf("Little Endiann");
} else if (et.c[0] == 0x12 && et.c[1] == 0x34 && et.c[2] == 0x56 && et.c[3] == 0x78) {
printf("Big Endiann");
} else {
printf("Unknown Endiann");
}
printf("0x%lX 在記憶體中的儲存順序：n", et.l);
for (int i = 0; i < 4; i++) {
printf("%p : 0x%02Xn", &et.c[i], et.c[i]);
}
return 0;
}
網路位元組順序
#include <stdio.h>
#include <stdint.h>
#include <arpa/inet.h>
typedef union {
uint32_t l;
unsigned char c[4];
} EndianTest;
// 輸出位元組順序
void printBytes(uint32_t x) {
EndianTest et;
et.l = x;
for (int i = 0; i < 4; i++) {
printf("0x%02X ", et.c[i]);
}
printf("n");
}
int main() {
uint32_t x = 0x12345678;
printf("0x%X 在記憶體中的儲存順序：", x);
printBytes(x);
uint32_t n = htonl(x);
printf("0x%X 在網路中的傳輸順序：", x);
printBytes(n);
}
0x12345678 在記憶體中的儲存順
Q: sizeof(struct data)? (64-bits machine)
struct __attribute__((__packed__)) data {
char c; //1
short s1; //2
short s2; //2
int h; //4
};
printf("%lu\n", sizeof(struct data)); //9
bitwise operator
Q: What is the output
unsigned int x = 0xf;
x << = 4;
x |= 0x03;
printf("0x%x",x) // 0xf3
Q: Complete the program
void write_reg(unsinged int *x, unsigned int loc,unsigned char en)
{
if(loc<0) return;
if(en == '0'){
*x &= ~(1<<loc); //clear bit
}else if(en == '1'){
*x |=(1<<loc) // set bit
}else if(en == '2'){
*x ^= (1<<loc); // toggle bit
}else{
printf("intput error\n");
}
}
Q: Write a program to check is power of 2
int is_pow_2(unsigned int x){
return (x&-x) == x;
}
Q: Write a program to calculate number of 1
int number_of_one(unsigned int x){
int c = 0;
while(x != 0){
x = x &(x-1);
}
return c;
}
Q: Find the MSB and LSB location
void MSB(unsinged int x){
unsigned int test = 0x80000000;
int count = 31;
if(x<=0){
return;
}
while((x & test)>>count !=1){
count --;
test>>=1;
}
printf("MSB bit is at %d\n",count);
}
void LSB(unsigned int x){
unsigned int test = 0x1;
int count = 0;
while((x & test)<<count == 0){
test <<=1;
count++;
}
printf("LSB is at %d\n",count);
}
Write a program to check the hex is equal
int is_hex_equal(unsigned short input)
{
unsigned short hex[4]={0};
hex[0] = (input & 0xF000)>>12;
hex[1] = (input & 0x0F00)>>8;
hex[2] = (input & 0x00F0)>>4;
hex[3] = (input & 0x000F;
if(hex[0]==hex[1]&&hex[0]==hex[2]&&hex[0]==hex[3]){
return 1;
}else{
return 0;
}
}
Programming
Basic
Q: Write a program to print fibonacci number
/* recursive */
int fib_recursive(int n){
if(n<=1){
return fib_recursive(n-2)+fib_recursive(n-1)
}
}
/* Dp */
int fib_dp(int n){
int dp[1001] ={0};
dp[0] = 0;
dp[1] = 1;
if(n <= 1) return dp[0];
if(n == 2) return dp[1];
for(int i = 2;i<n,i++){
dp[i] =dp[i-1]+dp[i-2];
}
return dp[n-2]+dp[n-1];
}
Q: Write a swap function
// normal
void swap(int *a, int *b){
int tmp = 0;
tmp = *a;
*a = b;
*b = tmp;
}
void swap_bitwise(int *a, int *b){
*a =(*a)^(*b);
*b =(*a)^(*b);
*a=(*a)^(*b);
}
PrintStar
void print_star()
{
for(int i =1;i<=n;i++){
for(int j = 0;j<i;j++){
printf("*");
}
printf("\n");
}
}
calculate GCD
int gcd_recursive(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
int gcd(int a,int b){
while(a != b){
if(a>b) a -=b;
if(b>a) b -= a;
}
return a;
}
int lcm(int a,int b){
return a*b /gcd(a,b)
}
Find 1~100 prime
void find_prime(int n){
int flag = 1;
int prime = 0;
for(int i = 2;i<=n;i++){
prime = i;
flag = 1;
for(int j = 2;j<i;j++){
if(i%j==0){
flah = 0;
break;
}
}
if(flag) printf("%d\n", prime)
}
}
roundoff program
int roundoff(float x){
return (int)(x+0.5)
}
reversestring
void swap(char *c1,char *c2){
*c1 = (*c1) ^(*c2);
*c2 = (*c1)^(*c2);
*c1 = (*c1)^(*c2);
}
char *reverse_str(char *str){
const int len = strlen(str);
for(int i = 0;i<len/2;i++){
swap(&str[i],&str[len-1-i]);
}
return str;
}
Complete strcpy、strlen、strcmp、strcat
// strcpy
void strcpy(char *dest,const char *src){
if(dest == NULL|| src == NULL) return;
while(*src !='\0'){
*dest = *src;
dest++;
src++;
}
}
//strcat
void strcat(char *dest,const char *src){
char *p = dest;
int location = 0;
if(dest == NULL || location == NULL) return;
while(*(p++) != '\0') location++;
while(*src !='\0'){
dest[location] = *src;
src++;
location++;
}
}
// strlen
void strlen(const char *str){
int len = 0;
while(*str++ !='\0') len++;
return len;
}
//strcmp
void strcmp(const char *s1, const char *s2){
char *ptr = s1+ strlen(s1)
while(*s2 !='\0'){
*ptr++ = *s2++;
}
*ptr = '\0';
return s1;
}
binary search
void binary_search(int *arr,int len,int target){
int right = len-1,left = 0,mid=0;
while(right>=left){
mid=(right+left)/2;
if(arr[mid]<target){
left = mid +1;
}else if(arr[mid]>target){
right = mid - 1;
}else if(arr[mid]== target){
printf("Found it\n");
return;
}
}
printf("Not found it\n");
}
Marco
//max
#define MAX(a,b) ((a)>(b))?(a):(b)
// array element
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
// setbit
#define set_bit(b,n) ((b) |= (1<<(n)))
// clearbit
#define clear_bit(b,n) ((b) &= ~(1<<(n)))
// togglebit
#define toggle_bit(b,n) ((b) ^= (1<<(n)))
大小寫轉換
char convert(char c){
if(c>='A'&&c<='Z')
return c+32;
else if(c>='a'&&c<='z')
return c-32
else
return 0;
}
輸入三個數找出最大和最小值
struct ret_val{
int max;
int min;
}
struct ret_val find(int a,int b,int c){
struct ret_val ret;
ret.max = 0;
ret.min = 0;
if(a>b){
if(a>c)
{ret.max =a;}
else{
ret.max = c;
}
}else{
if(b>c){
ret.max = b;
}else{
ret.max = c;
}
}
if(a<b){
if(a<c){
ret.min= a;
}else{
ret.min = c;
}
}else{
if(b<c){
ret.min = b;
}else{
ret.min = c;
}
}
return ret;
}
Sorting
linkedlist
Append node
把node加在list最後面
最簡單實作的方法為traverse整個list然後再加上去，
如果list是空的就直接加上去
void append(struct listNode **head,int data){
struct listNode *new_node = NULL, *curr = *head;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if(new_node == NULL) return;
new_node -> next = NULL;
new_node -> data = data;
if(curr == NULL){
*head = new_node;
return ;
}
while(curr->next) curr = curr->next;
curr->next = new_node;
}
Push node
node加在最前面
void push(struct listNode **head,int data){
struct listNode *new_node = NULL;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if(new_node == NULL) return;
new_node->next = *head;
new_node->data = data;
*head = new_node;
}
print list
void print_list(struct listNode *head){
struct listNode *ptr = head;
while(ptr){
printf("%d->",ptr->data);
ptr = ptr->next;
}
printf("%d\n",ptr->data);
}
Delete Node
void delete_node_pos(listNode **head, int pos){
struct ListNode *prev = NULL;
struct ListNode *curr = *head;
int counter = 0;
if(pos<0) return; // Not allow -1,-2
while(cur && counter != pos){
prev = curr;
curr = curr->next;
counter++;
}
if(curr==NULL){
printf("Node doesn't exits\n")
}else if(*head == curr){
*head = curr->next;
free(curr);
curr = NULL;
}else{
prev->next = curr->next;
free(curr);
curr = NULL;
}
}
Insert node after a give postion
void insert_node_after(struct listNode **head,int pos,int data){
struct listNode *new_node = NULL;
struct listNode *curr = *head;
int i = 0;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if(new_node == NULL) return;
new_node->next = NULL;
new_node->data = data;
if(*head == NULL || pos <0)return;
while(curr->next && pos !=i){
curr = curr->next;
i++;
}
new_node->next = curr->next;
curr->next = new_node;
}
