416

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.

Mathieu Pagé
  • 10,764
  • 13
  • 48
  • 71
Abhineet
  • 6,459
  • 10
  • 35
  • 53
  • Similar question (but not a dupe): http://stackoverflow.com/questions/1949271/would-you-use-num2-or-num1-to-check-if-a-number-is-even – Steve Jessop May 21 '12 at 09:33
  • 77
    If you really want to assign the result to `x` again, neither is appropriate in this way: it should be either `x >>= 1` or `x /= 2`, depending on what you intend to express with the operation. Not because it's faster (any modern compiler will compile all the equivalent variants to identical, fast assembly anyway) but because it's less confusing. – leftaroundabout May 21 '12 at 13:46
  • 35
    I disagree with leftaroundabout. - But I think its noteworthy that there is an operation called [arithmetic shift](http://en.wikipedia.org/wiki/Arithmetic_shift) in many programming languages that keeps the sign bit in place and therefor works for signed values as expected. The syntax may be like `x = x >>> 1`. Also note that depending on the platform and compiler it may be quite reasonable to manually optimize divisions and multiplications using shifts. - Thinking of micro controllers, for instance, w/o direct ALU support for multiplication. – JimmyB May 21 '12 at 19:59
  • 36
    I prefer `x /= 2` because `x >>= 1` looks too much like monadic bind ;) – fredoverflow May 22 '12 at 04:50
  • @HannoBinder in which way do you disagree? – leftaroundabout May 23 '12 at 12:30
  • 19
    @leftaroundabout - I just deem it a lot more readable to write `x = x / 2` instead of `x /= 2`. Subjective preference maybe :) – JimmyB May 23 '12 at 14:51
  • 8
    @HannoBinder: certainly subjective, in particular a lot of habit. IMO, in a language where all arithmetic operators have the `⬜=` combinations, these should be used whenever it's possible. It removes noise and puts emphasis on the fact that `x` is _modified_, while the general `=` operator rather suggests that it takes on a completely new value independent of the old one. — Always avoiding the combined operators (so that it's readable so someone who only knows mathematical operators) may have its point as well, but then you'd need to relinquish the extremely useful `++`, `--`, `+=`, too. – leftaroundabout May 23 '12 at 15:20
  • 1
    Duplicates: [c-left-shift-or-add-to-itself-speed](http://stackoverflow.com/questions/7117406/c-left-shift-or-add-to-itself-speed), [divisions-by-power-of-two-value-into-shifts](http://stackoverflow.com/questions/2580680/does-a-c-c-compiler-optimize-constant-divisions-by-power-of-two-value-into-shi), [is-using-shift-operators-actually-faster](http://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster) – Inverse May 24 '12 at 20:06
  • Another similar question: http://stackoverflow.com/questions/53757/which-compiles-to-faster-code-n-3-or-nn2/53797#53797 – Ferruccio Jun 08 '12 at 09:52
  • 2
    Shifting bits is only for unsigned integer numbers. And other type of numbers bit representation is totally different. – Melug Jun 09 '12 at 02:27
  • @leftaroundabout And when using C++ or other languages with support for operator overloading, it can actually reduce temporary copies by updating the internal state of the assigned-to object directly (as the overloaded operator usage ends up converted into function calls, there's no guarantee the compiler would be able to optimize away all the temporaries that could end up created, though some of them probably will be due to move semantics/copy elision in modern compilers). – JAB Nov 18 '15 at 21:51

22 Answers22

855

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)

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 48
    In C++03, both are implementation defined for negative numbers, and *might* give the same results. In C++11, division is well defined for negative numbers, but shifting is still implementation defined. – James Kanze May 21 '12 at 08:02
  • 2
    While the definition of / is implementation (does if round up or down for negative numbers) defined in early C standards. It must always be consistent with % (modulo/remainder operator). – ctrl-alt-delor May 21 '12 at 11:42
  • different results for negative numbers at ALL. – std''OrgnlDave May 21 '12 at 14:42
  • @JamesKanze - Does "Implementation Defined" mean the architecture of CPU? What are the variables/constants that would affect the output? – makerofthings7 May 21 '12 at 19:24
  • 7
    "Implementation defined" means that the implementer of the compiler got to choose among several implementation choices, usually with substantial constraints. Here, one constraint is that the `%` and `/` operators must be consistent for both positive and negative operands so that `(a/b)*b+(a%b)==a` is true regardless of the signs of `a` and `b`. Usually, the author will make choices that get the best possible performance out of the CPU. – RBerteig May 21 '12 at 20:35
  • you need to take into account that integers are one complement. Even though the foremost bits are effectively signed bits, the other bits aren't. -1, for example, is expressed as 11111111 – user4951 May 22 '12 at 01:29
  • 2
    For C/C++, Java, bc, expr, the math is done right. But for Ruby, Python and Tcl, -5 / 2 = -3, while - (5 / 2) = -2, counter intuitive but noteworthy. See http://bugs.ruby-lang.org/issues/3289 – ryenus May 22 '12 at 04:07
  • 1
    @richard C++11 defines the modulo operator explicitly for negative numbers. – Mahmoud Al-Qudsi May 22 '12 at 04:40
  • Just for later viewers who only look at the accepted solution, it should be better to include at least a short sentence about how the compiler would most likely generate the same code from both. – vsz May 22 '12 at 06:05
  • 1
    @JimThio First, the representation of negative numbers depends on the machine. And second, by far the most widespread representation is two's complement, not ones complement. In 32 bit two's complement, -1 is `0xFFFFFFFF`; right shifted, it is implementation defined whether this results in `0x7FFFFFFF` (2147483647) or `0xFFFFFFFF` (-1). – James Kanze May 22 '12 at 07:34
  • 2
    @RBerteig Also, "implementation defined" means that the implementation is required to document what it does. – James Kanze May 22 '12 at 07:35
  • @JamesKanze of course documentation is expected as part of the deal. The quality of that documentation might be a good indicator of the quality of the standards compliance of the compiler. – RBerteig May 22 '12 at 17:11
  • 2
    @RBerteig Documentation is expected for every program. In the case of "implementation defined", the standard says that the implementation is non-conformant if it doesn't document its behavior in these cases. (In my experience, most compilers are non-conform in this regard. Or else they've got the documentation particularly well hidden.) – James Kanze May 22 '12 at 18:27
  • While I think that this is a fine answer, I'm kind of amazed that this (and the other answers, including my own) have received so many upvotes. They aren't particularly profound. – jamesdlin May 23 '12 at 04:45
  • In the C standards a feature can be: defined by the standard, implementation defined, or undefined. The first 2 are defined, by the standard or individual implementation, the 3rd undefined does not have to be defined, it can do it different every time. – ctrl-alt-delor May 23 '12 at 13:33
  • 6
    So everyone who says "the compiler will convert it to a shift anyway" is wrong, right? Unless the compiler can guarantee that you are dealing with a non-negative integer (either it is a constant or it is an unsigned int), it can't change it to a shift – Kip May 25 '12 at 19:39
  • @RBerteig: On many processors, dividing a value of unknown sign by an unknown quantity will be fastest using truncate-toward-zero, but dividing by many known quantities (including powers of two, but in many cases quite a few other values as well) will be faster using truncate-toward-negative-infinity. – supercat Nov 01 '13 at 19:24
  • 1
    @ryenus: While -5/2=-3 differs from what C-derived languages do, I can't think of any program where I've ever wanted to compute a quotient that was truncated toward zero; the only programs I've seen which would have difficulty if a compiler that instead rounded toward negative infinity are those which adjust negative values prior to division so that the compiler's truncate-toward-zero will yield the result that truncate-toward-negative-infinity would have given without adjustment. Can you offer any counter-examples? – supercat Nov 01 '13 at 19:39
  • @Kip: It can't change it to *just one* shift, but signed `int` `x/2` can be done as `(x + (unsigned(x)>>31)) >> 1`, which is what compilers do in practice. https://godbolt.org/z/G9TTYG6Ke shows compilers never actually use a slow `idiv`, instead a shift/add before the real shift. But yes, if you don't need `x /= 2` truncation towards zero for negative numbers, `x >>= 1` is even faster for signed `int`. – Peter Cordes May 03 '22 at 02:43
