資料結構›Ch8 雜湊第 23 題/共 37 題
23. Bloom Filter、Bitmask、程式追蹤
#DS-08-023易Bloom FilterBitmask程式追蹤
題組題幹(本題:(a),共 4 小題)點擊展開
A firewall uses a fast pre-check before running an exact check. All input integers are non-negative. You must answer Questions 1-4 based on the program below.
static inline uint32_t f1(int x) { return (uint32_t)(x % 8); }
static inline uint32_t f2(int x) { return (uint32_t)((x / 2) % 8); }
static inline void set1(uint32_t *b, uint32_t p) { *b |= (1u << p); }
static inline int get1(uint32_t b, uint32_t p) { return (b >> p) & 1u; }
static int precheck(uint32_t bits, int x) {
return get1(bits, f1(x)) && get1(bits, f2(x));
}
static int exact_check(int x) {
return (x == 10) || (x == 22);
}
int main(void) {
int base[] = {10, 22};
uint32_t bits = 0;
for (int i = 0; i < (int)(sizeof(base)/sizeof(base[0])); i++) {
set1(&bits, f1(base[i]));
set1(&bits, f2(base[i]));
}
int n;
scanf("%d", &n);
int exact_checks = 0, blocked = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
if (precheck(bits, x)) {
exact_checks++;
if (exact_check(x)) blocked++;
}
}
printf("%d %d\n", exact_checks, blocked);
return 0;
}
[3%] What is precheck(bits, x) mainly used for?
📄 成大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