高度なデータ構造と応用——bitmapを使用して文字列の重み付けを行う

bitmapは、単一要素がboolean(0/1、0は未出現、1は既に出現)の配列である.
C/C++にオリジナルのbooleanタイプがない場合は、intまたはcharをbitmapとして使用できます.ある文字(char)が現れたかどうかを判断する場合は、

はintをbitmapの下位データ構造として用いる、bitmapはint配列であり、1つのint長は32ビットビットであり、

c/32⇒bitmapの数番目のint

c%32⇒bitmapのあるintのうちの何番目のbitビットか;

はcharをbitmapの下位データ構造として使用し、bitmapはchar配列であり、1つのchar長は8つのbitビットビットである.

c/8⇒bitmapの何番目のchar

c%8⇒bitmapの中のあるcharの中の何番目のbit位;

ASCII

A-Z:65-90

a-z:97-122

bitmapの代わりにcharを下位データ構造として使用する場合、文字列の重み付けを実現するためにcharの長さはどのくらいですか?122/8+1 ⇒ 16.bitmapの下位層としてintを用いる場合、int配列の長さは122/32+1⇒4である必要がある
1.intを下位データ構造とする

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を下位データ構造として使用

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://www.cnblogs.com/mtcnn/p/9420961.html