1

在一次采访中，我被要求检查天气给定的字符串是否有重复的字符。谷歌搜索这个问题，我了解到一个使用位操作的问题。

bool check(char*name)
{
     int i;
     int checker=0;
     for(i=0;name[i]!=0;i++)
     {
        int val=name[i]-'a';
        if((checker&(1<<val))>0)return false;
          checker|=(1<<val);
     }
     return true;
 }

我检查了这段代码，它工作正常。但我不明白这一行背后的逻辑。

> if((checker&(1<<val))>0)return false;
>               checker|=(1<<val);

第二个疑问是，如果字符串太长或包含 Unicode（2 字节宽的字符），这会起作用吗？

4

2 回答 2

1

该算法使用每个 ascii 字符 1 位来指示集合的存在。所以它至少适用于英文小写字母——其中 26 个和连续的 ascii 代码。a= 000001, b= 000010, c= 000100 等等。不管 a 和 c 出现的次数如何，'aacaaccc' 和 'ac' 和 'ca' 都将编码为 000101。因此字符串长度无关紧要。

您对 2 字节字符是正确的。拉丁字符集也会引起问题，但混合大小写（大写和小写）的问题可以通过屏蔽第 5 位 (32) 以转换为大写（或与 32 进行 oring 以转换为小写）来轻松解决。

ASCII 字符表为所有字符分配一个整数：

@ = 64 = 01**0**00000   ...  
A = 65 = 01**0**00001   ...   a =  97 = 01**1**00001
B = 66 = 01**0**00010   ...   b =  98 = 01**1**00010 
.. 
Z = 90 = 01**0**11010   ...   z = 122 = 01**1**11010

大写和小写字符仅在该特定位上有所不同，'a' - 32 == 'A'或者反过来：'B' + 32 == 'b'or 'B' | 32 == 'b'，其中|是按位或运算符。

于 2012-11-08T07:16:45.507 回答
1

这称为位掩码。这里检查器是位掩码。

第一个表达式:if((checker&(1<<val))>0)获取位，第二个表达式checker|=(1<<val)设置位。

左移运算符将 2^val 提高。所以你有类似 001000 的东西（对于 'd'）。

只要检查器的第 i 位和新的 val(001000) 均为 1，& 运算符就会返回 true。因此，您知道该字符是否已被覆盖。

该| 运算符只需将第 i 位设置为 1 。因此，如果在某些情况下检查器是 010000，现在它变为 011000。

于 2012-11-08T07:25:52.413 回答