Thread: Get absolute value efficiently

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    21

    Question Get absolute value efficiently

    Hello everyone,
    I was searching for a way to get absolute value efficiently using bit level hacks, n found it's int equivalent, but i wanted it on long long so changed int to long long,
    Code:
    #include <stdio.h>
    #define CHAR_BIT 8
    
    unsigned long long getAbs(long long n)
    {
      long long int const mask = n >> (sizeof(long long) * CHAR_BIT - 1);
      return ((n + mask) ^ mask);
    }
    
    int main()
    {
      long long n = -6;
      printf("Absoute value of %ll is %llu", n, getAbs(n)); //why the value of n is not printed.... 
      getchar();
      return 0;
    }
    Last edited by greendragons; 06-12-2012 at 07:27 AM.

  2. #2
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    And your question is?

    Because my first question would be "why are you trying to optimise abs() with bit-level junk", especially when one "if" would probably do the job just fine?

    - Compiler warnings are like "Bridge Out Ahead" warnings. DON'T just ignore them.
    - A compiler error is something SO stupid that the compiler genuinely can't carry on with its job. A compiler warning is the compiler saying "Well, that's bloody stupid but if you WANT to ignore me..." and carrying on.
    - The best debugging tool in the world is a bunch of printf()'s for everything important around the bits you think might be wrong.

  3. #3
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    I've just found your question in the comment. It's because your printf isn't using a standardised specifier that works cross-platform. Long long ints are a pain. Look for the macros inside inttypes.h to help you get the right printf specifier for them instead.

    Oh, and I just made a long long abs function with my if. Works perfectly. You used a bit-shift, a multiplication, a subtraction, an addition and a XOR to achieve what one conditional jump and a negation can achieve.

    Standard glibc way of achieving labs, for reference:

    http://sourceware.org/git/?p=glibc.g...39f7da;hb=HEAD
    Last edited by ledow; 06-12-2012 at 08:16 AM.

    - Compiler warnings are like "Bridge Out Ahead" warnings. DON'T just ignore them.
    - A compiler error is something SO stupid that the compiler genuinely can't carry on with its job. A compiler warning is the compiler saying "Well, that's bloody stupid but if you WANT to ignore me..." and carrying on.
    - The best debugging tool in the world is a bunch of printf()'s for everything important around the bits you think might be wrong.

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    21
    Im writing a program where efficiency is very important as im dealing with large numbers, so branching will lead to slow running time, and here comes the bit hack to rescue, mine long long abs works fine(what i didn't notice before), the problem is about printing %ll in printf, i am compiling with gcc C99...

    Anyways thanks.. i got the solution,, i should have used lld instead of ll, as it is signed long long..
    Last edited by greendragons; 06-12-2012 at 08:23 AM.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Remember to test with positive values; because I think you code only does negative values.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    It might not hurt to try llabs(), too, since a good compiler will not make a function call, but rather inline the fastest native code to do absolute value.

    Also, don't define CHAR_BIT yourself; it's defined in limits.h.

  7. #7
    Registered User
    Join Date
    Dec 2011
    Posts
    21
    nah it's working fine for positive values too...

  8. #8
    Registered User
    Join Date
    Mar 2011
    Posts
    546

    if you don't profile it, you don't know what its 'efficiency' is

    Quote Originally Posted by greendragons View Post
    Im writing a program where efficiency is very important as im dealing with large numbers, so branching will lead to slow running time, and here comes the bit hack to rescue, mine long long abs works fine(what i didn't notice before), the problem is about printing %ll in printf, i am compiling with gcc C99...

    Code:
    #define _ISOC99_SOURCE
    #include <stdio.h>
    #include <stdlib.h>
    #include <inttypes.h>
    #include <sys/time.h>
    
    #define CHAR_BIT 8
    
    double t(void) {
       struct timeval tx;
       gettimeofday(&tx,0);
       return (double)tx.tv_sec + ((double)tx.tv_usec / 1000000.0);
    }
    
    unsigned long long getAbs(long long n)
    {
      long long int const mask = n >> (sizeof(long long) * CHAR_BIT - 1);
      return ((n + mask) ^ mask);
    }
    
    int main()
    {
      double t0;
      double t1;
      long long v = 100000000;
      long long n;
      unsigned long long u;
    
      // use homebrew getAbs
      n = -v;
      t0 = t();
      while(n < v) {
              u = getAbs(n);
              n++;
      }
      t1 = t();
      printf("getAbs : %.6f\n",t1 - t0);
    
      // use runtime library _abs64
      n = -v;
      t0 = t();
      while(n < v) {
              u = llabs(n);
              n++;
      }
      t1 = t();
      printf("llabs : %.6f\n",t1 - t0);
    
      /*
      timing results: getAbs >2x slower than built in llabs
      getAbs : 1.265443
      llabs : 0.547850
      */
      return 0;
    }
    edit: similar result on Windows.

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Maybe the OP did profile it. You can't know that. Furthermore, while it is true that you should only optimize what you KNOW to be a bottleneck, profiling is not the only way of knowing something. Extensive experience, domain expertise, and algorithm analysis on paper are also ways of knowing. From MY experience, an abs() call in an inner loop can be quite destructive to performance.

  10. #10
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    I found this in Hackers Delight, you would need to change it for long long though.

    Code:
    ((x) >> 30) | 1) * x
    You could also #define that as a macro.

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Subsonics View Post
    I found this in Hackers Delight, you would need to change it for long long though.

    Code:
    ((x) >> 30) | 1) * x
    You could also #define that as a macro.
    You're missing an initial parens:
    Code:
    (((x) >> 30) | 1) * x
    But why is the shift 30 and not 31?
    And it's assuming a sign-extending right shift and two's-complement representation; but I suppose these kinds of hacks often have assumptions.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  12. #12
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by oogabooga View Post
    You're missing an initial parens:
    Code:
    (((x) >> 30) | 1) * x
    Thanks, actually from the online version it's: ((x >> 30) | 1) * x

    Quote Originally Posted by oogabooga View Post
    But why is the shift 30 and not 31?
    And it's assuming a sign-extending right shift and two's-complement representation; but I suppose these kinds of hacks often have assumptions.
    That is a good question. It's here on page 17-18: http://www.hackersdelight.org/basics.pdf

    It's not necessarily an assumption, if the target cpu is known.

  13. #13
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I think I figured out why 30 works, although 31 also works. It's because the | 1 will set the rightmost bit anyway, giving you your 2's comp -1 (or just 1 if all other bits are 0).
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    [Edit]
    Decided this post was to abrasive. I'll rewrite it when I get some sleep.
    [/Edit]

    Soma
    Last edited by phantomotap; 06-13-2012 at 12:03 AM.

  15. #15
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Right-shifting a signed integer is implementation-defined. The hack assumes the compiler will sign-extend the value.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Efficiently adding to the end of a linked ist
    By nkbxwb in forum C Programming
    Replies: 1
    Last Post: 10-29-2011, 04:41 PM
  2. Drawing bitmaps efficiently
    By scwizzo in forum Windows Programming
    Replies: 28
    Last Post: 06-30-2009, 08:25 PM
  3. Help on making program run more efficiently
    By peeweearies in forum C Programming
    Replies: 2
    Last Post: 03-23-2009, 02:01 AM
  4. solve efficiently
    By jack_carver in forum C Programming
    Replies: 4
    Last Post: 02-20-2009, 07:56 AM
  5. solving efficiently
    By jack_carver in forum C++ Programming
    Replies: 1
    Last Post: 02-20-2009, 07:54 AM

Tags for this Thread