6

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.

  • possible duplicate of What are bit operators good for? and of Importance of bitwise thinking – gnat Jun 29 '14 at 18:00
  • 1
    Regarding the provoking SO question: the best suggestion is to stay calm and don't be trolled (by your interviewer or a random question on SO). And as for legitimate use, you have already mentioned some: Java programmers who use colors and graphics (as simple as picking RGB colors) will do a small amount of bit manipulation. This would still apply if the heavy-lifting is done in another language. True "bit hacks" are employed by compilers as in Peephole optimization. – rwong Jun 29 '14 at 20:15
8

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.

  • The part about caches seems out of place. I've never seen a bit hack that uses less memory than the obvious way. If anything, they add lookup tables. Usually they only add bitwise operations, and sometimes (shorter) loops and branches. Occasionally a fast bit hack may make it worthwhile to calculate values on the fly instead of caching them but that too seems rather rare. – user7043 Jun 29 '14 at 18:34
  • Side-channel countermeasure is more an art of machine code obfuscation than optimization. – rwong Jun 29 '14 at 19:59
  • @rwong when you are dealing with Java, you have difficulty getting the degree of machine code obfuscation that one would find in something closer to the metal. What you do have is the ability to avoid branches. For crypto, its not about making it run fast (many times its intended to make it run slow), but to make it run consistently. – user40980 Jun 29 '14 at 20:15
  • @MichaelT: agrees. So it is a bit amazing that while in C/C++ one could at least disable all compiler optimizations for one source file (containing the function), I couldn't even imagine how a Java execution environment (JIT or VM) could give you this kind of control. – rwong Jun 29 '14 at 20:19
  • 1
    @rwong by forcing the system to do things without branching and preforming all of the operations on each piece of data (even if they are null operations). By using the bit version of min (the sample code), the system doesn't know what you are trying to do with those bit operations and so can't optimize out any of those operations. As there are no branches, branch prediction isn't something that one can use to figure out the data. Thus, by careful choice of bit operations, one can avoid the compiler and runtime optimizations that could happen with branches and more straight forward code. – user40980 Jun 29 '14 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.