bitmap 即為由單個元素為 boolean（0/1, 0 表示未出現，1 表示已經出現過）的數組。
如果c/c++ 沒有原生的 boolean 類型，可以用 int 或 char 來作為 bitmap 使用，如果我們要判斷某字符（char）是否出現過
使用 int 作為 bitmap 的底層數據結構，bitmap 即為 int 數組，一個 int 長度為 32 個 bit 位，
- c / 32 ⇒ bitmap 中的第幾個 int
- c % 32 ⇒ bitmap 中的某 int 中的第幾個 bit 位；
使用 char 作為 bitmap 的底層數據結構，bitmap 即為 char 數組，一個 char 長度為 8 個 bit 位；
- c / 8 ⇒ bitmap 中的第幾個 char
- c % 8 ⇒ bitmap 中某 char 中的第幾個 bit 位；
ascii
- a-z：65-90
- a-z：97-122
如果使用 char 作為 bitmap 的替代底層數據結構，為了實現字符串的去重需要 char 的長度為多少呢？122/8+1 ⇒ 16。如果使用 int 作為 bitmap 的底層實現，則需要 int 數組的長度為 122/32 + 1 ⇒ 4
1. int 作為底層數據結構
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void dedup(const char* src, char* dst){ unsigned int exists[4] = { 0 }; int i = 0, j = 0; unsigned int mask; char c; while (src[i]) { c = src[i]; mask = 1 << (c % 32); if ((exists[c / 32] & mask) == 0) { dst[j++] = c; exists[c / 32] |= mask; } i++; } dst[j] = '\0';} |
2. 使用 char 作為底層數據結構
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void dedup(const char* src, char* dst){ unsigned char exists[16] = { 0 }; int i = 0, j = 0; unsigned int mask; char c; while (src[i]) { c = src[i]; mask = 1 << (c % 8); if ((exists[c / 8] & mask) == 0) { dst[j++] = c; exists[c / 8] |= mask; } i++; } dst[j] = '\0';} |
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對服務器之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
原文鏈接：https://blog.csdn.net/lanchunhui/article/details/80554725
