Doubling a number - shift left vs. multiplication

Question

What are the differences between

int size = (int)((length * 200L) / 100L); // (1)

and

int size = length << 1; // (2)

(length is int in both cases)

I assume both code snippets want to double the length parameter.

I'd be tempted to use (2) ... so are there any advantages for using (1)? I looked at the edge cases when overflow occurs, and both versions seem to have the same behavior.

Please tell me what am I missing.

Answer 1

This sounds like premature optimizations. The plus for just doing length * 2 is that the compiler most certainly optimizes this and it's easier to maintain.

Answer 2

Below link gives detailed discussion on the same with moral being that computer does not perform multiplication by calling addition repeatedly.

http://stackoverflow.com/questions/3060064/how-computer-multiplies-2-numbers

So the answer of computer using repeated addition for multiplication is wrong.

Answer 3

And here is the 3rd option:

int size = length * 2; // Comment explaining what is 2 or what means this multiplication

And this must be the best option. As it is readable and easy to understand what you want to do. As for performance, compilers are generating pretty optimized code, so no need to worry for such a simple operation. If you have any concerns concerning overflow you can use checked block.

EDIT As mentioned by many others just use any meaningful variable instead of 2 here.

Answer 4

With any modern compiler left shift by 1 or multiplying by 2 will generate the same code. It's probably going to be an add instruction adding the number to itself, but it depends on your target.

On the other hand, doing (x*200)/100 will not be the same as doubling the number since the first multiplication may overflow, so this cannot be optimized safely to doubling the number.

Answer 5

Which is more readable to your average programmer:

int size = length * 2;
int size = length << 1;

Unless they come from a strong C++ bit tweaking background I'd wager your average programmer knows immediately what the first line does (it even has the number "2" for "double" in it) but would have to stop and pause for the second line.

In fact I'd feel inclined to comment the second line explaining what it does which seems redundant when you can get the code do the talking as in the first line.

Answer 6

What do 200L and 100L represent? Seems to me you are using magic numbers. You should try to write your program in such a way that it describes its intent as good as possible; making it as readable as possible. Using named constants for these values instead of magic numbers is a good way of doing this. Also extracting the calculation in its own well named method helps too. When you do this, you will immediately see that there is no way of rewriting it to x << 1. Not because the results will be different, but because maintainability will suffer. When you write code like x << 1, the next programmer has no idea what that actually means and it will increase the famous WTFs per minute:

---

I think your code should look more like this:

int size = CalculateThingSize(length);

private static int CalculateSizeOfThing(int length)
{
    const long TotalArraySize = 200L;
    const long BytesPerElement = 100L;

    return (length * TotalArraySize) / BytesPerElement;
}

Of course the names of these const values are a wild guess :-)

Answer 7

The idea that << is faster than multiplication is reasoning as though the .NET jit compiler is actually a poorly optimized C compiler written in the 1970's. Even if it were true, the difference would be measured in picoseconds at this point in time, even if there were a difference, which there probably is not.

Write code so that it is easy to read. Let the compiler take care of the pico-optimizations. Optimize your code based on profiling realistic scenarios, not on second guessing what the compiler will generate.

Furthermore, the shift operators do not have the same semantics as multiplication. For example, consider the following sequence of edits:

Original program by Jill:

int x = y * 2;

Edit by Bob: Silly Jill, I'll make this "faster":

int x = y << 1;

Edit by Larry the Intern: Oh, we have a bug, we're off by one, let me fix that:

int x = y << 1 + 1;

and Larry has just introduced a new bug. y * 2 + 1 is different than y << 1 + 1; the latter is actually y * 4.

I have seen this bug in real live production code. It is very easy to mentally get into the mindset that "shifting is multiplication" and forget that shifting is lower precedence than adding, whereas multiplication is higher precedence.

I have never once seen someone get arithmetic precedence wrong who multiplied by two by writing x * 2. People understand the precedence of + and *. Lots of people forget what the precedence of shifting is. Are the picoseconds you don't actually save worth any number of potential bugs? I say no.

Answer 8