230

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.

Shahbaz
  • 46,337
  • 19
  • 116
  • 182
Cat Plus Plus
  • 125,936
  • 27
  • 200
  • 224
  • 18
    Many compilers will not turn division by power of two into a bitshift. That would be an incorrect optimization for signed integers. You should try to look at assembly output from your compiler and see for yourself. – exDM69 Jun 08 '12 at 09:52
  • 1
    IIRC I used that to make parallel reduction faster on CUDA (avoid integer div). However this was more than a year ago, I wonder how smart the CUDA compilers are nowadays. – Nils Jun 08 '12 at 10:43
  • 9
    @exDM69: Many compilers will do that even for signed integers, and just adjust them according to the signedness. A nice tool to play with these things is this: http://tinyurl.com/6uww253 – PlasmaHH Jun 08 '12 at 11:57
  • 21
    @exDM69: And that's relevant, how? I said "if possible", not "always". If optimisation is incorrect, then doing it manually doesn't make it correct (plus as mentioned, GCC is smart enough to figure out proper replacement for signed integers). – Cat Plus Plus Jun 08 '12 at 15:26
  • 4
    Looking at the WikiPedia page, this is apparently controversial, but I wouldn't call it a strength reduction. A strength reduction is when, in a loop, you reduce from, for instance, multiplication to addition, by adding to previous values in the loop. This is more of a peephole optimization, which compilers can do pretty reliably. – SomeCallMeTim Jun 08 '12 at 16:37
  • @exDM69: It only takes an extra shift and add to implement `x/2` in terms of logical and arithmetic shifts. https://godbolt.org/z/G9TTYG6Ke So yes, `x>>1` is even cheaper for signed, but `x/2` won't use `idiv` with any sane compiler. This answer could do a better job of explaining what happens if it's not doable with a single `shr` or `sar`. – Peter Cordes May 03 '22 at 02:46
