Advanced Data Structure and Application Example of String Reduplication Using bitmap

bitmap is an array of single elements boolean (0/1, 0 for nonexistent, 1 for present).

If C/C++ does not have a native boolean type, int or char can be used as bitmap if we want to determine if a character (char) has ever occurred

Using int as the underlying data structure of bitmap, bitmap is an int array, with an int length of 32 bit bits.

c / 32 ⇒Number of ints in bitmap c% 32 ⇒The number of bit bits in an int in bitmap;

Using char as the underlying data structure of bitmap, bitmap is the char array, and one char is 8 bit bits long.

c / 8 ⇒Number of chars in bitmap c% 8 ⇒The number of bit bits in an char in bitmap;

ASCII

A-Z:65-90 a-z:97-122

If you use char as an alternative underlying data structure to bitmap, what length does char need to be in order to achieve string redundancy?122/8+1 &868658;16.If int is used as the underlying implementation of bitmap, the length of the int array is 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';
}

summary