How can x & 0xffffffff produce more than 32 bits?


The short summary

I would expect n & 0xffffffff to yield a 32-bit number, not more. But it's yielding a 64-bit number. Why?

The details

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 0x811d68ec0c35c4, 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 b and 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 int vs. long data types of intermediate results, and possibly with negative numbers being represented using the high bit?

asked on Stack Overflow May 12, 2020 by LarsH

1 Answer


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 long:

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, 0xffffffff, from int to 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.

answered on Stack Overflow May 12, 2020 by LarsH • edited May 16, 2020 by LarsH

User contributions licensed under CC BY-SA 3.0