194

When browsing the source code of Guava, I came across the following piece of code (part of the implementation of hashCode for the inner class CartesianSet):

int adjust = size() - 1;
for (int i = 0; i < axes.size(); i++) {
    adjust *= 31;
    adjust = ~~adjust;
    // in GWT, we have to deal with integer overflow carefully
}
int hash = 1;
for (Set<E> axis : axes) {
    hash = 31 * hash + (size() / axis.size() * axis.hashCode());

    hash = ~~hash;
}
hash += adjust;
return ~~hash;

Both of adjust and hash are ints. From what I know about Java, ~ means bitwise negation, so adjust = ~~adjust and hash = ~~hash should leave the variables unchanged. Running the small test (with assertions enabled, of course),

for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
    assert i == ~~i;
}

confirms this. Assuming that the Guava guys know what they are doing, there must be a reason for them to do this. The question is what?

EDIT As pointed out in the comments, the test above doesn't include the case where i equals Integer.MAX_VALUE. Since i <= Integer.MAX_VALUE is always true, we will need to check that case outside the loop to prevent it from looping forever. However, the line

assert Integer.MAX_VALUE == ~~Integer.MAX_VALUE;

yields the compiler warning "Comparing identical expressions", which pretty much nails it.

dimo414
  • 47,227
  • 18
  • 148
  • 244
bisgardo
  • 4,130
  • 4
  • 29
  • 38
  • 42
    @dr_andonuts Guava is a pretty standard library to include in a project these days -- I think the advice to run far away is misplaced. – yshavit Apr 19 '15 at 23:19
  • 4
    The assert does not check the edge case `Integer.MAX_VALUE`. Contrast with `-(-Integer.MIN_VALUE) != Integer.MIN_VALUE`. – Franky Apr 20 '15 at 07:04
  • 1
    @Franky You're right with the missing test case, but wrong with the other part as for every `int`, both `-(-x)` and `~(~x)` equal `x`, no matter what. – maaartinus Apr 20 '15 at 08:22
  • 3
    @Franky What maaartinus said. `-Integer.MIN_VALUE` wraps around to `Integer.MIN_VALUE`, so negating that again simply produces `Integer.MIN_VALUE` again. –  Apr 20 '15 at 08:24
  • 2
    @maaartinus, @hvd, thanks for pointing that out. Now I remember that `-x = (~x) + 1`. – Franky Apr 20 '15 at 08:51
  • 7
    @dr_andonuts Trolling? Why run away from things you do not understand. This is what StackOverflow is here for: to help you learn. – Jared Burrows Apr 20 '15 at 14:58
  • @Franky Thanks for pointing out the missing test case, I updated the question accordingly. – bisgardo Apr 20 '15 at 17:45
  • 1
    Now you're missing `Integer.MAX_VALUE`. There's no nice solution, you need either a `long` loop or a `break` at the end. – maaartinus Apr 20 '15 at 18:56
  • @maaartinus The edit was for taking care of that. – bisgardo Apr 21 '15 at 08:19

1 Answers1

246

In Java, it means nothing.

But that comment says that the line is specifically for GWT, which is a way to compile Java to JavaScript.

In JavaScript, integers are kind of like doubles-that-act-as-integers. They have a max value of 2^53, for instance. But bitwise operators treat numbers as if they're 32-bit, which is exactly what you want in this code. In other words, ~~hash says "treat hash as a 32-bit number" in JavaScript. Specifically, it discards all but the bottom 32 bits (since the bitwise ~ operators only looks at the bottom 32 bits), which is identical to how Java's overflow works.

If you didn't have that, the hash code of the object would be different depending on whether it's evaluated in Java-land or in JavaScript land (via a GWT compilation).

yshavit
  • 42,327
  • 7
  • 87
  • 124
  • 2
    This makes sense. It also seems like the JIT compiler will optimize the statements away: when I ran the "test" above, it exited so quickly that it seems like the entire loop was being removed as dead code. – bisgardo Apr 19 '15 at 23:29
  • So GWT is broken, and by default implements integers incorrectly? That's.. sort of scary – harold Apr 20 '15 at 09:15
  • 10
    @harold It's not a GWT thing, it's a JavaScript thing. That's just now numbers work in that language. – yshavit Apr 20 '15 at 12:05
  • 5
    Often the `| 0` (or zero) is used to obtain the same thing (http://stackoverflow.com/questions/7487977/using-bitwise-or-0-to-floor-a-number) – xanatos Apr 20 '15 at 12:46
  • 18
    @yshavit However, it is *not* how numbers work in Java. If GWT doesn't hide the fact that numbers are implemented differently in JS and on the JVM from the user, then it is a poor compiler indeed. – valderman Apr 20 '15 at 12:57
  • @valderman -- somewhat agreed. I don't see a reason why GWT couldn't insert the ~~ sequence for you... – LThode Apr 20 '15 at 13:01
  • 8
    @harold, yeah, it's JavaScript that implements integers incorrectly (there's actually no such thing as an integer type in JavaScript). – Mike G Apr 20 '15 at 13:07
  • 8
    @valderman That's a good point. Adding the `|0` or `~~` sounds like it wouldn't be hard, though I don't know what the performance hit would be (you'd have to add it at every step of every expression). I don't know what the design considerations were. Fwiw, the inconsistency is documented on [GWT's compatibility page](http://www.gwtproject.org/doc/latest/DevGuideCodingBasicsCompatibility.html). – yshavit Apr 20 '15 at 13:19
  • So, at least it's documented. I still consider this incorrect though. The whole idea of GWT is "write java, run js", well now you basically have to "write js in java" in order to avoid bugs like this. Multiplication is going to be particularly sweet.. – harold Apr 20 '15 at 13:29
  • @harold What bug? I've been using GWT for a while and have also done arithmetic, never come across any issues. – Ali Apr 20 '15 at 17:28
  • 1
    @ClickUpvote as far as you know, anyway. It's not that far-fetched that this behavior breaks things, case in point: code from OP, if didn't specifically use the workaround. – harold Apr 20 '15 at 17:32
  • 6
    `hashCode` is weird in that it _deliberately_ courts, or even expects, overflow to happen. The only place you can observe inconsistency is where a normal Java int would overflow, which is not an issue that comes up in most code; it's just relevant in this one weird case. – Louis Wasserman Apr 20 '15 at 18:54
  • 2
    @valderman: crucially, it's *not* a Java compiler and neither does it play one on television. It's a compiler for a language that's a bit (well, a lot) like Java. – Steve Jessop Apr 20 '15 at 20:40
  • ... @Halle Are you sure that you enabled assertions? :P Not disputing the results, just the methodology.. – Riking Apr 21 '15 at 05:08
  • "never come across any issues" -- you could only have truthfully said that before seeing this SO question. – Jim Balter Jul 17 '15 at 19:25