字符串去重，bitmap操作

liqingfang

将类似aaabbccdabgf这样的去重为abcdgf
下面是算法设计：

int main()
{
  int i;
  char *source = "aaabbccdabgf";  
  
  char *dest;
  char *temp;

  unsigned int bitmap[8] = {0,0,0,0,0,0,0,0};
  unsigned char c;
  unsigned int mask;

  dest = (char*)malloc(strlen(source));
  temp = dest;

  printf("Before %s\n", source);
  i=0;
  while(source[i])
  {
    c = source[i];
    mask = 1 << (c % 32);
    if ((bitmap[c/32] & mask) == 0)   
    {
      *temp++ = source[i];
      bitmap[c/32] |= mask;
    }
    i++;
  }
  *temp = '\0';
   
  printf("After %s\n", dest);
}

不明白为while循环内部的操作，望大牛们指点！@

liqingfang

先自己顶下，哈哈

lenky0401

while(source[i])  //循环处理每个字符
   {
     c = source[i];  //当前待处理字符
     mask = 1 << (c % 32);  //当前字符对应的到某一bit位
     // 除以32是因为一个int类型有32个bit，注意bitmap是int数组
     if ((bitmap[c/32] & mask) == 0)   //比较，没有出现过？
     {
       *temp++ = source[i];  //转存到temp变量内
       bitmap[c/32] |= mask;  //对应的标记置位
     }
     i++;
   }

代码还有很多细节问题

lenky0401

我说的细节问题是比如malloc没有判空，无关紧要。{:3_185:}

liqingfang

回复 3# lenky0401

多谢楼上进行代码注释，不过还是没理解，mask = 1 << (c % 32); 为什么对32进行取模操作后进行左移1位，也就是x2

edgar51774

回复 5# liqingfang


    左移为了这个 bitmap[c/32] & mask

liqingfang

回复 6# edgar51774


    可不可以详细些？

liqingfang

{:3_205:}

KBTiller

回复  lenky0401

多谢楼上进行代码注释，不过还是没理解，mask = 1 << (c % 32); 为什么对32进行取模操作后进行左移1位，也就是x2liqingfang 发表于 2011-06-28 09:45

    这个你理解有误
    不是左移1位
    是1左移若干位

KBTiller

代码的核心思想是
unsigned int bitmap[8] = {0,0,0,0,0,0,0,0};
一共有 8*sizeof bitmap =256 bits
用这256位记录256个数(unsigned char c的范围)是否出现过
比如65('A') 出现
就把第65位写为1
bitmap的第65位显然应该记录在bitmap[2]中（bitmap[0]，bitmap[1]记录了64位）
其他就没什么好说的了吧