2

次のコードがあります。

    public void AddHash( int val )
    {
        m_Hash ^= (val & 0x3FFFFFF);
        m_Hash ^= (val >> 26) & 0x3F;
    }

bool HasHash( int val )それが一体何をするのか知りたいのですが、 m_Hash がその数を持っているかどうかを教えてくれるa を構築する方法を知っていれば満足です...

このようなもの？

    public bool HasHash( int val )
    {
        return (m_Hash & val) == 0;
    }
4

2 に答える 2

3

コードの機能

の最後の 26 ビットを取得し、 XORを使用してval結合します。その後、これを の最初の 6 ビットと結合します。したがって、32 ビット長の整数は 26 ビットに削減されます。鳩の巣の原理によると、これは元に戻せません。m_Hashval

HasHash 関数

複数の入力値が同じ値になるため、一度HasHashだけ呼び出しても関数を作成することはできません。AddHashvalm_hash

于 2011-04-30T19:01:42.790 に答える
3

@schnaaderが見つけたバグを修正するための編集：それは何をしますか？このコードは、おそらく左方向 (時計回り) に 6 ビット回転させ、1 の補数の合計(編集: 前に述べたように、積ではありません) を形成することを望んでいます。新しい を生成します。その新しいものは、次に呼び出されたときに使用されます。valm_Hashm_Hashm_HashAddHash( )

ただし、記述されたコードにはバグがあります。 の上位 6 ビットのみをval左に回転し、 の下位 26 ビットをそのまま残しますval。次に、コードは 3 つの値を xor します。

  1. の新しい下位 (古い上位) 6 ビットval。
  2. ;の元のシフトされていない下位 26 ビットval。と
  3. の現在の値m_Hash

結果を に残しm_Hashます。

それはどのように行うのですか？それをマップしてエミュレートするだけです：

  1. val & 0x3FFFFFFの下位 26 ビットを抽出することを意味しvalます。

  2. xorの現在の値を持つそれらの 26 ビットm_Hash

  3. の下位 6 ビットに の上位 6 ビットだったvalものが残るように、下位 26 ビットが下位の端から削除されるように右にシフトします。valval

  4. でマスクし0x3fて、これらの下位 6 ビットのみを抽出します (無関係なビットが の上位部分にシフトされた場合val)。
  5. xorの現在の値を持つ下位 6 ビットはm_Hash、新しい を提供しm_Hashます。

ハッシュの計算では、回転と排他的論理和が一般的な操作であることをご存知でしょう。

編集: @schnaader は、元のコードのバグを指摘しました: そのコードは、回転のもう一方の行を実行するのを忘れていました: 下位 26 ビットを左に 6 シフトします。それを修正するには、コードは次のように読む必要があります:

public void AddHash( int val )
{
  m_Hash ^= ((val & 0x3FFFFFF) << 6);
  m_Hash ^= (val >> 26) & 0x3F;
}

あなたのHasHash( )機能に関して：あなたはそのことわざを知っておくべきです

return (m_Hash & val) == 0;

は、望ましくない場合も含め、多くの条件下で TRUE を返します。たとえば、関数は と の場合に TRUE を返しm_Hash == 0xC0ますval == 0x03。

于 2011-04-30T19:05:03.747 に答える