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);

2 番目の疑問は、文字列が長すぎるか、Unicode (2 バイト幅の文字) が含まれている場合に機能するかどうかです。

4

2 に答える 2

1

このアルゴリズムは、ASCII 文字ごとに 1 ビットを使用して、セットへの存在を示します。したがって、少なくとも英語の小文字、つまり 26 個の小文字と、連続する ASCII コードで機能します。a= 000001、b= 000010、c= 000100 など。「aacaaccc」と「ac」と「ca」は、a と c の出現回数に関係なく、すべて 000101 にエンコードされます。したがって、文字列の長さは問題ではありません。

あなたは2バイト文字について正しいです。ラテン文字セットも問題を引き起こしますが、大文字と小文字が混在する問題は、5 番目のビット (32) をマスクして大文字に変換する (または 32 と論理和をとって小文字に変換する) ことで簡単に解決できます。

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'、ここ|で はビットごとの OR 演算子です。

于 2012-11-08T07:16:45.507 に答える
1

これはビット マスキングと呼ばれます。ここで、チェッカーはビット マスクです。

最初の式:if((checker&(1<<val))>0)はビットを取得し、2 番目の式checker|=(1<<val)はビットを設定します。

左シフト演算子は 2^val だけ上げます。つまり、001000 ('d' の場合) のようなものになります。

& 演算子は、チェッカーの i 番目のビットと新しい val(001000) の両方が 1 の場合は常に true を返します。したがって、その文字が既にカバーされているかどうかがわかります。

| | 演算子は単に i 番目のビットを 1 に設定します。そのため、あるインスタンス チェッカーで 010000 だった場合、今では 011000 になります。

于 2012-11-08T07:25:52.413 に答える