I would expect
n & 0xffffffff to yield a 32-bit number, not more. But it's yielding a 64-bit number. Why?
In an Android (Java) app I have the following line of code:
hash = ((hash ^ b) * FNV_PRIME) & 0xffffffff;
When logging the value of
hash after this step, I get values like
0x342d586144387f57, etc. which are obviously more than 32 bits can hold. They're 64-bit numbers.
hash is of type
long. I could give more details about
FNV_PRIME, but that seems irrelevant to the question. No matter what the value of
((hash ^ b) * FNV_PRIME) is, when we bitwise-AND it with
0xFFFFFFFF, a 32-bit number, we should end up with all zeroes except for the least significant 32 bits. Right?
Is there something implicit going on here with
long data types of intermediate results, and possibly with negative numbers being represented using the high bit?
OK I seem to have found a solution. And I'm going to guess at why it worked. If someone can shed more light on this I'd be happy to hear it.
The fix: add an
L to the hex literal on the right side of the
& to mark it as a
hash = ((hash ^ b) * FNV_PRIME) & 0xffffffffL;
I tested this and it worked: the code now produces only 32-bit values.
So what was wrong and why did that fix it?
The left side of the
& is a
long value, because
hash is a
long (and so is FNV_PRIME but that shouldn't matter). For
& to do its job, it needs a its operands to be of the same type. So it automatically promotes the right side value,
long. Since Java types are signed,
0xffffffff is interpreted as -1, which as a
long would be
0xffffffffffffffff. So the above line ends up doing the equivalent of
hash = ((hash ^ b) * FNV_PRIME) & 0xffffffffffffffff;
and that's how I ended up getting 64-bit values from it.
When I instead made the right operand
0xffffffffL, it was already a
long and didn't need to be promoted, so it didn't get interpreted as a negative number because of the high bit. To put it another way,
0xffffffffL is equivalent to
0x00000000ffffffffL, so the high bit was not set.
What's the moral of this story?
Well I could use help with that. Some ideas:
Thoroughly understand how Java decides what data types to use to represent numbers at every intermediate stage throughout every computation. Ugh, that sounds hard, especially when most things "work fine" most of the time.
Just muddle through until something doesn't work, and then trace it with a debugger in increasing detail until you find the problem. This assumes that if a program fails, it will fail while still in the developer's hands.
Good & thorough unit testing. :-) Not sure if I would have designed a test that would have detected this problem, e.g. a test to assert that the return value of my function was no more than 32 bits long.
Pay careful attention to compiler warnings in the IDE. I didn't notice it until late in the game, but eventually I saw that Android Studio had a warning that said:
'hash = ((hash ^ b) * FNV_PRIME) & 0xffffffff' can be replaced by 'hash = ((hash ^ b) * FNV_PRIME)'
If I had read that earlier I would have been very puzzled, but it would have given me a good clue about the problem.
User contributions licensed under CC BY-SA 3.0