190

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.

Community
  • 1
  • 1
Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • 5
    It's also worth adding that while there are rules of precedence, there isn't a damn thing wrong with using parentheses. While revamping some production code, I actually saw something of the form `a/b/c*d` (where `a..d` denoted numeric variables) instead of the far more readable `(a*d)/(b*c)`. –  May 23 '12 at 20:16
  • 1
    The performance and optimizations depend on the compiler and target. For example, I do some work for a microcontroller where anything higher than -O0 is disabled unless you buy the commercial compiler, so the compiler will definitely not turn divide into bitshifts. Furthermore, bitshifts take one cycle and divide takes 18 cycles on this target and since the microcontrollers clock speed is pretty low, this may be indeed be a noticeable performance hit (but it depends on your code - you should definitely use / until profiling tells you its a problem!) –  Jun 08 '12 at 10:21
  • 4
    @JackManey, if there's any possibility that `a*d` or `b*c` would produce an overflow, the less readable form is not equivalent and has an obvious advantage. P.S. I agree that parentheses are your best friend. – Mark Ransom Jun 08 '12 at 16:36
  • @MarkRansom - A fair point (even though I ran into `a/b/c*d` in R code--in a context where overflow would mean that something was seriously wrong with the data--and not in, say, a performance-critical block of C code). –  Jun 08 '12 at 18:10
  • The code `x=x/2;` is only "clearer" than `x>>=1` if `x` will never be an odd negative number or one doesn't care about off-by-one errors. Otherwise `x=x/2;` and `x>>=1;` have different meanings. If what one needs is the value computed by `x>>=1`, I would regard that as clearer than `x = (x & ~1)/2` or `x = (x < 0) ? (x-1)/2 : x/2`, or any other formulation I can think of using division by two. Likewise if one needs the value computed by `x/=2`, that is clearer than `((x + ((unsigned)x>>31)>>1)`. – supercat Nov 01 '13 at 19:10
  • @Dan: Writing code for non-optimizing compilers is very much a corner case. You're going to have to write less-easy-to-read code in more ways than that to try to optimize the asm. Besides, even at -O0, gcc and icc implement signed division by 2 with a shift + adjust-for-sign-bit. [(godbolt link)](http://goo.gl/FTupG5). clang -O0 does actually use div, though. Modern x86 CPUs have a similar latency&throughput ratio for div vs. shift, so yes, it's a big deal for compilers to avoid div. It's maybe not quite as bad as a branch mispredict, but maybe something like an L1 miss that hits in L2 – Peter Cordes Oct 04 '15 at 14:38
  • @PeterCordes I agree. That's why I said `The performance and optimizations depend on the compiler and target` and `you should definitely use / until profiling tells you its a problem!`. My point was that there ARE corner cases (eg microcontrollers, in my case it was a `PIC24` and, at least at the time when I wrote the comment, it did not optimise `/` on `-O0`) where there is a difference and that it depends on if you are working in one of these corner cases or not. –  Oct 05 '15 at 10:05
