odd/even bitwise and

Discussion in 'C Programming' started by Serve Laurijssen, Apr 6, 2004.

  1. Some people prefer to use
    "if (x & 1)"
    to see if a number is odd or even. Is this completely portable according to
    the standard?
     
    Serve Laurijssen, Apr 6, 2004
    #1
    1. Advertising

  2. "Serve Laurijssen" <> wrote in message
    news:eJucc.5394$RU5.83970@zonnet-reader-1...
    > "if (x & 1)"
    > to see if a number is odd or even. Is this completely portable according

    to
    > the standard?


    I don't know what does this have to do with the standard, but the thing is
    an odd number will ALWAYS have bit 0 set to '1' and an even number will
    always have bit 0 set to '0'. This is a matter of binary representation.

    Ahmed
     
    Ahmed S. Badran, Apr 6, 2004
    #2
    1. Advertising

  3. Serve Laurijssen

    CBFalconer Guest

    Serve Laurijssen wrote:
    >
    > Some people prefer to use
    > "if (x & 1)"
    > to see if a number is odd or even. Is this completely portable
    > according to the standard?


    Only if x is some form of unsigned integer.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Apr 6, 2004
    #3
  4. Serve Laurijssen

    pete Guest

    Serve Laurijssen wrote:
    >
    > Some people prefer to use
    > "if (x & 1)"
    > to see if a number is odd or even.
    > Is this completely portable according to the standard?


    If x is an unsigned integer type
    or a signed type with a non negative value, then it's portable.

    --
    pete
     
    pete, Apr 6, 2004
    #4
  5. Serve Laurijssen

    pete Guest

    Ahmed S. Badran wrote:
    >
    > "Serve Laurijssen" <> wrote in message
    > news:eJucc.5394$RU5.83970@zonnet-reader-1...
    > > "if (x & 1)"
    > > to see if a number is odd or even.
    > > Is this completely portable according to the standard?

    >
    > I don't know what does this have to do with the standard,


    The answer to the question, is in the standard.

    > but the thing is an odd number will ALWAYS have bit 0 set to
    > '1' and an even number will always have bit 0 set to '0'.


    That's not true for one's complement
    representations of negative integers.

    > This is a matter of binary representation.


    The standard specifies more than one
    way to represent negative integers.

    --
    pete
     
    pete, Apr 6, 2004
    #5
  6. Serve Laurijssen

    osmium Guest

    Ahmed S. Badran writes:

    > > "if (x & 1)"
    > > to see if a number is odd or even. Is this completely portable according

    > to
    > > the standard?

    >
    > I don't know what does this have to do with the standard, but the thing is
    > an odd number will ALWAYS have bit 0 set to '1' and an even number will
    > always have bit 0 set to '0'. This is a matter of binary representation.


    It depends on the hardware. If x is a one's complement representation of 0
    the test might fail. It strikes me as code intended to impress someone with
    one's erudition, I would not do it.
     
    osmium, Apr 6, 2004
    #6
  7. pete wrote:
    > Ahmed S. Badran wrote:
    >>
    >> "Serve Laurijssen" <> wrote in message
    >> news:eJucc.5394$RU5.83970@zonnet-reader-1...
    >>> "if (x & 1)"
    >>> to see if a number is odd or even.
    >>> Is this completely portable according to the standard?

    >>
    >> I don't know what does this have to do with the standard,

    >
    > The answer to the question, is in the standard.
    >
    >> but the thing is an odd number will ALWAYS have bit 0 set to
    >> '1' and an even number will always have bit 0 set to '0'.

    >
    > That's not true for one's complement
    > representations of negative integers.
    >
    >> This is a matter of binary representation.

    >
    > The standard specifies more than one
    > way to represent negative integers.

    Ok, just to re-elaborate and make the answer complete, I never took negative
    numbers into consideration with my previous answer, so my previous answer is
    valid/correct with all positive integers. Thanks for pointing that out guys.

    Ahmed
     
    Ahmed S. Badran, Apr 6, 2004
    #7
  8. Serve Laurijssen wrote:
    > Some people prefer to use
    > "if (x & 1)"
    > to see if a number is odd or even. Is this completely portable according to
    > the standard?


    No. That is only possible if the representation of the integers use
    twos-complement.

    To see if a number is odd or even, use the modulus operator (e.g., x%2).

    --
    =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    Rogério Brito - - http://www.ime.usp.br/~rbrito
    =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
     
    =?ISO-8859-1?Q?Rog=E9rio_Brito?=, Apr 6, 2004
    #8
  9. Serve Laurijssen

    Mark Henning Guest

    Rogério Brito wrote:
    > No. That is only possible if the representation of the integers use
    > twos-complement.
    >
    > To see if a number is odd or even, use the modulus operator (e.g., x%2).


    That is the way that I have always done it, although it occurs to me
    that AND-ing a value with one may be a significantly simpler computation
    than calculating the remainder of a divide by two in the majority of
    circumstances. This method might be worth considering for unsigned
    integers.

    M. Henning.
     
    Mark Henning, Apr 6, 2004
    #9
  10. Serve Laurijssen

    Chris Torek Guest

    In article <news:c4ukgf$2ce$>
    Mark Henning <> writes:
    >[using % to obtain integer remainder after division] is the way that
    >I have always [tested for even/odd], although it occurs to me
    >that AND-ing a value with one may be a significantly simpler computation
    >than calculating the remainder of a divide by two in the majority of
    >circumstances. This method might be worth considering for unsigned
    >integers.


    This is true; but at the same time, on any machine where it matters,
    any optimizing compiler worthy of the word "optimizing" should turn:

    x % constant

    into:

    x & (constant - 1)

    whenever the given constant is a power of two, because these always
    produce the same result (for an unsigned x).

    For signed integers (and still power-of-two constants), the process
    is a bit more difficult -- a typical two's complement signed integer
    gives different answers for "x % CONST" and "x & (CONST-1)" when
    x is negative. There are bit-twiddling tricks that can be used if
    the value is required, though; and if only the "truth-ness" of the
    value is of interest, the above transform again works. That is:

    if (x % 8)

    and:

    if (x & 7)

    are both true (or false) in the same sets of cases, even when x is
    signed, as long as the machine uses two's complement. This allows
    an optimizing compiler to "do the right thing".
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Apr 6, 2004
    #10
  11. Mark Henning wrote:
    > That is the way that I have always done it, although it occurs to me
    > that AND-ing a value with one may be a significantly simpler computation
    > than calculating the remainder of a divide by two in the majority of
    > circumstances. This method might be worth considering for unsigned
    > integers.


    Sure, if you can assume certain things about the platform, then you can
    usually make some things slightly more efficient. But then the code is
    not portable anymore, which was what started the thread.

    And you might argue that the code is a little bit more obfuscated, since
    it is not expressing what you wanted in the first place (seeing the
    remainder of the division by two).

    These small optimizations are what Knuth is talking about when he says
    that "premature optimization is the root of all evil".

    And, of course, a smart compiler could very well see that the target
    platform uses a twos-complement and transform the particular cases of
    remainders modulo a power of two into a corresponding bitwise AND
    operation. The same for multiplying or dividing by a power of two and
    using appropriate shift operations.


    --
    =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    Rogério Brito - - http://www.ime.usp.br/~rbrito
    =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
     
    =?ISO-8859-1?Q?Rog=E9rio_Brito?=, Apr 6, 2004
    #11
  12. Serve Laurijssen

    Eric Sosman Guest

    Mark Henning wrote:
    >
    > Rogério Brito wrote:
    > > No. That is only possible if the representation of the integers use
    > > twos-complement.
    > >
    > > To see if a number is odd or even, use the modulus operator (e.g., x%2).

    >
    > That is the way that I have always done it, although it occurs to me
    > that AND-ing a value with one may be a significantly simpler computation
    > than calculating the remainder of a divide by two in the majority of
    > circumstances. This method might be worth considering for unsigned
    > integers.


    What fraction of your program's running time is expended
    on determining whether a number is even or odd? One percent
    seems high, but let's be generous and suppose your design calls
    for a really large number of such determinations. All right,
    how much faster might "and" be than "remainder?" Machine-
    specific, of course, but let's again be generous and suppose
    "modulus" takes whatever it takes while "and" is infinitely
    faster, taking zero time. Switching from "modulus" to "and"
    would speed up your program by ...

    << May I have the envelope, please? >>

    ... a WHOPPING one percent! WOW!!!

    If your other problems are so insignificant that something
    this tiny becomes important, you are to be envied.

    --
     
    Eric Sosman, Apr 6, 2004
    #12
  13. On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
    <> wrote:
    >so my previous answer is
    >valid/correct with all positive integers.


    Unless, of course, there are padding bits in the integer. The only
    correct way to test for mathematical even or odd is to use a mathematical
    expression.


    --
    #include <standard.disclaimer>
    _
    Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
    Per the FCA, this address may not be added to any commercial mail list
     
    Kevin D. Quitt, Apr 6, 2004
    #13
  14. Serve Laurijssen wrote:

    > Some people prefer to use
    > "if (x & 1)"
    > to see if a number is odd or even. Is this completely portable according to
    > the standard?
    >

    NO.
     
    Martin Ambuhl, Apr 6, 2004
    #14
  15. Serve Laurijssen

    pete Guest

    Rogério Brito wrote:
    >
    > Serve Laurijssen wrote:
    > > Some people prefer to use
    > > "if (x & 1)"
    > > to see if a number is odd or even.
    > > Is this completely portable according to the standard?

    >
    > No. That is only possible if the representation of the integers use
    > twos-complement.


    It's also possible with Sign and Magnitude representation.

    --
    pete
     
    pete, Apr 6, 2004
    #15
  16. Serve Laurijssen

    pete Guest

    Kevin D. Quitt wrote:
    >
    > On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
    > <> wrote:
    > >so my previous answer is
    > >valid/correct with all positive integers.

    >
    > Unless, of course, there are padding bits in the integer.


    Makes no difference if there are padding bits in the integer.
    (x & 1) is true for all positive odd int x, regardless of padding.

    --
    pete
     
    pete, Apr 7, 2004
    #16
  17. pete wrote:
    > Rogério Brito wrote:
    >
    >>Serve Laurijssen wrote:
    >>
    >>>Some people prefer to use
    >>>"if (x & 1)"
    >>>to see if a number is odd or even.
    >>>Is this completely portable according to the standard?

    >>
    >>No. That is only possible if the representation of the integers use
    >>twos-complement.

    >
    >
    > It's also possible with Sign and Magnitude representation.
    >


    Wouldn't that be "signed magnitude"? Or are there some other
    representations I'm missing out on?

    (The ones I know of are signed magnitude, one's complement, and two's
    complement.)

    --
    yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
    To email me, rot13 and convert spelled-out numbers to numeric form.
    "Makes hackers smile" makes hackers smile.
     
    August Derleth, Apr 7, 2004
    #17
  18. On Tue, 6 Apr 2004, August Derleth wrote:
    >
    > pete wrote:
    > > Rogério Brito wrote:
    > >>
    > >>No. That is only possible if the representation of the integers use
    > >>twos-complement.

    > >
    > > It's also possible with Sign and Magnitude representation.

    >
    > Wouldn't that be "signed magnitude"? Or are there some other
    > representations I'm missing out on?
    >
    > (The ones I know of are signed magnitude, one's complement, and two's
    > complement.)


    No. The canonical phrase is "sign-magnitude representation,"
    which refers to the fact that S-M representation is one in which
    the ign of the number is separated from the [M]agnitude. That
    is, you have one bit for the sign and the rest for the magnitude,
    unlike two's-complement or ones'-complement, in which the sign is
    sort of "tied up with" the magnitude in an icky way. ;-)
    I believe I've got the apostrophes in the right places above.
    Knuth, IIRC, says in TAOCP why he writes the apostrophes where he
    does. Ones' complement, plural possessive, because you're XORing
    the number with a bunch of ones (111111...) to negate it. Two's
    complement, singular possessive, because you're doing something or
    other with a power of two.

    You're not missing any representation methods allowed by the C
    standard, although I'm sure there are many more outlandish ones
    out there.

    HTH,
    -Arthur
     
    Arthur J. O'Dwyer, Apr 7, 2004
    #18
  19. On Tue, 6 Apr 2004 13:39:08 +0200, "Ahmed S. Badran"
    <> wrote:

    >
    >"Serve Laurijssen" <> wrote in message
    >news:eJucc.5394$RU5.83970@zonnet-reader-1...
    >> "if (x & 1)"
    >> to see if a number is odd or even. Is this completely portable according

    >to
    >> the standard?

    >
    >I don't know what does this have to do with the standard, but the thing is
    >an odd number will ALWAYS have bit 0 set to '1' and an even number will
    >always have bit 0 set to '0'. This is a matter of binary representation.
    >

    There are systems where bit 0 is the high order or sign bit, not the
    low order one.


    <<Remove the del for email>>
     
    Barry Schwarz, Apr 7, 2004
    #19
  20. On Tue, 06 Apr 2004 23:01:26 GMT, pete <> wrote:


    >Kevin D. Quitt wrote:
    >>
    >> On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
    >> <> wrote:
    >> >so my previous answer is
    >> >valid/correct with all positive integers.

    >>
    >> Unless, of course, there are padding bits in the integer.

    >
    >Makes no difference if there are padding bits in the integer.
    >(x & 1) is true for all positive odd int x, regardless of padding.


    According to what?


    --
    #include <standard.disclaimer>
    _
    Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
    Per the FCA, this address may not be added to any commercial mail list
     
    Kevin D. Quitt, Apr 8, 2004
    #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. dohnut
    Replies:
    0
    Views:
    547
    dohnut
    Oct 20, 2003
  2. dohnut
    Replies:
    1
    Views:
    586
    Sam Holden
    Oct 21, 2003
  3. dohnut
    Replies:
    0
    Views:
    584
    dohnut
    Oct 21, 2003
  4. Stan Goodman

    Even older fart, even newer newbie

    Stan Goodman, Jul 3, 2003, in forum: Java
    Replies:
    11
    Views:
    702
    Stan Goodman
    Jul 4, 2003
  5. dohnut
    Replies:
    7
    Views:
    133
    Tad McClellan
    Oct 21, 2003
Loading...

Share This Page