In Java, why use bit hacks when non-bitwise technique it is more readable?

Question

Is there any legitimate use for bit manipulation hacks in higher-level languages such as Java?

I can see them being useful in speed-sensitive low-level and computation-intensive programs, e.g. graphics processing or crypto functions. I guess that's why all collections of them are in C. However, getting to think about them in terms of higher-level design I cannot think of any point where I would, for example, write the following in a Java program:

r = y ^ ((x ^ y) & -(x < y));

rather than:

r = (x < y) ? x : y;

The first line looks more like an obfuscation than an improvement. And most applications have different kinds of bottlenecks - most commonly networks or disc access, so much so that any potential improvement gained by using a bitwise hack would be so tiny that it is completely ignorable.

This line of thought was provoked by a recent SO question in which someone was asked about a bitwise hack in Java during a interview.

I agree as much as anyone that it's always better to write faster code, but considering that it becomes much less readable, especially by someone not familiar with bit hacks, is there any kind of application in which it is legitimately worth it?

This question is not about bitwise operators in general, but more specifically about bitwise hacks, and even more specifically about bitwise hacks in Java.

By bitwise hack I mean a manipulation that has a trivial and/or obvious implementation, but which can be done slightly faster/better with some clever bitwise manipulation -- which in most cases makes it near-unreadable to someone not used to bitwise hacks.

---

There are similar looking questions: Importance of bitwise thinking and What are bit operators good for? The answers in these questions talk about bit manipulations in general, which yes, have a lot of clear and useful applications; especially in other languages like C. While this may seem similar, my question was about having them versus using the non-bitwise technique in Java. In the other questions this is not addressed at all.

Answer 1

Sometimes, the specification of an algorithm is based on bit operations. This is especially true in crypto work.

Crypto has another attribute to it that is important - that the operation takes exactly the same amount of time no matter what the parameters are. This is to try to avoid leaking any data with timing attacks (there are even attacks based on the sounds the computer makes while doing cryptography).

Thus, for cryptography, it is of paramount importance that the code takes exactly the same amount of time and does the same things. Bitwise operations can play a significant role in that area in that they are not often or easily optimized by the compiler. With things were you can short circuit the expression or decide to follow one branch or another that has a different timing these are avenues of timing attacks.

The code

if(x < y) {
  r = x;
} else {
  r = y;
}

Can take different amounts of time based on the branch prediction and branching itself. While

r = y ^ ((x ^ y) & -(x < y));

takes exactly the same amount of time each time through the code. Branch prediction doesn't play a role because there are no branches in there.

---

With graphics work, there are similar areas of concern. Some systems (especially older ones) had the CRT refresh tied with the clock cycle (for example the Amiga had 4 clock cycles per refresh line). This meant that when you wrote code that was specifically tailored to the graphics of the system you knew exactly where the screen refresh was and could improve the appearance of the system. This isn't quite as much of an issue now (the GForce GTX 780 can do 40,0000 operations per pixel per frame refresh), but it is something to be considered.

Secondly, there's also deep magic within fitting things into various caches on various systems. Doing as much as possible with the cache can improve that. This often means doing bitwise work rather than trying to load and store things or send them off to the ALU.

In Java, this can be difficult to know for certain, but again, maintaining a consistent frame rate based on the scene is something that is often very important with graphics.

Answer 2

Note that this:

r = y ^ ((x ^ y) & -(x < y));

Is not valid in Java, since you cannot treat booleans like (x < y) and integers interchangeably like you can in C.

But even if I were using C, in the example provided in the question, I would still definitely use:

r = (x < y) ? x : y;

Because a good compiler should optimize that into a branchless version if necessary.

Another example that comes up often is writing x >> 4 or x >>> 4 instead of x / 16 (or any power of 2), as an optimization. There is more merit here, since x / 16, x >> 4, and x >>> 4 are all semantically different for x < 0. Depending on whether I want a truncating division, floor division, or a logical shift based on the context, I would choose the appropriate option.

In cases where there is no difference, I would be more inclined to choose the shift option because Java lacks unsigned types so the Java compiler cannot necessarily prove that x >= 0 even if you know that as a the programmer, hindering optimizations because the compiler might still handle x < 0 cases. Also, a single shift is much more widely understood than the more obscure branchless min implementation, so I would be less reluctant to use shifts in this case.

You would want to balance readability you are willing to sacrifice for speed. As mentioned with the min implementation in the question, I doubt the obfuscated branchless version is actually faster than the ?: especially in Java since you would need a ?: anyway to convert x < y into 1 or 0. And even if that were faster, the speedup would be negligible compared to the added complexity.

But if I had a case where I could write a loop or otherwise O(n) operation, but I could replace that with a few O(1) bitwise ops, I would go for that. If you are still concerned about the readability of the bitwise versions, you should still document them explaining what they do, even if they are not clear how they work to someone new to bitwise ops.

But in the end, bitwise operators are standard parts of the language, so understanding at least the gist of how they work is a reasonable expectation for readers, so you should not avoid them altogether just for the sake of avoiding them, when they would genuinely allow for a clean solution to a problem.

Answer 3

To answer the question asked: You replace perfectly fine working and readable code with unreadable code if that has advantages. For example a speed gain that is so extreme that the cost of writing new code, then testing and maintaining the new code is justified. The speed of the original code should have been measured before any changes. And very often you can write faster readable code. That was often my experience, for example replacing supposedly ultra fast assembler code with C or C++ code that was actually faster.

Some people do this thing because they think it makes them look clever - it doesn’t.