Is shifting bits faster than multiplying and divid

Question

Shifting bits left and right is apparently faster than multiplication and division operations on most, maybe even all, CPUs if you happen to be using a power of 2. However, it can reduce the clarity of code for some readers and some algorithms. Is bit-shifting really necessary for performance, or can I expect the compiler or VM to notice the case and optimize it (in particular, when the power-of-2 is a literal)? I am mainly interested in the Java and .NET behavior but welcome insights into other language implementations as well.

Answer 1

If the compiler (compile-time constant) or JIT (runtime constant) knows that the divisor or multiplicand is a power of two and integer arithmetic is being performed, it will convert it to a shift for you.

Answer 2

Humans are wrong in these cases.

99% when they try to second guess a modern (and all future) compilers.
99.9% when they try to second guess modern (and all future) JITs at the same time.
99.999% when they try to second guess modern (and all future) CPU optimizations.

Program in a way that accurately describes what you want to accomplish, not how to do it. Future versions of the JIT, VM, compiler, and CPU can all be independantly improved and optimized. If you specify something so tiny and specific, you lose the benefit of all future optimizations.

Answer 3

I would ask "what are you doing that it would matter?". First design your code for readability and maintainability. The likelyhood that doing bit shifting verses standard multiplication will make a performance difference is EXTREMELY small.

Answer 4

According to the results of this microbenchmark, shifting is twice as fast as dividing (Oracle Java 1.7.0_72).

Answer 5

This is an analysis of the benchmark done by from Savvas Dalkitsis. Although this test checks speed of multiplication over bit shifting, the values used are not the same, check code below in C# which displays the values)

for (int i = 0, j = 1, k = 1; i < 10; i++)
{
  j = j * 2;
  k <<= 2;
  Console.WriteLine("{0} {1}", j, k);
}

The equivalent code of Savvas Dalkitsis example with the values displayed in C# will be

    public static void Main(String[] args)
    {
        for (int i = 0, j = 1, k = 1; i < 10; i++)
        {
            j = j * 2; k <<= 2;
            Console.WriteLine("{0} {1}", j, k);
        }
        Console.WriteLine("-----------------------------------------------");


        DateTime before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a *= 2;
        }
        DateTime after = DateTime.Now;

        Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds");

        before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a = a << 1;
        }
        after = DateTime.Now;
        Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds");
        Console.ReadKey();
    }

Answer 6

Most compilers today will do more than convert multiply or divide by a power-of-two to shift operations. When optimizing, many compilers can optimize a multiply or divide with a compile time constant even if it's not a power of 2. Often a multiply or divide can be decomposed to a series of shifts and adds, and if that series of operations will be faster than the multiply or divide, the compiler will use it.

For division by a constant, the compiler can often convert the operation to a multiply by a 'magic number' followed by a shift. This can be a major clock-cycle saver since multiplication is often much faster than a division operation.

Henry Warren's book, Hacker's Delight, has a wealth of information on this topic, which is also covered quite well on the companion website:

• http://www.hackersdelight.org/

See also a discussion (with a link or two ) in:

• Reading assembly code

Anyway, all this boils down to allowing the compiler to take care of the tedious details of micro-optimizations. It's been years since doing your own shifts outsmarted the compiler.