contributed by < haoyu0970624763
>
int hammingDistance(int x, int y){
return __builtin_popcount(x ^ y);
}
Hamming Distance 是要計算兩串二進位字串不同的地方有幾個,也就是計算 XOR 之後 有幾個 1
int hammingDistance(int x, int y) {
x=x^y;
unsigned count=0;
while(x){
count++;
x=x&(x-1);
}
return count;
}
#include <stdlib.h>
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]];
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->n; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj);
}
obj->parent = malloc(n * sizeof(int *));
可以從這一行看出 parent
為 pointer to pointer 的 type
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;
}
max_level
是紀錄現在這個tree當中最大的level數為多少
將 obj->parent
做成二維陣列,obj->parent[n][max_level]
並將所有值初始化成 -1
( -1 表示 no ancestor 的意思)
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
parent[i]
存放的是 nodei 父親的位置
並把obj->parent[i][0]
用來存放 nodei 的父親
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]];
if (obj->parent[i][j] != -1) quit = 0;
}
if (quit) break;
}
目的: 設置 obj->parent 的 element
從 1 數到 n
可以觀察到:
#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;
}
程式解說
div3
、div5
分別可知道 i
是否為 3 或 5 的倍數
這個概念在quiz2有碰過
length
則是根據我們觀察,判斷是不是3或5的倍數進行 operator 的平移
div3 |
div5 |
length |
( 8 >> div5) >> (div3 << 2) |
---|---|---|---|
1 | 0 | 4 | 0 |
0 | 1 | 4 | 4 |
1 | 1 | 8 | 0 |
0 | 0 | 2 | 8 |
// OpenCL卷积核 __kernel void convolution(__global const float *restrict inputImage, __global float *restrict outputImage, __constant const float *restrict filter, const int filterWidth) { // 計算濾波器寬度的一半 int half_filter_width = filterWidth >> 1; // 獲取圖像的寬度和高度
Jan 3, 2024VECTOR_WIDTH = 2
Nov 11, 2023contributed by < haoyu0970624763 > 測驗 1 跨平台的 ASR (arithmetic right shift) 實作 #include <stdio.h> int asr_i(signed int m, unsigned int n) { const int logical = (((int) -1) >> 1) > 0; unsigned int fixu = -(logical & (m < 0));
Mar 30, 2023Emotion Recognition for Cognitive Edge Computing Using Deep Learning 當資料從 sensor / IoT 大量傳輸到處理中心時 , 主要有三個挑戰 : latency, scalability, and security latency : 將 vedio data 輸入從 sensor 送到 cloud , 在 cloud 推斷結果 , 再 return 結果 , 這樣會造成許多延遲 , 此時 data scaliing 是一個有效運用資源的方法 邊緣運算 : 從 sensor / IoT 傳遞資料上去處中心時時需要大量的頻寬以及足夠的時間 , 因此 , 在連續的資料傳輸中 , 資料應該被預處理以減輕傳遞的負擔 , 可以为用户提供更少的延迟和实时体验 Edge devices : 1 個 edge server , 一個行動通信基地台 , 數個 end devices(數據來源) edge server 位置處於 sensor / IoT gateways 附近可以減低 latency
Feb 15, 2023or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up