It's interesting that most of the answers argue that the compiler will optimise a multiply by a power of 2 into a bitshift. It's obvious that none of the responders have actually tried compiling a bitshift versus a multiply to see what the compiler actually produces.

This is purely an academic exercise; as just about everyone has pointed out, the multiply is easier to read (though quite why the "*200L / 100L" part is in there is anyone's guess - that just serves to obfuscate things). It's also pretty obvious that replacing a multiply with a bitshift in C# isn't going to have any significant performance increase, even in tight loops. If you need that kind of optimisation, you're using the wrong platform and language to start with.

Let's see what happens when we compile a simple program with CSC (the C# compiler) included with Visual Studio 2010 with optimisations enabled. Here's the first program:

static void Main(string[] args)
{
    int j = 1;

    for (int i = 0; i < 100000; ++i)
    {
        j *= 2;
    }
}

Using ildasm to decompile the resultant executable gives us the following CIL listing:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       23 (0x17)
  .maxstack  2
  .locals init ([0] int32 j,
           [1] int32 i)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.1
  IL_0004:  br.s       IL_000e
  IL_0006:  ldloc.0
  IL_0007:  ldc.i4.2
  IL_0008:  mul
  IL_0009:  stloc.0
  IL_000a:  ldloc.1
  IL_000b:  ldc.i4.1
  IL_000c:  add
  IL_000d:  stloc.1
  IL_000e:  ldloc.1
  IL_000f:  ldc.i4     0x186a0
  IL_0014:  blt.s      IL_0006
  IL_0016:  ret
} // end of method Program::Main

Here's the second program:

static void Main(string[] args)
{
    int j = 1;

    for (int i = 0; i < 100000; ++i)
    {
        j <<= 1;
    }
}

Decompiling this gives us the following CIL listing:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       23 (0x17)
  .maxstack  2
  .locals init ([0] int32 j,
           [1] int32 i)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.1
  IL_0004:  br.s       IL_000e
  IL_0006:  ldloc.0
  IL_0007:  ldc.i4.2
  IL_0008:  shl
  IL_0009:  stloc.0
  IL_000a:  ldloc.1
  IL_000b:  ldc.i4.1
  IL_000c:  add
  IL_000d:  stloc.1
  IL_000e:  ldloc.1
  IL_000f:  ldc.i4     0x186a0
  IL_0014:  blt.s      IL_0006
  IL_0016:  ret
} // end of method Program::Main

Note the difference at line 8. The first version of the program uses a multiply (mul), whilst the second version uses a left-shift (shl).

Quite what the JIT does to it when the code is executed I'm not sure, but the C# compiler itself demonstrably does not optimise multiplies by powers of two into bitshifts.

Answer 9

To answer your actual question, there appears to be no behavior differences between those two snippits of code, when length is a non-negative int and the code text is within an unchecked context.

Within a checked context (int.MaxValue * 200L) will never overflow because the result easily fits within a long. (int)((length * 200L) / 100L will only overflow when length * 2 overflows. Under no circumstances will a shift operator overflow. Therefore, the code snippits behave differently within a checked context.

If length is negative, then the shift operation will produce incorrect results, while the multiplication will work correctly. Therefore, the two code snippits are different if the length variable is allowed to be negative.

(Contrary to popular opinion x << 1 is not the same as x * 2. They are only the same if x is an unsigned integer.)

Answer 10

When I see the idiom:

int val = (someval * someConstant) / someOtherConstant;

I think that the code's intent is to do scaling in some manner. It could be manual fixed point code or it could be avoiding problems with integer division. A concrete example:

int val = someVal * (4/5); // oops, val = 0 - probably not what was intended

or written to avoid going back and forth to floating point:

int val = (int)(someVal * .8); // better than 0 - maybe we wanted to round though - who knows?

when I see this idiom:

int val = someVal << someConstant;

I briefly wonder if the individual bits in someVal have some deeper meaning that requires the shifting and then I start looking at surrounding context to understand why it was done this way.

The thing to remember is that when you are writing code that has something like this:

int val = expr;

that there are an infinite number of ways to create expr such that val will always have the same value. It is important to consider what intent you are expressing in expr for those who will follow.