2018q3 第 4 週測驗題 (上)

目的: 檢驗學員對前 3 週的認知

測驗 `1`

考慮以下求絕對值的程式碼:

#include <stdint.h>
int64_t abs64(int x) {
    if (x < 0) return -x;
    return x;
}

移除分支並善用二補數特性，改寫為下方程式碼:

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x A1 (A2 - 1);
    return (x A3 y) - y;
}

請補完，其中 A1 和 A3 都是 operator。

作答區

A1 = ?

(a) &
(b) |
(c) ^
(d) <<
(e) >>

A2 = ?

(a) 0
(b) 1
(c) 61
(d) 62
(e) 63
(f) 64

A3 = ?

(a) &
(b) |
(c) ^
(d) <<
(e) >>

延伸問題:

解釋運作原理，並探討可能的 overflow/underflow 議題;
搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 abs64 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

static uint64_t r = 0xdeadbeef
int64_t rand64() {
    r ^= r >> 12;
    r ^= r << 25;
    r ^= r >> 27;
    return (int64_t) (r * 2685821657736338717);
}

在 GitHub 找出類似用法的專案並探討，提示：密碼學相關

2018q3 第 4 週測驗題 (上)

測驗 1

測驗 `1`