1

What is the fastest way to compute absolute value of integer of long long int type in C++ ? Is it possible to do without if() statement ? I was trying conversion to unsigned and then to signed again, but it doesn't work.

Qbik
  • 5,885
  • 14
  • 62
  • 93

3 Answers3

5

Try std::abs against the ternary operator, profile, and see for yourself.

juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • 1
    Would `std::abs` be faster than a XOR operation against `0x8000000000000000`? – user123 Mar 18 '13 at 21:48
  • @Magtheridon96 maybe not. However, `std::abs` is portable, while that bit hack isn't. – Richard J. Ross III Mar 18 '13 at 21:49
  • @Magtheridon96 `std::abs` would be portable. Concerning speed, I would say the same: profile and see for yourself. – juanchopanza Mar 18 '13 at 21:50
  • 1
    Oh well, portability wins in the end. I'd profile, but I'm quite low on disk space and Visual Studio created 2GB of files last time I attempted to profile my project, so I guess I'll just leave that for another day. :P – user123 Mar 18 '13 at 21:50
  • @Magtheridon96 well, not always. You might need to squeeze performance out of an application that only runs on a specific platform. But the point about profiling still applies, of course. – juanchopanza Mar 18 '13 at 21:51
  • 2
    @Magtheridon96: That XOR will flip the sign, but a) you don't know whether you even need to modify the input (what if it is already positive) and b) even if you do, that XOR will not give you the correct value. `-1 ^ 0x8000... != 1` (in most common platforms with two's complement) – David Rodríguez - dribeas Mar 18 '13 at 21:53
  • @downvoter If there is something wrong with my answer, or it is controversial enough to merit a downvote, I would be interested in knowing so I can improve/fix it. – juanchopanza Mar 18 '13 at 21:57
2

Adapted from Bit Twiddling Hacks, Compute the integer absolute value (abs) without branching:

long long v; // value to abs()
long long const mask = v >> sizeof(long long) * CHAR_BIT - 1;

unsigned long long result = (v + mask) ^ mask;
Marco Bonelli
  • 63,369
  • 21
  • 118
  • 128
nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • 2
    The only problem with this is that it requires a very specific implementation of `long long`, which while is very prevalent, isn't perfectly portable. – Richard J. Ross III Mar 18 '13 at 21:47
  • 1
    .. that and that in some platforms the are specific non-branching instructions to implement the ternary operator with fundamental types... – David Rodríguez - dribeas Mar 18 '13 at 21:48
  • I like this answer. Would I be correct in assuming that this now means that the pipeline is guaranteed to saturate as opposed to relying on branch prediction to give you the improvements only some of the time? If that's the case then this is faster than branching. – nonsensickle Mar 18 '13 at 21:54
  • 1
    @nonsensical: Profile. On some platforms, ternaries can be optimized to conditional moves (or, e.g. on ARM, conditional instructions), which usually execute just as fast as arithmetic instructions. – nneonneo Mar 18 '13 at 21:55
  • 4
    @nonsensical, you're replacing a single branch with multiple logical and arithmetic operations. You can't guarantee that it will be faster, especially if the majority of your inputs will be one sign or the other. And there's always the possibility that your compiler uses non-branching instructions in the first place. – Mark Ransom Mar 18 '13 at 22:02
  • @nneonneo Good point. I guess the depth of the pipeline is another factor to consider in gauging the benefits of using this approach. Still, it is a good one to remember. Thanks – nonsensickle Mar 18 '13 at 22:07
  • Is there any way you can explain to me how that last line works? What is the logic behind it? – David G May 05 '13 at 03:44
0

You should use llabs. See the reference about abs functions on cplusplus.com

joce
  • 9,624
  • 19
  • 56
  • 74