# 2020q3 Homework4 (quiz4)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

# hammingDistance

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

Use xor (^ operator in c) to count different bits.

* leetcode Total Hamming Distance


int totalHammingDistance(int* nums, int numsSize){
    const int* end = nums + numsSize;
    const int bits  = sizeof(int) * 8;
    int b[bits];
    
    for(int i=0;i<bits;++i) b[i] = 0;
    
    for(int* begin=nums;begin!=end;++begin)
        for(int i=0;i<bits;++i)
            b[i] += ((*begin) >> i) & 0x1;
    
    int sum=0;
    for(int i=0;i<bits;++i)
        sum+=(numsSize-b[i])*b[i];
    return sum;
}

# KthAncestor

typedef struct {
    int **parent;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j - 1] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (1 << i))
            node = obj->parent[node][i];
    return node;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->max_level; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}

# FizzBuzz

#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 >> div5) >> (div3 << 2)], length);
        fmt[length] = '\0';

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

Using truth table to understand the implementation.

|div3|div5|length|offset|fmt|
|-|-|-|-|-|
|0|0|2|8|"%u"|
|0|1|4|0|"Fizz"|
|1|0|4|4|"Buzz"|
|1|1|8|0|"FizzBuzz"|

Compare to naive version, it is
* branch less, won't be any branch prediction fail.
* doesn't use integer division
* come with a cost of one additional memory copy