Which is better option to use for dividing an integer number by 2?

Which of the following techniques is the best option for dividing an integer by 2 and why?

Technique 1:

x = x >> 1;

Technique 2:

x = x / 2;

Here x is an integer.

Use the operation that best describes what you are trying to do.

• If you are treating the number as a sequence of bits, use bitshift.
• If you are treating it as a numerical value, use division.

Note that they are not exactly equivalent. They can give different results for negative integers. For example:

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

Does the first one look like dividing? No. If you want to divide, use x / 2. Compiler can optimise it to use bit-shift if possible (it's called strength reduction), which makes it a useless micro-optimisation if you do it on your own.

To pile on: there are so many reasons to favor using x = x / 2; Here are some:

• it expresses your intent more clearly (assuming you're not dealing with bit twiddling register bits or something)

• the compiler will reduce this to a shift operation anyway

• even if the compiler didn't reduce it and chose a slower operation than the shift, the likelihood that this ends up affecting your program's performance in a measurable way is itself vanishingly small (and if it does affect it measurably, then you have an actual reason to use a shift)

• if the division is going to be part of a larger expression, you're more likely to get the precedence right if you use the division operator:

  x = x / 2 + 5;
  x = x >> 1 + 5;  // not the same as above
  

• signed arithmetic might complicate things even more than the precedence problem mentioned above

• to reiterate - the compiler will already do this for you anyway. In fact, it'll convert division by a constant to a series of shifts, adds, and multiplies for all sorts of numbers, not just powers of two. See this question for links to even more information about this.

In short, you buy nothing by coding a shift when you really mean to multiply or divide, except maybe an increased possibility of introducing a bug. It's been a lifetime since compilers weren't smart enough to optimize this kind of thing to a shift when appropriate.

> Which one is the best option and why for dividing the integer number by 2?

Depends on what you mean by best.

If you want your colleagues to hate you, or to make your code hard to read, I'd definitely go with the first option.

If you want to divide a number by 2, go with the second one.

The two are not equivalent, they don't behave the same if the number is negative or inside larger expressions - bitshift has lower precedence than + or -, division has higher precedence.

You should write your code to express what its intent is. If performance is your concern, don't worry, the optimizer does a good job at these sort of micro-optimizations.

Just use divide (/), presuming it is clearer. The compiler will optimize accordingly.

I agree with other answers that you should favor x / 2 because its intent is clearer, and the compiler should optimize it for you.

However, another reason for preferring x / 2 over x >> 1 is that the behavior of >> is implementation-dependent if x is a signed int and is negative.

From section 6.5.7, bullet 5 of the ISO C99 standard:

> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has > an unsigned type or if E1 has a signed type and a nonnegative value, > the value of the result is the integral part of the quotient of E1 / > 2^E2. If E1 has a signed type and a negative value, the resulting value > is implementation-defined.

x / 2 is clearer, and x >> 1 is not much faster (according to a micro-benchmark, about 30% faster for a Java JVM). As others have noted, for negative numbers the rounding is slightly different, so you have to consider this when you want to process negative numbers. Some compilers may automatically convert x / 2 to x >> 1 if they know the number can not be negative (even thought I could not verify this).

Even x / 2 may not use the (slow) division CPU instruction, because some shortcuts are possible, but it is still slower than x >> 1.

(This is a C / C++ question, other programming languages have more operators. For Java there is also the unsigned right shift, x >>> 1, which is again different. It allows to correctly calculate the mean (average) value of two values, so that (a + b) >>> 1 will return the mean value even for very large values of a and b. This is required for example for binary search if the array indices can get very large. There was a bug in many versions of binary search, because they used (a + b) / 2 to calculate the average. This doesn't work correctly. The correct solution is to use (a + b) >>> 1 instead.)

Knuth said: > Premature optimization is the root of all evil.

So I suggest to use x /= 2;

This way the code is easy to understand and also I think that the optimization of this operation in that form, don't mean a big difference for the processor.

Take a look at the compiler output to help you decide. I ran this test on x86-64 with
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Also see compiler outputs online at godbolt.

What you see is the compiler does use a sarl (arithmetic right-shift) instruction in both cases, so it does recognize the similarity between the two expressions. If you use the divide, the compiler also needs to adjust for negative numbers. To do that it shifts the sign bit down to the lowest order bit, and adds that to the result. This fixes the off-by-one issue when shifting negative numbers, compared to what a divide would do.
Since the divide case does 2 shifts, while the explicit shift case only does one, we can now explain some of the performance differences measured by other answers here.

C code with assembly output:

For divide, your input would be

int div2signed(int a) {
  return a / 2;
}

and this compiles to

    movl    %edi, %eax
    shrl    $31, %eax            # (unsigned)x >> 31
    addl    %edi, %eax           # tmp = x + (x<0)
    sarl    %eax                 # (x + 0 or 1) >> 1  arithmetic right shift
    ret

similarly for shift

int shr2signed(int a) {
  return a >> 1;
}

with output:

    sarl    %edi
    movl    %edi, %eax
    ret

Other ISAs can do this about as efficiently, if not moreso. For example GCC for AArch64 uses:

        add     w0, w0, w0, lsr 31      // x += (unsigned)x>>31
        asr     w0, w0, 1               // x >>= 1
        ret

Just an added note -

x *= 0.5 will often be faster in some VM-based languages -- notably actionscript, as the variable won't have to be checked for divide by 0.

Use x = x / 2; OR x /= 2; Because it is possible that a new programmer works on it in future. So it will be easier for him to find out what is going on in the line of code. Everyone may not be aware of such optimizations.

I am telling for the purpose of programming competitions. Generally they have very large inputs where division by 2 takes place many times and its known that input is positive or negative.

x>>1 will be better than x/2. I checked on ideone.com by running a program where more than 10^10 division by 2 operations took place. x/2 took nearly 5.5s whereas x>>1 took nearly 2.6s for same program.

I would say there are several things to consider.

1. Bitshift should be faster, as no special computation is really needed to shift the bits, however as pointed out, there are potential issues with negative numbers. If you are ensured to have positive numbers, and are looking for speed then I would recommend bitshift.

2. The division operator is very easy for humans to read. So if you are looking for code readability, you could use this. Note that the field of compiler optimization has come a long way, so making code easy to read and understand is good practice.

3. Depending on the underlying hardware, operations may have different speeds. Amdal's law is to make the common case fast. So you may have hardware that can perform different operations faster than others. For example, multiplying by 0.5 may be faster than dividing by 2. (Granted you may need to take the floor of the multiplication if you wish to enforce integer division).

If you are after pure performance, I would recommend creating some tests that could do the operations millions of times. Sample the execution several times (your sample size) to determine which one is statistically best with your OS/Hardware/Compiler/Code.

As far as the CPU is concerned, bit-shift operations are faster than division operations. However, the compiler knows this and will optimize appropriately to the extent that it can, so you can code in the way that makes the most sense and rest easy knowing that your code is running efficiently. But remember that an unsigned int can (in some cases) be optimized better than an int for reasons previously pointed out. If you don't need signed arithmatic, then don't include the sign bit.

x = x / 2; is the suitable code to use.. but an operation depend on your own program of how the output you wanted to produce.

Make your intentions clearer...for example, if you want to divide, use x / 2, and let the compiler optimize it to shift operator (or anything else).

Today's processors won't let these optimizations have any impact on the performance of your programs.

The answer to this will depend on the environment you're working under.

• If you're working on an 8-bit microcontroller or anything without hardware support for multiplication, bit shifting is expected and commonplace, and while the compiler will almost certainly turn x /= 2 into x >>= 1, the presence of a division symbol will raise more eyebrows in that environment than using a shift to effect a division.
• If you're working in a performance-critical environment or section of code, or your code could be compiled with compiler optimization off, x >>= 1 with a comment explaining its reasoning is probably best just for clarity of purpose.
• If you're not under one of the above conditions, make your code more readable by simply using x /= 2. Better to save the next programmer who happens to look at your code the 10 second double-take on your shift operation than to needlessly prove you knew the shift was more efficient sans compiler optimization.

All these assume unsigned integers. The simple shift is probably not what you want for signed. Also, DanielH brings up a good point about using x *= 0.5 for certain languages like ActionScript.

mod 2, test for = 1. dunno the syntax in c. but this may be fastest.

generaly the right shift divides :

q = i >> n; is the same as: q = i / 2**n;

this is sometimes used to speed up programs at the cost of clarity. I don't think you should do it . The compiler is smart enough to perform the speedup automatically. This means that putting in a shift gains you nothing at the expense of clarity.

Take a look at this page from Practical C++ Programming.

Obviously, if you are writing your code for the next guy who reads it, go for the clarity of "x/2".

However, if speed is your goal, try it both ways and time the results. A few months ago I worked on a bitmap convolution routine which involved stepping through an array of integers and dividing each element by 2. I did all kinds of things to optimize it including the old trick of substituting "x>>1" for "x/2".

When I actually timed both ways I discovered to my surprise that x/2 was faster than x>>1

This was using Microsoft VS2008 C++ with the default optimizations turned on.

In terms of performance. CPU's shift operations are significantly faster than divide op-codes. So dividing by two or multiplying by 2 etc all benefit from shift operations.

As to the look and feel. As engineers when did we become so attached to cosmetics that even beautiful ladies don't use! :)

X/Y is a correct one...and " >> " shifting operator..if we want two divide a integer we can use (/) dividend operator. shift operator is used to shift the bits..

x=x/2; x/=2; we can use like this..