# 課前測驗

## Q1

---
## Solution:

1. 其具體作用是 bit reverse, e.g., 11000101 to 10100011.

思路：
0xaaaaaaaa： 1010 1010 1010 1010 1010 1010 1010 1010
0x55555555： 0101 0101 0101 0101 0101 0101 0101 0101

11000101 經過上述運算，仍為 11000101

0xcccccccc： 1100 1100 1100 1100 1100 1100 1100 1100
0x33333333： 0011 0011 0011 0011 0011 0011 0011 0011

11000101 經過上述運算，為 00110101

0xf0f0f0f0： 1111 0000 1111 0000 1111 0000 1111 0000
0x0f0f0f0f： 0000 1111 0000 1111 0000 1111 0000 1111

00110101 經過上述運算，為 01010011
結果不對

另外一種可能 先從 >>4 and <<4 開始
11000101 to 01011100

01011100 to 01010011

01010011 to 10100011

OK!

2.

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

unsigned int v; // input bits to be reversed
v = num;
unsigned int r = v & 1; // r will be reversed bits of v; first get LSB
of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s--;
}
r <<= s; // shift when v's highest bits are zero

3. uint16_t version

#include <stdint.h>
#include <stdio.h>

uint16_t func16(uint16_t x) {
uint16_t value = x;
const uint16_t mask0 = 0x5555;
const uint16_t mask1 = 0x3333;
const uint16_t mask2 = 0x0F0F;
const uint16_t mask3 = 0x00FF;

value = (((~mask0) & value) >> 1) | ((mask0 & value) << 1);
value = (((~mask1) & value) >> 2) | ((mask1 & value) << 2);
value = (((~mask2) & value) >> 4) | ((mask2 & value) << 4);
value = (((~mask3) & value) >> 8) | ((mask3 & value) << 8);
return value;
}

4. Where can we use this code?
FFT(Fast Fourier Transform)的演算法中，可以用來求得信號對應的頻譜。
其中，將訊號拆成奇數點與偶數點，並作蝶形運算，因此需要 Bit-Reverse.
[FFT](http://eshare.stust.edu.tw/EshareFile/2010_6/2010_6_a78298c9.pdf)

---
## Q2


---
## Solution:

uint multiplier(uint a, uint b)
{
uint r = 0;
while (b != 0)
{
if ((b & 1) != 0)
r = r + a;
a <<= 1;
b >>= 1;
}
return r;
}

---

## Q3


---
## Solution:

---
## Q5


---
## Solution:

24個。c

fork()的功能是創建新的執行緒。
且因為 wait(NULL)的作用才會產生 24個 "-"。

status 參數是用來保存 process 退出時的狀態，如果我們對 child process 怎
麼死掉毫不在意的話，可以設 NULL。

若將 i 上限設為2，程式會產生8個 "-"。
wait(NULL),parent process will wait until child process die.

Let's do some exp:

result:

*****************
i = 0, After fork(), I am the proc:0,@
i = 1, After fork(), I am the proc:0,@
out of loop
*****************
i = 0, After fork(), I am the proc:31096,@
i = 1, After fork(), I am the proc:0,@
out of loop
*****************
i = 0, After fork(), I am the proc:0,@
i = 1, After fork(), I am the proc:31098,@
out of loop
*****************
i = 0, After fork(), I am the proc:31096,@
i = 1, After fork(), I am the proc:31097,@
out of loop

#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main() {
pid_t proc;
//printf("I am the proc:%d\n",proc);
printf("*****************\n");
for (int i = 0; i < 2; i++) {
printf("i = %d, ", i);
proc = fork();
printf("After fork(), I am the proc:%d,@\n", proc );
//printf("I am the proc:%d\n",getpid());
}
printf("out of loop\n");
wait(NULL); wait(NULL);wait(NULL);
return 0;
}

目前看起來的行為是，process都會從頭開始跑 （所以有星號那一排），
process總共有2^2個，
迴圈由i=0,i=1，跑兩圈，所以(2^2)*2 = 8。

i=0, i<3 的時候，
process總共有2^3個，
迴圈由i=0到i=2，跑三圈，所以(2^3)*3 = 24。

猜測 i=0,i<4 的時候，
(2^4)*4 = 64


Bingo!
規律是有找到，總之就是fork()之後，不管是父還是子，都會從頭開始跑。
看跑幾次迴圈，跑 n 次，子 process 就是 (2^n) - 1 個，會印 (2^n)*n 個 "_"。

但是 printf("-\n"); 這樣會只有6個"-"
WHY???

#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main() {
pid_t proc;
//printf("I am the proc:%d\n",proc);
// printf("*****************\n");
for (int i = 0; i < 2; i++) {
//printf("i = %d, ", i);
proc = fork();
//printf("After fork(), I am the proc:%d,@\n", proc );
//printf("I am the proc:%d\n",getpid());
printf("-\n");
}
//printf("out of loop\n");
wait(NULL); wait(NULL);wait(NULL);
return 0;
}