4

I've seen multiple sources (some here, and on the Wikipedia article on bitwise operation) say that using bitshifting to calculate is faster than normal multiplication/division/addition. However, they've also mentioned that that only really applies to older processors, and that most modern processors have made it so the speeds are virtually equal.

How valid is that statement? Is it safe in Java or C# to just use regular math operands? Is using bitshifting as a substitute for those operands really necessary anymore?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131

2 Answers2

9

You just leave this to the compiler. Good compilers know about the hardware that they are targetting. If the compiler knows that bitwise operations are faster, then it can emit code to do it that way. You should always write the human readable code in the most clear fashion, the fashion that correctly expresses the operation being performed. Let the compiler do the rest.

As for whether or not it is still true that bitwise operations can be faster than arithmetic, I believe that they are. Certainly many modern C++ compilers will emit code that uses bitwise operations for arithmetic.

David Heffernan
  • 601,492
  • 42
  • 1,072
  • 1,490
  • Alright thanks for the response. I've seen a few people write code including bitshifting and I was just so confused as to why they didn't just use multiplication. Thank you! –  May 22 '12 at 15:20
  • 6
    If any of my team ever tried to do arithmetic with bitwise operations, then that would result in a very painful code review session! – David Heffernan May 22 '12 at 15:21
  • +1 for the painful code review session =) – pcalcao May 22 '12 at 15:28
  • 2
    I've written code with bitwise operations, but only when I had hard benchmark numbers to demonstrate the improved performance, and only with a very thorough code review session. – Louis Wasserman May 22 '12 at 16:05
  • [Example](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/src-html/com/google/common/math/LongMath.html#line.414): `LongMath.gcd` in Guava. – Louis Wasserman May 22 '12 at 16:11
  • 1
    @Louis There are always special cases and exceptions to any rule. But my guess is that the type of code that is being referred to in this question will be of the form `<<1` to multiply by 2. That just obfuscates code and almost invariably for no benefit. – David Heffernan May 22 '12 at 16:12
  • Absolutely agreed. (And if you make the JIT output the compiled assembly, you'll find that it will, indeed, make those optimizations itself.) – Louis Wasserman May 22 '12 at 16:16
  • I don't have the exact figures at hand, but on current Intel and AMD CPUs, multiplications are in the order 8 to 20 times slower than a bit shift, so in some situations, this may actually matter. More important though is that there is probably no direct correlation between the operator used in a high-level language like Java or C# (*, << or >>) and the op code actually executed by the CPU. – jarnbjo May 24 '12 at 12:53
  • @jarnbjo My experiments with gcc show that it goes to great lengths to reduce multiplications/divisions to combinations of shift operations. – David Heffernan May 24 '12 at 13:11
  • @DavidHefferman: Which is difficult for gcc, unless you know at compile-time on exactly which CPU model the code will be running. If the replacement is too complex and the CPU model has a fast multiplication implementation, the "optimized" version may just as well be slower than using an actual multiplication op code. – jarnbjo May 24 '12 at 13:34
2

I'm not sure what's the scale of the difference between using bitwise operations and and using simple operators on today's architectures and compilers (my guess is... close to none on most problems).

I'm basing my hunch on the fact that most code you write nowadays doesn't really bottleneck on CPU operations, but rather on database access, I/O, network (yes, I'm being redundant here).

The compiler for the JVM, for instance, already optimizes a lot of operations to the architecture where you're running your code, abstracting this necessity away from the developer (that's what it's there for).

One final point I would like to make is... readability counts. No matter what some bitwise operation fans will argue, bitwise operation in the middle of your code are usually much less readable by most developers then simply using standard math.

The cost of understanding the code and the increased probability that someone will introduce a bug when the code needs to be changed makes, IMHO, the risk far surpass the benefits. It's important to write efficient code, but it still has to be readable by humans.

Disclaimer: There might be some domains where the number of mathmatical operations is such that this might become a factor, but this certainly is not the norm.

pcalcao
  • 15,789
  • 1
  • 44
  • 64