# 2019q3 Homework2 (quiz2)
contributed by < `uccuser159` >
## 題目1
- [ ]考慮下方檔案 4thought.c 是 ACM-ICPC 題目 4 thought 的一個解法，假設程式的輸入符合 4 thought 的描述，請補完程式碼:
```cpp
#include <stdbool.h>
#include <stdio.h>
enum {
opType1 = 0x1 << 0, opType2 = 0x1 << 1,
opType3 = 0x1 << 4, opType4 = 0x1 << 5,
};
static int operate(int op, int a, int b) {
switch (op) {
case opType1: return a + b;
case opType2: return a - b;
case opType3: return a * b;
case opType4: return (int) a / b;
}
return 0;
}
static char op_to_char(int op) {
return "+-*/?"[op - 1];
}
static int op_to_prio(int op) {
return ((int[]){opType1, opType2, opType3, opType4, -1})[op - 1];
}
static int calc(int op1, int op2, int op3) {
op1 = op_to_prio(op1);
op2 = op_to_prio(op2);
op3 = op_to_prio(op3);
bool p1 = (op1 & 0x0F) == 0; // = 1 for * or /
bool p2 = (op2 & 0x0F) == 0; // else = 0
bool p3 = (op3 & 0x0F) == 0;
// (4 + 4 + 4 + 4) or (4 / 4 / 4 / 4)
if ((p1 == p2) && (p2 == p3))
return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
/* Write your code here */
return 0;
}
int main(void) {
int n;
scanf("%d", &n);
int sol[n];
for (int i = 0; i < n; i++)
scanf("%d", &sol[i]);
bool validSolution = false;
for (int i = 0; i < n; i++) {
for (int op1 = 4; op1 > 0; op1--) {
for (int op2 = 4; op2 > 0; op2--) {
for (int op3 = 4; op3 > 0; op3--) {
int sol_checked = calc(op1, op2, op3);
if (sol_checked == sol[i]) {
validSolution = true;
char op1char = op_to_char(op1);
char op2char = op_to_char(op2);
char op3char = op_to_char(op3);
printf("4 %c 4 %c 4 %c 4 = %d\n", op1char, op2char,
op3char, sol[i]);
op1 = -1; op2 = -1; op3 = -1;
break;
}
}
}
}
if (!validSolution)
printf("no solution\n");
validSolution = false;
}
return 0;
}
```
---
### 思考
在`calc`函式中式在做**四則運算**，考慮先乘除後加減的問題：
4 __ 4 __ 4 __ 4 (底線處放運算子 + . - . x . /)
根據`op_to_prio`函式回傳的值與 0x0F 做 AND 運算：
(+ . -)應該得到的布林值為0； (x . /)得到的布林值為1
所以應該補入的程式碼為：
```cpp
if(!p1 && p2 && p3) // 4 + 4 x 4 x 4
return operate(op1,(operate(op3,operate(op2,4,4),4),4);
if(!p1 && !p2 && p3) // 4 + 4 + 4 x 4
return operate(op2,(operate(op1,operate(op3,4,4),4),4);
if(!p1 && p2 && !p3) // 4 + 4 x 4 + 4
return operate(op3,(operate(op1,operate(op2,4,4),4),4);
if(p1 && !p2 && p3) // 4 x 4 + 4 x 4
return operate(op2,(operate(op3,operate(op1,4,4),4),4);
if(p1 && p2 && !p3) // 4 x 4 x 4 + 4
return operate(op3,(operate(op2,operate(op1,4,4),4),4);
```
* 延伸問題
## 題目2
- [ ]考慮以下程式碼 (`fitbits.c`) 可檢驗輸入的整數 `x` 是否可用 `n` 個位元來表示，例如 (x = 4, n = 9) 要回傳 `true`, 當 (x = 4, n = 2) 回傳 `false`。
```cpp
#include <stdbool.h>
bool fit_bits(int x, int n) {
/* Write your code here */
return (bool) x;
}
```
實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，可用的運算子是 `>>`, `<<`, `-`, `+`, `!`, `~`, `&`, `|`
請補完程式碼，作答時需要包含函式宣告及定義。除了撰寫程式，你應該提供對應的程式碼註解。
---
### 思考
若 n=3 只要小於8的數字皆可以用3個位元表示；若 n=4 只要小於16的數字皆可以用4個位元表示，以此類推，要數字 x 可以被 n 個位元表示，則 $x <= 2^n$ 。
所以補完的程式碼為：
```c
#include <stdbool.h>
bool fit_bits(int x, int n) {
x = ((x >> n) == 0);
//將數字 x 除以2且取整數 n 次，若為0則可以被 n 位元表示，反之則不能被 n 位元表示
return (bool) x;
}
```
* 延伸問題
## 題目3
- [ ]考慮以下程式碼 (`is-less-equal.c`) 可檢驗輸入的整數 `x` 和 `y`，是否存在 $x <= y$ 的關係。例如 (x = 4, y = 4) 要回傳 `true`, 當 (x = 14, y = 9) 回傳 `false`。
```cpp
#include <stdbool.h>
bool is_leq(int x, int y) {
int s;
/* Write your code here */
return (bool) s;
}
```
實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，當然也不能用 `>=`, `>`, `<`, `<=`, `-` 等運算子。可用的運算子是 `>>`, `<<`, `+`, `~`
請補完程式碼，作答時需要包含函式宣告及定義。除了撰寫程式，你應該提供對應的程式碼註解。
---
### 思考
用兩數相減來比較大小，若 s = y - x >= 0，則 s 的 MSB 為0；若 s = y - x < 0，則 s 的 MSB 為1。此處不能使用 "-" 運算子，故採用取2補數的減法。
所以補完的程式碼為：
```cpp
#include <stdbool.h>
bool is_leq(int x, int y) {
int s;
s = y + (~x+1); // s = y - x
s = ((s >> 31) == 0); // 判斷 s 的正負(s>=0回傳true;s<0回傳false)
return (bool) s;
}
```
* 延伸問題
## 題目4
考慮一種針對短字串的最佳化操作，假設字串總是小於等於 8 bytes，標的硬體是像 x86_64 這樣的 64-bit 架構而且是 little endian，於是我們可實作類似以下的程式碼 (`ministr.c`):
```cpp
#include <stdint.h>
#include <stdio.h>
#include <string.h>
typedef union {
uint64_t integer;
char array[8];
} mini_str;
static unsigned BitScanReverse(uint64_t x) {
return 63 - __builtin_clzll(x);
}
/**
* Find the length of the given mini_str.
* @param str string to find length of
* @return length of the given string
*/
unsigned mini_strlen(mini_str str) {
// Special case for empty string.
if (str.integer == 0) return 0;
// Otherwise find first non-zero bit (which will be in the first non-zero
// byte), and find which byte it is in.
// FIXME: Assumes little-endian.
unsigned msb = BitScanReverse(str.integer);
return msb / 8 + 1;
}
/**
* Create a new mini_str with length 0.
* @return newly created mini_str
*/
mini_str mini_str_new(void) {
// Create string of all null bytes.
mini_str str = {.integer = 0};
return str;
}
/**
* Append str2 to the end of str1 and return the reult.
* @param str1 first string
* @param str2 second string
* @return combined string
*/
mini_str mini_strcat(mini_str str1, mini_str str2) {
// Shift str2 along by str1Len characters to move it into position.
unsigned str1Len = mini_strlen(str1);
str2.integer <<= str1Len * 8; // FIXME: Assumes little-endian.
/* Write your code here */
return str1;
}
#define mini_str_to_c(mini_str) ((const char *) (mini_str).array)
#define mini_str_to_cNoConst(mini_str) ((char *) (mini_str).array)
/**
* Create a mini_str from a standard C character array.
* @param cstr Null-terminated C-string to use as input
* @return newly created mini_str
*/
mini_str mini_str_from_c(const char *cstr) {
// Create empty string.
mini_str mini_str = mini_str_new();
// Copy string.
strncpy(mini_str_to_cNoConst(mini_str), cstr, 7);
return mini_str;
}
int main(int argc, char **argv) {
mini_str all = mini_str_from_c("All ");
mini_str red = mini_str_from_c("red");
mini_str cat = mini_strcat(all, red);
printf("%s\n", mini_str_to_c(cat));
return 0;
}
```
這裡的 `__builtin_clzll` 是 GCC builtin function，作用是 bit scan，程式預期輸出為:
```
All red
```
你應該要實作 `calc` 函式中標註 `/* Write your code here */` 之後的程式碼。除了撰寫程式，你應該提供對應的程式碼註解。
注意: 實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，也不能用 `>=`, `>`, `<`, `<=`, `-` 等運算子。
---
### 思考
`mini_strcat`函式要合併兩個`mini_str`，`str1Len`為`str1`的長度。
`tr2.integer <<= str1Len * 8` 是為了要騰出`str1`長度的字串空間，再來就是要把`str2`補進去`str1`
所以補完的程式碼為：
```c
/**
* Append str2 to the end of str1 and return the reult.
* @param str1 first string
* @param str2 second string
* @return combined string
*/
mini_str mini_strcat(mini_str str1, mini_str str2) {
// Shift str2 along by str1Len characters to move it into position.
unsigned str1Len = mini_strlen(str1);
str2.integer <<= str1Len * 8; // FIXME: Assumes little-endian.
str1.integer += str2.integer; // append str2
return str1;
}
```
* 延伸問題
修改成適用 big/little-endian
在 [GCC builtin function](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 中，可以查到 Built-in Function:
>**int __builtin_clz (unsigned int x)**
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
**int __builtin_clzll (unsigned long long)**
Similar to __builtin_clz, except the argument type is unsigned long long.
## 題目5 & 6
- [ ]population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `POPCNT` 指令，`POPCNT` 可處理 16-bit, 32-bit, 64-bit 整數。
GCC 提供對應的 builtin function:
${\_\_builtin\_popcount}(x)$: `x` 總共有幾個 `1`。使用示範:
```cpp
int x = 5328; // 00000000000000000001010011010000
printf("%d\n", __builtin_popcount(x)); // 5
```
以下是個存在實作缺陷的版本:
```cpp
int popcnt_naive(int n) {
int count = 0;
while (n) {
if (n & 1)
++count;
n = n >> 1;
}
return count;
}
```
呼叫 `popcnt_naive(-1)` 時，會造成無窮迴圈，請指出錯誤所在，並且重寫為正確的版本。
---
### 思考
因為(-1)=1111...111~2~(32 bits)且當在做算術右移時，會一直補 MSB 進來，所以用函式`popcnt_naive(int n)` ，只要參數 n 小於0，即會造成無窮迴圈。
所以改進的程式碼為：
```c
int popcnt(int n) {
int count = 0;
while (n) {
n = n && (n-1); // remove the right most 1
count = count + 1;
}
return count;
}
```
- [ ] 延伸測驗 `5`，實作 branchless 的 `popcnt` 並附上對應的程式原理解說。
```c
int popcnt_branchless(int x){
x = (0x55555555 & x) + (0x55555555 & (x>> 1)); // 0-2 in 2 bits
x = (0x33333333 & x) + (0x33333333 & (x>> 2)); // 0-4 in 4 bits
x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); // 0-8 in 8 bits
x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8)); // 0-16 in 16 bits
x = (0x0000ffff & x) + (0x0000ffff & (x>>16)); // 0-32 in 32 bits
return x;
}
```
* Reference
[Source code for low level binary functions](https://www.jjj.de/bitwizardry/bitwizardrypage.html)
## 題目7
Sign in with Wallet
Connect another wallet