bitwise absolute value

Discussion in 'C Programming' started by Christopher Benson-Manica, Sep 7, 2003.

  1. I'm trying to compute the absolute value of an integer using only bitwise
    operators...

    int x;
    sscanf( "%d", &x );
    printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );

    That works, but it assumes 32 bit integers. Is there a portable/standard way
    to do this? Or are ANSI integers always 32 bits? If not, is using
    sizeof(int) * 8 - 1 as the shift value an acceptable alternative?

    --
    Christopher Benson-Manica | Jumonji giri, for honour.
    ataru(at)cyberspace.org |
    Christopher Benson-Manica, Sep 7, 2003
    #1
    1. Advertising

  2. Christopher Benson-Manica

    Malcolm Guest

    "Christopher Benson-Manica" <> wrote in message
    >
    > are ANSI integers always 32 bits? If not, is using
    > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?
    >

    Integers can be 16, 32 or very rarely another number of bits. chars are
    usually 8 bits but 9 or 32 has occasionally been reported.

    using ( sizeof(int) * CHAR_BIT ) will be reasonably portable, but vulnerable
    to padding bits. INT_MAX will give you the maximum value of an integer.
    There is also no guarantee that your system uses two's complement
    representation of negative numbers.

    So it is quite easy to make your construct portable to any architecture you
    are likely to encounter in practise, but very difficult to do so in a
    perfectly compliant manner. Since your problem looks like a brainteaser
    rather than a real programming construct, it is probably worth pinting out
    the pitfalls to whoever set it.
    Malcolm, Sep 7, 2003
    #2
    1. Advertising

  3. On Sun, 07 Sep 2003 20:06:20 +0000, Christopher Benson-Manica wrote:

    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...
    >
    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    >
    > That works, but it assumes 32 bit integers.


    That can be easily fixed. The more insidious assumption is that it assumes
    twos-complement representation of integers.

    Josh
    Josh Sebastian, Sep 7, 2003
    #3
  4. "Christopher Benson-Manica" <> wrote in message
    news:bjg33s$b10$...
    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...
    >
    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    >
    > That works, but it assumes 32 bit integers. Is there a portable/standard

    way
    > to do this? Or are ANSI integers always 32 bits? If not, is using
    > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?
    >
    > --
    > Christopher Benson-Manica | Jumonji giri, for honour.
    > ataru(at)cyberspace.org


    Why not just (x ^ (x>>31)) - (x>>31)?
    Good compilers will actually generate this code. It avoids a branch which is
    important on today's processors.
    Be aware that Sun has a patent on this method.


    Carsten Hansen
    Carsten Hansen, Sep 7, 2003
    #4
  5. Carsten Hansen <> spoke thus:

    >> (x^((~((x>>31)&1))+1)) + ((x>>31)&1)


    > Why not just (x ^ (x>>31)) - (x>>31)?
    > Good compilers will actually generate this code. It avoids a branch which is
    > important on today's processors.
    > Be aware that Sun has a patent on this method.


    Whoops... What's the rationale behind that though? I'm trying to wrap my
    brain around the logic... And how does it avoid a branch?

    --
    Christopher Benson-Manica | Jumonji giri, for honour.
    ataru(at)cyberspace.org |
    Christopher Benson-Manica, Sep 8, 2003
    #5
  6. "Christopher Benson-Manica" <> wrote in message
    news:bjgg1f$c0o$...
    > Carsten Hansen <> spoke thus:
    >
    > >> (x^((~((x>>31)&1))+1)) + ((x>>31)&1)

    >
    > > Why not just (x ^ (x>>31)) - (x>>31)?
    > > Good compilers will actually generate this code. It avoids a branch

    which is
    > > important on today's processors.
    > > Be aware that Sun has a patent on this method.

    >
    > Whoops... What's the rationale behind that though? I'm trying to wrap my
    > brain around the logic... And how does it avoid a branch?
    >
    > --
    > Christopher Benson-Manica | Jumonji giri, for honour.
    > ataru(at)cyberspace.org |


    Traditionally you take the absolute value by doing something like

    if (x < 0)
    y = -x;
    else
    y = x;

    Or maybe

    y = (x < 0) ? -x : x;

    But this involves a comparison and a branch. If the sign of x is random, the
    branch prediction is of no value. Hence the processor will stall in 50% of
    the cases. Very bad.
    In compression code this is common case. You remove all redundancy, and the
    rest is white noise that you have to encode.
    Today it is in general better to do a few extra instructions if that will
    avoid a branch. "Keep the processor busy".
    Intel's compiler will do this optimization.


    Carsten Hansen
    Carsten Hansen, Sep 8, 2003
    #6
  7. Christopher Benson-Manica <> wrote in message news:<bjg33s$b10$>...
    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...


    Why?

    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    >
    > That works, but it assumes 32 bit integers.


    And two's complement representation, and sign bit propogating right
    shifts, and possibly an absence of trap representations.

    In a clc sense, it doesn't work at all.

    > Is there a portable/standard way to do this?


    (x < 0 ? -x : x)

    Note that it does assume that INT_MIN is negatable, which isn't the
    case in 2c.

    > Or are ANSI integers always 32 bits?


    Definitely not. An int must have at least 16 (value+sign) bits, a long
    must have at least 32.

    > If not, is using sizeof(int) * 8 - 1 as the shift value an acceptable
    > alternative?


    No, since CHAR_BIT need not be 8 and the integer can be padded.

    --
    Peter
    Peter Nilsson, Sep 8, 2003
    #7
  8. Peter Nilsson <> spoke thus:

    > Why?


    It was an assignment for the intro-to-C class at school and I was trying to
    help a friend... and it was a macho thing to prove I could do it ;)

    > In a clc sense, it doesn't work at all.


    By "works," of course, I meant "produces correct results on my implementation."

    > (x < 0 ? -x : x)


    Certainly would have been my first choice, but all conditional operators were
    explicitly forbidden by the assignment. The 32-bit integer assumption was
    explicitly permitted, and two's complement represenation was implied. Since
    the code was only required to work on a specific implementation (an i386 Linux
    box, I believe), these assumptions were acceptable in the context of the
    assignment.

    Is this question impossible to answer in a strictly ANSI-compliant way, then?

    --
    Christopher Benson-Manica | Jumonji giri, for honour.
    ataru(at)cyberspace.org |
    Christopher Benson-Manica, Sep 8, 2003
    #8
  9. Carsten Hansen <> spoke thus:

    >> Whoops... What's the rationale behind that though? I'm trying to wrap my
    >> brain around the logic... And how does it avoid a branch?


    > (reply snipped)


    I probably should have been clear earlier - this was an assignment a friend of
    mine had, and conditional operations were explictly forbidden.

    --
    Christopher Benson-Manica | Jumonji giri, for honour.
    ataru(at)cyberspace.org |
    Christopher Benson-Manica, Sep 8, 2003
    #9
  10. On Mon, 8 Sep 2003, Christopher Benson-Manica wrote:
    >
    > Peter Nilsson <> spoke thus:
    >
    > > Why?

    >
    > It was an assignment for the intro-to-C class at school and I was trying to
    > help a friend... and it was a macho thing to prove I could do it ;)


    Yes, it is September already.
    (BTW, I'm in a course this year whose first lab consists entirely of
    about a dozen of these "brain-teasers," assuming the same things that
    the OP's code assumed (sign-propagation, two's-complement, 32-bit, no
    trap on overflow...). But we didn't have to do absolute value for our
    lab.)

    > > In a clc sense, it doesn't work at all.

    >
    > By "works," of course, I meant "produces correct results on my
    > implementation."


    Well, that's not the clc sense of "works." :)

    > > (x < 0 ? -x : x)

    >
    > Certainly would have been my first choice, but all conditional operators
    > were explicitly forbidden by the assignment. The 32-bit integer assumption
    > was explicitly permitted, and two's complement representation was
    > implied. Since the code was only required to work on a specific
    > implementation (an i386 Linux box, I believe), these assumptions were
    > acceptable in the context of the assignment.
    >
    > Is this question impossible to answer in a strictly ANSI-compliant way,
    > then?


    See Peter's answer.

    y = (x < 0)? -x: x;

    This *is* the ISO-compliant way to compute absolute value. Bitwise
    operators in C operate on bits, not values, so you can't use them to
    compute [much of] anything related to value. C makes a distinction
    between the *value* of an 'int' and the *representation* thereof.
    <OT> I bet your code works [in the clc sense] in Java. </OT>

    HTH,
    -Arthur
    Arthur J. O'Dwyer, Sep 8, 2003
    #10
  11. Christopher Benson-Manica

    Ben Pfaff Guest

    Christopher Benson-Manica <> writes:

    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...
    >
    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );


    + is not a bitwise operator.
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
    Ben Pfaff, Sep 8, 2003
    #11
  12. Christopher Benson-Manica

    Ben Pfaff Guest

    It doesn't answer your question directly, but here's some code
    that you might find interesting:

    #include <stdio.h>
    #include <limits.h>

    /* Return X + 1. */
    unsigned
    uincr (unsigned x)
    {
    unsigned y;

    for (y = 1; y != 0; y <<= 1)
    if ((x ^= y) & y)
    break;

    return x;
    }

    /* Return X - 1. */
    unsigned
    udecr (unsigned x)
    {
    unsigned y;

    for (y = 1; y != 0; y <<= 1)
    if (!((x ^= y) & y))
    break;

    return x;
    }

    /* Returns value of most significant bit in unsigned type. */
    unsigned
    msb (void)
    {
    /* There must be a better way... */
    unsigned y;
    for (y = 1; y << 1; y <<= 1);
    return y;
    }

    /* Negates X, which is in the machine's native int format. */
    unsigned
    negate (unsigned x)
    {
    if ((int) UINT_MAX == -1)
    return uincr (~x);
    else if ((int) UINT_MAX == 0)
    return ~x;
    else
    return x ^ msb ();
    }

    /* Converts X, in the machine's native int format, to 2's complement
    form. */
    unsigned
    n2twos (unsigned x)
    {
    if ((x & msb ()) == 0 || (int) UINT_MAX == -1)
    return x;
    else if ((int) UINT_MAX == 0)
    return uincr (x);
    else
    return uincr (~(x ^ msb ()));
    }

    /* Converts X, in 2's complement format, to the machine's native int
    format. */
    int
    twos2n (unsigned x)
    {
    if ((x & msb ()) == 0 || (int) UINT_MAX == -1)
    return x;
    else if ((int) UINT_MAX == 0)
    return udecr (x);
    else
    return uincr (~x) ^ msb ();
    }

    /* Returns the bit pattern in X as an int. */
    int
    u2i (unsigned x)
    {
    return *(int *) &x;
    }

    /* Returns the bit pattern in X as an unsigned. */
    unsigned
    i2u (int x)
    {
    return *(unsigned *) &x;
    }

    /* Returns X + 1. */
    int
    sincr (int x)
    {
    return u2i (twos2n (uincr (n2twos (i2u (x)))));
    }

    /* Returns X - 1. */
    int
    sdecr (int x)
    {
    return u2i (twos2n (udecr (n2twos (i2u (x)))));
    }

    int
    main (void)
    {
    int x;

    for (x = -10; x <= +10; x = sincr (x))
    printf ("% 3d ", x, negate (x));
    putchar ('\n');

    for (x = +10; x >= -10; x = sdecr (x))
    printf ("% 3d ", x);
    putchar ('\n');

    return 0;
    }

    --
    "Your correction is 100% correct and 0% helpful. Well done!"
    --Richard Heathfield
    Ben Pfaff, Sep 8, 2003
    #12
  13. On Mon, 8 Sep 2003, Arthur J. O'Dwyer wrote:
    >
    > On Mon, 8 Sep 2003, Christopher Benson-Manica wrote:
    > > Peter Nilsson <> spoke thus:
    > >
    > > > Why?

    > >
    > > It was an assignment for the intro-to-C class at school and I was
    > > trying to help a friend... and it was a macho thing to prove I
    > > could do it ;)

    >
    > Yes, it is September already.
    > (BTW, I'm in a course this year whose first lab consists entirely of
    > about a dozen of these "brain-teasers," assuming the same things that
    > the OP's code assumed (sign-propagation, two's-complement, 32-bit, no
    > trap on overflow...). But we didn't have to do absolute value for our
    > lab.)


    Funny story... right after I wrote that, I headed to recitation for
    the systems class (15-213, for anyone who cares). And what should
    we be doing in recitation but going over an example trick for the
    lab -- namely, the "absolute value" one!

    So I got to "show off" by putting the (x ^ x>>31) +1+~ (x>>31)
    solution on the chalkboard off the top of my head. ;-)

    -Arthur
    Arthur J. O'Dwyer, Sep 8, 2003
    #13
  14. Christopher Benson-Manica

    Paul Hsieh Guest

    Christopher Benson-Manica <> wrote in message news:<bjg33s$b10$>...
    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...
    >
    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    >
    > That works, but it assumes 32 bit integers. [...]


    It also assumes twos complement arithmetic. I.e., -x = 1+~x is true
    for twos complement, but not for example, in ones complement.
    Unfortunately, the ANSI C standard does not specify whether or not you
    can assume twos complement representations, so this whole idea is not
    really useful in C.

    Of course, it is highly unlikely you will ever encounter a non-twos
    complement machine ever in your life (and ones complement has been
    aggressively phased out pretty much everywhere), however the ANSI C
    standard does not take this into account.

    > [...] Is there a portable/standard way to do this?


    Syntactically or semantically? I mean, to be truly semantically
    portable you have to build up your own twos complement model from
    scratch. I suppose that's doable, but its also pure nonsense.

    > [...] Or are ANSI integers always 32 bits?


    Not ANSI C, however Java integers are always 32 bits, and the
    operators are always twos complement. So if you really really
    need/want to perform this trick and you actually need to be portable,
    you probably should switch to Java. ANSI C really doesn't have
    anything to offer you.

    > [...] If not, is using
    > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?


    Apparently bytes can be something other than 8 bits. I've seen people
    post things like "CHAR_BITS" in this newsgroup, however, I don't know
    whether that's part of any standard.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    Paul Hsieh, Sep 8, 2003
    #14
  15. "Malcolm" <> wrote in message
    news:bjg6sq$va$...
    >
    > "Christopher Benson-Manica" <> wrote in message
    > >
    > > are ANSI integers always 32 bits? If not, is using
    > > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?
    > >

    > Integers can be 16, 32 or very rarely another number of bits. chars are
    > usually 8 bits but 9 or 32 has occasionally been reported.
    >
    > using ( sizeof(int) * CHAR_BIT ) will be reasonably portable, but

    vulnerable
    > to padding bits. INT_MAX will give you the maximum value of an integer.
    > There is also no guarantee that your system uses two's complement
    > representation of negative numbers.


    I would think that preprocessor expressions could separate twos complement,
    ones complement, and sign magnitude.

    #if ~0==-1
    printf("twos complement\n");
    #elif ~0==-0
    printf("ones complement\n");
    #else
    printf("sign magnitude\n");
    #endif

    Then the three different bitwise absolute value expressions could be
    conditionally generated

    How about x&((~0>>1)) for sign magnitude?

    -- glen
    Glen Herrmannsfeldt, Sep 9, 2003
    #15
  16. "Carsten Hansen" <> wrote in message
    news:RBO6b.133003$...

    > Why not just (x ^ (x>>31)) - (x>>31)?
    > Good compilers will actually generate this code. It avoids a branch which

    is
    > important on today's processors.
    > Be aware that Sun has a patent on this method.


    Are you sure that works? It seems close but not right to me.

    Conditional load is designed to avoid branch. Don't most machines have an
    absolute value instruction?

    -- glen
    Glen Herrmannsfeldt, Sep 9, 2003
    #16
  17. Christopher Benson-Manica

    pete Guest

    Glen Herrmannsfeldt wrote:

    > #if ~0==-1
    > printf("twos complement\n");
    > #elif ~0==-0
    > printf("ones complement\n");
    > #else
    > printf("sign magnitude\n");
    > #endif
    >
    > Then the three different bitwise absolute value expressions could be
    > conditionally generated
    >
    > How about x&((~0>>1)) for sign magnitude?


    (~0) is not a portable expression.
    Representations which would equate to (-0), may be traps.

    --
    pete
    pete, Sep 9, 2003
    #17
  18. Christopher Benson-Manica

    Morris Dovey Guest

    Christopher Benson-Manica wrote:
    > I'm trying to compute the absolute value of an integer using only bitwise
    > operators...
    >
    > int x;
    > sscanf( "%d", &x );
    > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    >
    > That works, but it assumes 32 bit integers. Is there a portable/standard way
    > to do this? Or are ANSI integers always 32 bits? If not, is using
    > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?


    Hmm. If you're going to allow arithmetic operators, then how about:

    int my_abs(int x)
    { return x * ((x > 0) - (x < 0))
    }

    --
    Morris Dovey
    West Des Moines, Iowa USA
    C links at http://www.iedu.com/c
    Morris Dovey, Sep 9, 2003
    #18
  19. "Glen Herrmannsfeldt" <> wrote in message
    news:yua7b.396502$o%2.177909@sccrnsc02...
    >
    > "Carsten Hansen" <> wrote in message
    > news:RBO6b.133003$...
    >
    > > Why not just (x ^ (x>>31)) - (x>>31)?
    > > Good compilers will actually generate this code. It avoids a branch

    which
    > is
    > > important on today's processors.
    > > Be aware that Sun has a patent on this method.

    >
    > Are you sure that works? It seems close but not right to me.
    >


    Either it works or it doesn't. Give an example where it fails.
    Be aware that both Microsoft's and Intel's compiler generate the equivalent
    code

    value in eax
    cdq
    xor eax,edx
    sub eax,edx

    Also, the trick is mentioned in IBM's guide for compiler writers for the
    PowerPC.

    > Conditional load is designed to avoid branch. Don't most machines have an
    > absolute value instruction?
    >
    > -- glen
    >
    >


    They may have an instruction for taking the absolute value of a
    floating-point number. But neither the x86 nor the PowerPC have an
    instruction for taking the absolute value of a fixed-point number.

    Carsten Hansen
    Carsten Hansen, Sep 9, 2003
    #19
  20. Christopher Benson-Manica

    pete Guest

    Morris Dovey wrote:
    >
    > Christopher Benson-Manica wrote:
    > > I'm trying to compute the absolute value of an integer using only bitwise
    > > operators...
    > >
    > > int x;
    > > sscanf( "%d", &x );
    > > printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
    > >
    > > That works, but it assumes 32 bit integers.
    > > Is there a portable/standard way
    > > to do this? Or are ANSI integers always 32 bits? If not, is using
    > > sizeof(int) * 8 - 1 as the shift value an acceptable alternative?

    >
    > Hmm. If you're going to allow arithmetic operators, then how about:
    >
    > int my_abs(int x)
    > { return x * ((x > 0) - (x < 0))
    > }


    You also inserted relational operators.

    --
    pete
    pete, Sep 9, 2003
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Derk Gwen

    Re: bitwise absolute value

    Derk Gwen, Sep 10, 2003, in forum: C Programming
    Replies:
    7
    Views:
    714
    Arthur J. O'Dwyer
    Sep 11, 2003
  2. Chad
    Replies:
    9
    Views:
    349
    Coos Haak
    Jan 22, 2008
  3. John B. Matthews
    Replies:
    73
    Views:
    4,411
    John B. Matthews
    Nov 9, 2009
  4. Moe Sisko
    Replies:
    2
    Views:
    212
    Moe Sisko
    Jan 7, 2008
  5. James Byrne
    Replies:
    3
    Views:
    549
    James Byrne
    Sep 14, 2010
Loading...

Share This Page