# G10: quiz7

#### tags: `sysprog2019`
contributed < `Benny1117Yen` >

## 測驗 `1`

考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3的倍數，印出 "Fizz"
* 如果是 5 的倍數，印出 "Buzz"
* 如果是 15 的倍數，印出 "FizzBuzz"
* 如果都不是，就印出數字本身

直覺的實作程式碼如下: (`naive.c`)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 `printf` 的(格式)字串，可分類為以下三種:
1. 整數格式字串 `"%d"` : 長度為 2 B
2. "Fizz" 或 "Buzz" : 長度為 4 B
3. "FizzBuzz" : 長度為 8 B

考慮下方程式碼:

#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bit-wise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)

#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char **argv) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

其中 `is_divisible` 函式技巧來自 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/)，甚至 gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。

Ans: `KK1` = `div5`, `KK2` = `div3`, `KK3` = `2`

### 延伸問題

待補
程式內註解 待補

---

## 測驗 `2`

[CS:APP 第 3 版](https://hackmd.io/@sysprog/S1vGugaDQ) 一書的第 2 章家庭作業 `2.97` (Page 97) 題目:
> 依據浮點數位元編碼規則，實作出符合以下原型定義和作用的函式: (`float-i2f.c`)

/* compute (float) i */
float_bits float_i2f(int i);

> 給定整數 `i`, 此函式計算 (float) i 逐位元的表示法。
> 其中

typedef unsigned float_bits;

> 並假設 `int` 長度為 32-bit 且在 little endian 機器上執行。

可用的工具函式:

/* Assuming i > 0, calculate an integer's bit length */
/*  * e.g. 0x3 => 2, 0xFF => 8 */
static inline int bits_length(int i) { return 32 - __builtin_clz(i); }

/* generating bitmask. e.g. 3  => 0x00000007, 16 => 0x0000FFFF */
static inline unsigned bits_mask(int l) { return (unsigned) -1 >> (32 - l); }

==本題採問答形式進行==

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

typedef unsigned float_bits;

float_bits float_i2f(int i);

static inline int bits_length(int i) { return 32 - __builtin_clz(i); }

static inline unsigned bits_mask(int l) { return (unsigned) -1 >> (32 - l); }

// Compute (float) i
float_bits float_i2f(int i) {
  unsigned sig, exp, frac, rest;
  unsigned exp_sig /* exp w/ sig */, round_part;
  unsigned bits, fbits;
  unsigned bias = 0x7F; // 01111111 = 127
  
  if (i == 0) {
    sig = 0;
    exp = 0;
    frac = 0;
    return sig << 31 | exp << 23 | frac;
  }
  
  if (i == INT_MIN) {
    sig = 1;
    exp = bias + 31;
    frac = 0;
    return sig << 31 | exp << 23 | frac;
  }
  
  sig = 0;
  /* 2's complatation */
  if (i < 0) {
    sig = 1;
    i = -i;
  }
  
  bits = bits_length(i); /* ex. 14; 25; 26 */
  fbits = bits - 1; /* 13; 24; 25 */
  exp = bias + fbits; /* 127 + 13; 127 + 24; 127 + 25 */

  rest = i & bits_mask(fbits); /* 11101101101101 & (u)-1 >> 19 = 00000000000000000001101101101101; 25 bits & (u)-1 >> 8 剩下 24 bits; 26 bits & -1 >> 7 剩下25 bits */
  if (fbits <= 23) {
    frac = rest << (23 - fbits);
    exp_sig = exp << 23 | frac;
  } else {
    int offset = fbits - 23; // if fbits > 23
    int round_mid = 1 << (offset - 1); /* ex. 0000 ~ 1111, mid = 1000 */

    round_part = rest & bits_mask(offset); /* 等於拿多出來的一段 & 整段, 得到多出來的 part */
    frac = rest >> offset; // 因為多於 23
    exp_sig = exp << 23 | frac;

    /* round to even */
    if (round_part < round_mid) { // 代表不會進位
      /* nothing */
    } else if (round_part > round_mid) { // 進位 +1
      exp_sig += 1;
    } else { /* 當兩個相同時, 拿 frac 來 & 1, 等於 1 就是看 frac 最小位為 1 時就把 sig + 1 */
      /* round_part == round_mid */
      if ((frac & 0x1) == 1) {
        /* round to even */
        exp_sig += 1;
      }
    }
  }

  return sig << 31 | exp_sig;
}

int main (in argc, char* argv[]) {
    float i2f = (float)(int) 15213;
    printf("0x%.8X\t%d\t", 15213, 15213);
    printf("0x%.8X\t%.50f\n", float_i2f(i2f), i2f);
}

#### Results

0x00003B6D 15213
0x466DB400 15213.00000000000000000000000000000000000000000000000000

---