2022q1 Homework2 (quiz2)

contributed by <huang-me>

測驗一 (average)

Solution 1

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (a & b & 1);
}

• 當兩數之 least significant bit 皆為 1 時，此兩數相加必定會進位，因此在計算平均時應該再將進位的 1 加回結果中。

Solution 2

uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

• a & b 記錄的是兩數皆為 1 之 bit，也就是相加之後會進位之 bit。
• a ^ b 則記錄兩數相加之後不會進位之 bit
• 取平均時應該要將兩者皆右移 1 bit，但因為上述第一點為進位之 bit 右移之後的進位恰與原本之 bit 相符合，因此不需要再做任何的移動，第二點則無此特性因此依舊需要右移 1 bit。

組合語言輸出比較

Solution1 assembly code

	movl	-4(%rbp), %eax    // load a
	shrl	%eax              // a >> 1
	movl	%eax, %edx
	movl	-8(%rbp), %eax    // load b
	shrl	%eax              // b >> 1
	addl	%eax, %edx        // s = (a >> 1) + (b >> 1)
	movl	-4(%rbp), %eax    // load a
	andl	-8(%rbp), %eax    // t = a & b
	andl	$1, %eax          // t &= 1
	addl	%edx, %eax        // s + t
	popq	%rbp

• -4(%rbp) 儲存 a 的值, -8(%rbp) 儲存 b 的值，%eax、%edx 存計算中的暫時資料
• 依序將 a 以及 b 右移一個 bit 之後再相加，最後計算 a & b & 1 再與之前的結果相加獲得最終結果

Solution2 assembly code

	movl	-4(%rbp), %eax    // load a
	andl	-8(%rbp), %eax    // a & b
	movl	%eax, %edx        // t = a & b
	movl	-4(%rbp), %eax    // load a
	xorl	-8(%rbp), %eax    // x = a ^ b
	shrl	%eax              // x >>= 1
	addl	%edx, %eax        // t + x
	popq	%rbp

• -4(%rbp) 儲存 a 的值, -8(%rbp) 儲存 b 的值，%eax、%edx 存計算中的暫時資料
• 依序計算 a & b、 (a ^ b) >> 1，最後再將結果相加獲得最終結果

測驗二 (branchless max)

運作原理

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

• 若 a < b ，則 a < b 的結果值為 1，同時 -1 在二補數中為 0b1111...1111，因此無論跟什麼數值做 & 必定還是原數，而 a ^ (a ^ b) = b。
  反之， a < b 的結果值為 0，無論與什麼數做 & 其值必定維持為 0，而得結果 a ^ 0 = a。
  此結果恰與 max 相符，所以為 branchless max 之一種做法。

32 bit signed int

#include <stdint.h>
int max(int a, int b)
{
    return a ^ ((a ^ b) & -(a < b));
}

• 因決定數值大小的關鍵為 a < b，而比較數值大小時如何看待給予的數值一開始定義輸入的形態時就已經決定，因此無論此數值是否為有號數依舊可以使用相同的想法

測驗三 (GCD)

GCD

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

1. 一開始將所有共有的 2 提出
2. 並且此後因為兩數所有共同的因數 2 皆已被提出，所以每次皆可直接把較小數的因數 2 去除以加速 gcd 計算，剩餘的部分就是做輾轉相除法以獲得結果
3. 最後將獲得的結果以及先前提出的 2 利用左移計算真正的 gcd 值

透過 __builtin_ctz 改寫 GCD

#define min(x, y) x ^ ((x ^ y) & -(x > y))
uint64_t gcd_blt(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    int shift = min(__builtin_ctz(u), __builtin_ctz(v));
    u >>= shift;
    v >>= shift;
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

• 利用 __builtin_ctz 可以直接計算最後 0 的 bit 數，大幅減少了迴圈重複執行的次數。
  從 valgrind 結果來看使用 __builtin_ctz 後減少了大約一半的指令數量 。