62

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.

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
59

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

justin
  • 104,054
  • 14
  • 179
  • 226
  • 36
    The compiler *should* optimize accordingly. – Noctis Skytower May 22 '12 at 15:01
  • 13
    If the compiler doesn't optimize accordingly, you *should* use a better compiler. – David Stone Aug 13 '12 at 00:34
  • 4
    @DavidStone: On what processors *can* a compiler optimize division of a possibly-negative signed integer by any constant other than 1 to be as efficient as a shift? – supercat Nov 01 '13 at 19:19
  • 2
    @supercat: That is a good point. You could of course store the value in an unsigned integer (which I feel have a much worse reputation than they should when combined with signed / unsigned mismatch warnings), and most compilers also have a way of telling them to assume something is true when optimizing. I would prefer wrapping that in a compatibility macro and have something like `ASSUME(x >= 0); x /= 2;` over `x >>= 1;`, but that is still an important point to bring up. – David Stone Nov 02 '13 at 01:17
  • @DavidStone Unless you are able to list such a "better compiler" for every microcontroller that anyone reading this question could be using, I'm inclined to disagree with your comment. There are plenty of compilers that people may have to use for one reason or another, and saying "you shouldn't be doing that" is quite useless information to them. I can't imagine any mainstream compiler not performing the optimization but compilers that don't still exist. – Kröw Mar 05 '23 at 05:02
38

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 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

jamesdlin
  • 81,374
  • 13
  • 159
  • 204
  • 4
    It's worthwhile to note that the behavior that many implementations define for `x>>scalepower` on negative numbers will be precisely what is needed when dividing a value by a power of two for purposes such as screen rendering, while using `x/scalefactor` will be wrong unless one applies corrections to negative values. – supercat Nov 01 '13 at 19:17
  • In practice almost(?) all implementations define `>>` on signed integral types as an arithmetic right shift, i.e. shifting in copies of the sign bit for 2's complement. (e.g. GNU C guarantees that: https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html.) Of course a Deathstation 9000 could do something non-useful, but this is not really a significant portability concern for most code. ISO C++ is even moving in the direction of standardizing it as an arithmetic right shift. – Peter Cordes May 03 '22 at 02:51
29

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.)

Thomas Mueller
  • 48,905
  • 14
  • 116
  • 132
  • 1
    Compilers cannot convert `x/2` to `x>>1` in cases where `x` may be negative. If what one wants is the value which `x>>1` would compute, that will almost certainly be faster than any expression involving `x/2` which computes the same value. – supercat Nov 01 '13 at 19:26
  • You are right. A compilers may only convert `x/2` to `x>>1` if he knows the value is not negative. I will try to update my answer. – Thomas Mueller Nov 02 '13 at 07:40
  • compilers do still avoid a `div` instruction though, by converting `x/2` into `(x + (x<0?1:0)) >> 1` (where >> is an arithmetic right-shift, that shifts in sign bits). This takes 4 instructions: copy the value, shr(to get just the sign bit in a reg), add, sar. http://goo.gl/4F8Ms4 – Peter Cordes Oct 04 '15 at 14:48
  • 1
    The question is tagged as C and C++. – Josh Sanford Jul 29 '16 at 19:30
21

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.

Ivan Californias
  • 319
  • 1
  • 3
  • 5
    What would you consider the preferred method of scaling a number down by a power of two if one wants integers to uphold the axiom (which applies to natural numbers and real numbers) that (n+d)/d = (n/d)+1? Violations that axiom when scaling graphics will cause visible "seams" in the result. If one wants something which is uniform and almost symmetric about zero, `(n+8)>>4` works nicely. Can you offer any approach which is as clear or as efficient without using a signed right shift? – supercat Nov 20 '13 at 17:29
