Je suis vraiment mauvais en maths et je veux faire une opération binaire
-
27-10-2019 - |
Question
Je le morceau de code suivant:
public void AddHash( int val )
{
m_Hash ^= (val & 0x3FFFFFF);
m_Hash ^= (val >> 26) & 0x3F;
}
Je voudrais bien savoir ce que le diable, il fait, mais je serais satisfait de savoir comment construire un bool HasHash( int val )
qui me dit si m_Hash a ce nombre ou non ...
quelque chose comme ça?
public bool HasHash( int val )
{
return (m_Hash & val) == 0;
}
La solution
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:
- the new low-order (old high-order) 6 bits of
val
; - the original, unshifted low-order 26 bits of
val
; and - 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:
val & 0x3FFFFFF
means extract the low-order 26 bits ofval
.xor
those 26 bits with the current value ofm_Hash
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 ofval
in the low-order 6 bits ofval
.- Mask with
0x3f
to extract only those low-order 6 bits (in case some extraneous bits got shifted into the high order part ofval
). xor
those low-order 6 bits with the current value ofm_Hash
to give the newm_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
.
Autres conseils
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.