# 2020q3 Homework4 (quiz4) contributed by < [stonelin](https://github.com/StoneLin0708) > ###### tags: `sysprog2020` # hammingDistance ```c int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); } ``` Use xor (^ operator in c) to count different bits. * leetcode Total Hamming Distance ![](https://i.imgur.com/172iRNJ.png) ```c 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 ```c 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 ```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 >> 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