18

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
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Michael Donohue
  • 11,776
  • 5
  • 31
  • 44
  • Depending upon what one is doing, it may fix the off-by-one error, or it may *cause* an off-by-one error (compared with what's actually needed) which will necessitate the use of further code to fix it. If what one wants is a floored result, a right-shift is a faster and easier than any alternative I know of. – supercat Nov 20 '13 at 00:15
  • If you need a floor, it is unlikely you would describe what you want as "dividing by 2" – Michael Donohue Nov 20 '13 at 07:03
  • Division of both natural numbers and real numbers upholds the axiom that (n+d)/d = (n/d)+1. Division of real numbers also upholds (-n)/d = -(n/d), an axiom which is meaningless with natural numbers. It is not possible to have a division operator which is closed on integers and upholds both axioms. To my mind, saying that the first axiom should hold for all numbers and the second only for reals seems more natural than saying that the first should hold for whole numbers or reals but not for integers. Further, I'm curious in what cases the second axiom is actually *useful*. – supercat Nov 20 '13 at 16:58
  • 1
    An integer division method which satisfies the first axiom will partition the number line into regions of size `d`. Such partitioning is useful for many purposes. Even if one would rather have the breakpoint somewhere other than between 0 and -1, adding an offset will move it. An integer division which satisfies the second axiom will partition the number line into regions which are mostly of size `d`, but one of which is of size `2*d-1`. Not exactly "equal" divisions. Can you offer suggestions of when the oddball partition is actually useful? – supercat Nov 20 '13 at 17:03
  • Your compiler output for shr2signed is wrong. gcc on x86 chooses to implement >> of signed integers with arithmetic shifts (`sar`). http://goo.gl/KRgIkb. This mailing list post (https://gcc.gnu.org/ml/gcc/2000-04/msg00152.html) confirms that gcc historically uses arithmetic shifts for signed ints, so it's highly unlikely that FreeBSD gcc 4.2.1 used unsigned shift. I updated your post to fix that and the early paragraph saying both used shr, when it's actually SAR that they both use. The SHR is how it extracts the sign bit for the `/` case. Also included a godbolt link. – Peter Cordes Oct 04 '15 at 15:14
  • Since those operations are not the same there's little point in comparing them for performance. – skyking Nov 12 '21 at 09:58
15

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.

ansiart
  • 2,563
  • 2
  • 23
  • 41
  • 2
    @minitech: That's such a bad test. All the code in the test is constant. Before the code is even JITed, it'll eliminate all the constants. –  Jan 27 '14 at 03:44
  • @M28: I was pretty sure jsPerf’s internals (i.e. `eval`) made that happen afresh each time. Regardless, yes, it is a pretty bad test, because it’s a very silly optimization. – Ry- Jan 27 '14 at 04:10
  • Isn't the OP asking specifically about dividing by 2? Where could a divide by 0 come up? – Kröw Mar 05 '23 at 05:06
13

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.

Shashwat Kumar
  • 5,159
  • 2
  • 30
  • 66
  • 1
    For unsigned values, a compiler should optimize `x/2` to `x>>1`. For signed values, nearly all implementations define `x>>1` to have a meaning which is is equivalent to `x/2` but can be computed faster when `x` is positive, and is usefully different from `x/2` when `x` is negative. – supercat Nov 20 '13 at 00:22
13

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.

James Oravec
  • 19,579
  • 27
  • 94
  • 160
  • 2
    "Bitshift should be faster". compilers will optimize divisions into bitshifts – Trevor Hickey May 24 '12 at 04:09
  • I hope they would, but unless you have access to the source of the compiler, you can't be sure :) – James Oravec Jul 31 '13 at 14:57
  • 1
    I would also recommend bitshift if one's implementation handles it in the most common fashion and the way one wants to handle negative numbers matches with what `>>` does and doesn't match what `/` does. – supercat Nov 01 '13 at 19:34
  • This is a very nice answer that not only sums up much of the other posts above it, but lists many things to consider instead of picking a subjective side. – Kröw Mar 05 '23 at 05:08
13

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.

tylerl
  • 30,197
  • 13
  • 80
  • 113
12

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.

Imdad
  • 5,942
  • 4
  • 33
  • 53
10

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.

Gooner
  • 369
  • 5
  • 16
10

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.

Atul Kumar
  • 421
  • 3
  • 12
9

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.

gkimsey
  • 517
  • 6
  • 13
8

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

circusdei
  • 1,967
  • 12
  • 28
6

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.

Mouna Cheikhna
  • 38,870
  • 10
  • 48
  • 69
  • 1
    If one wants to compute the value that e.g. `(x+128)>>8` would compute for values of `x` not near the maximum, how could one concisely do it without a shift? Note that `(x+128)/256` won't work. Do you know of any nice expression that will? – supercat Nov 01 '13 at 19:28
6

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.

Chris Bennet
  • 587
  • 5
  • 13
4

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! :)

Farjad
  • 257
  • 4
  • 9
2

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..

chocolate boy
  • 63
  • 1
  • 6