I'm really bad at math and I want to do a binary operation

Question

I have the following piece of code:

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

I would like very much to know what the heck it does, but I would be satisfied to know how to build a bool HasHash( int val ) that tells me whether m_Hash has that number or not...

something like this?

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

Answer 1

EDIT to fix the bug that @schnaader found: What it does? This code probably wants to rotate val leftwards (clockwise) by 6 bits and form the ones-complement sum (edit: not the product, as I'd said before) -- the xor -- of that rotated value and the current value of m_Hash to yield a new m_Hash. That new m_Hash will be used the next time AddHash( ) is called.

However, the code as written has a bug: it rotates only the high-order 6 bits of val leftwards, leaving in place the low-order 26 bits of val. The code then xors together three values:

1. the new low-order (old high-order) 6 bits of val;
2. the original, unshifted low-order 26 bits of val; and
3. the current value of m_Hash

leaving the result in m_Hash.

How does it do it? You can just map it out and emulate it:

1. val & 0x3FFFFFF means extract the low-order 26 bits of val.

2. xor those 26 bits with the current value of m_Hash

3. now shift val rightwards such that the low-order 26 bits drop off the low-order end, leaving what used to be the high-order 6 bits of val in the low-order 6 bits of val.

4. Mask with 0x3f to extract only those low-order 6 bits (in case some extraneous bits got shifted into the high order part of val).
5. xor those low-order 6 bits with the current value of m_Hash to give the new m_Hash.

You know that rotating and exclusive-oring are common operations in calculating a hash.

EDIT: @schnaader pointed out the bug in the original code: that code forgot to do the other leg of the rotate: shifting the low-order 26 bits left by 6. To fix that, the code should read something like:

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

As to your HasHash( ) function: you should know that saying

return (m_Hash & val) == 0;

will return TRUE under many conditions, including some you might not want. For example, the function will return TRUE if m_Hash == 0xC0 and val == 0x03.

Answer 2

What the code does

It takes the last 26 bits of val and combines it with m_Hash using XOR. After that, it combines this with the first 6 bits of val. So an integer with 32 bits length will be reduced to 26 bits. According to the pigeonhole principle, this is not reversible.

HasHash function

So you won't be able to create a HasHash function even if you only called AddHash just once, because multiple input values in val will result in the same m_hash value.