bitmap is an array with a single element boolean (0/1, 0 means not appearing, 1 means already appearing).
If C/C++ does not have a native boolean type, you can use int or char as a bitmap. If we want to determine whether a character (char) has appeared
Use int as the underlying data structure of bitmap, bitmap is an int array, with an int length of 32 bit bits.
- c/32 ⇒ how many ints in bitmap
- c % 32 ⇒ Which bit bit in an int in bitmap;
Use char as the underlying data structure of bitmap, bitmap is a char array, with a char length of 8 bits;
- c/8 ⇒How many chars in bitmap
- c % 8 ⇒ Which bit bit in a char in a bitmap;
ASCII
- A-Z：65-90
- a-z：97-122
If char is used as an alternative to the underlying data structure of bitmap, what is the length of char in order to achieve string deduplication? 122/8+1 ⇒ 16. If you use int as the underlying implementation of bitmap, you need the length of the int array to be 122/32 + 1 ⇒ 4
1. int as the underlying data structure
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. Use char as the underlying data structure
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';
}
Summarize
The above is the entire content of this article. I hope that the content of this article has certain reference value for your study or work. Thank you for your support. If you want to know more about it, please see the relevant links below