the fastest way to do an odd/even check?

Discussion in 'C++' started by Klaas Vantournhout, Feb 1, 2007.

  1. Hi,

    I have a question, which is just out of interest.
    What is the fastest way to do an odd/even check with c++ and if needed
    assembler.

    Assume n is an unsigned integer like type (unsigned int, unsigned long
    int), what is the fastest?

    using the modulo operator

    a) if (n%2 == 0) then even
    b) if (n%2 == 1) then odd
    c) if (n%2 != 1) then even
    d) if (n%2 != 0) then odd

    using the bit shift operator

    e) if ((n >> 1) << 1 == n) then even
    f) if ((n >> 1) << 1 != n) then odd
    g) if (((n >> 1) << 1) - n == 0) then even
    h) if (n - ((n >> 1) << 1) == 1) then odd

    They always told me that checking against '0' is the best for "speed",
    if you can call it speed here ;-), thus this rules out b and c for sure.

    But what would it be? I think bitshifts are faster then modulo
    calculations. Is this right?

    The most fast would be checking the last bit in the binary array. Is it
    1, then it is odd else it is even. Can you do bitchecks in a number
    with c++?

    I can think of a rule, assume you want to check bit 5, you can do

    n & (1<<5) == (1<<5)

    but this is for sure not faster then just reading the bit. Because you
    do 64 operations with the & and 64 operations with the checking, which
    is much more then 2 operations.

    So I was just wondering.
    Anybody an idea?

    Thanks
    Klaas
     
    Klaas Vantournhout, Feb 1, 2007
    #1
    1. Advertising

  2. * Klaas Vantournhout:
    > Hi,
    >
    > I have a question, which is just out of interest.
    > What is the fastest way to do an odd/even check with c++ and if needed
    > assembler.
    >
    > Assume n is an unsigned integer like type (unsigned int, unsigned long
    > int), what is the fastest?
    >
    > using the modulo operator
    >
    > a) if (n%2 == 0) then even
    > b) if (n%2 == 1) then odd
    > c) if (n%2 != 1) then even
    > d) if (n%2 != 0) then odd
    >
    > using the bit shift operator
    >
    > e) if ((n >> 1) << 1 == n) then even
    > f) if ((n >> 1) << 1 != n) then odd
    > g) if (((n >> 1) << 1) - n == 0) then even
    > h) if (n - ((n >> 1) << 1) == 1) then odd
    >
    > They always told me that checking against '0' is the best for "speed",
    > if you can call it speed here ;-), thus this rules out b and c for sure.
    >
    > But what would it be? I think bitshifts are faster then modulo
    > calculations. Is this right?
    >
    > The most fast would be checking the last bit in the binary array. Is it
    > 1, then it is odd else it is even. Can you do bitchecks in a number
    > with c++?
    >
    > I can think of a rule, assume you want to check bit 5, you can do
    >
    > n & (1<<5) == (1<<5)
    >
    > but this is for sure not faster then just reading the bit. Because you
    > do 64 operations with the & and 64 operations with the checking, which
    > is much more then 2 operations.
    >
    > So I was just wondering.
    > Anybody an idea?


    The assumptions about speeds of various operations above are plain
    wrong. It depends on the compiler and the computer (and more). Also,
    the assumptions about number of operations involved in bit shifting are
    plain wrong.

    Don't try to optimize at this level: let the compiler do it. If you
    think you have to optimize, first /measure/. And that doesn't mean
    measuring operations, it means measuring where your code spends its
    time, i.e. getting hard data on what may benefit from optimization.

    Even better, don't try to optimize basic operations, at all, but do
    choose reasonably efficient algorithms.

    Finally, please read the FAQ before posting.

    The FAQ contains much good advice, I believe also about the above.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Feb 1, 2007
    #2
    1. Advertising

  3. On Feb 1, 3:29 pm, Klaas Vantournhout <> wrote:
    > Hi,
    >
    > I have a question, which is just out of interest.
    > What is the fastest way to do an odd/even check with c++ and if needed
    > assembler.
    >
    > Assume n is an unsigned integer like type (unsigned int, unsigned long
    > int), what is the fastest?
    >
    > using the modulo operator
    >
    > a) if (n%2 == 0) then even
    > b) if (n%2 == 1) then odd
    > c) if (n%2 != 1) then even
    > d) if (n%2 != 0) then odd


    I would assume all of those to take the same amount of time on a
    modern CPU, though see my comment on comparing against 0 a bit down.

    > e) if ((n >> 1) << 1 == n) then even
    > f) if ((n >> 1) << 1 != n) then odd
    > g) if (((n >> 1) << 1) - n == 0) then even
    > h) if (n - ((n >> 1) << 1) == 1) then odd


    These does not look particularly fast to me, many operations. But it
    might be faster than modulo, I don't know how that's done in the CPU.

    > They always told me that checking against '0' is the best for "speed",
    > if you can call it speed here ;-), thus this rules out b and c for sure.
    >
    > But what would it be? I think bitshifts are faster then modulo
    > calculations. Is this right?


    On some CPUs there's a special register for the value 0 while other
    values might have to be loaded into a register first.

    > The most fast would be checking the last bit in the binary array. Is it
    > 1, then it is odd else it is even. Can you do bitchecks in a number
    > with c++?


    Bitwise compare:
    if (n | 0x1) then odd
    this is probably the fastest way.

    > I can think of a rule, assume you want to check bit 5, you can do
    >
    > n & (1<<5) == (1<<5)


    Better would be
    if (n | 0x10)

    >
    > but this is for sure not faster then just reading the bit. Because you
    > do 64 operations with the & and 64 operations with the checking, which
    > is much more then 2 operations.


    64 operations? Shifting is 1 operation and & is one operation and
    compare is 1, since there are two shifts that adds up to 4 operations.

    > So I was just wondering.
    > Anybody an idea?


    If you are wondering these kinds of things you should either go and
    read up some on how computers works and assembly programming. Or you
    are trying to optimize something, in which case I'd advice you to do
    some profiling before trying to speed up that operation, it's most
    probably not the slowest one in a program.

    If you want to know how these things work on modern CPUs you can
    download a lot of stuff from Intel: http://www.intel.com/products/processor/manuals/index.htm
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Feb 1, 2007
    #3
  4. Erik Wikström wrote:
    > If you are wondering these kinds of things you should either go and
    > read up some on how computers works and assembly programming. Or you
    > are trying to optimize something, in which case I'd advice you to do
    > some profiling before trying to speed up that operation, it's most
    > probably not the slowest one in a program.
    >
    > If you want to know how these things work on modern CPUs you can
    > download a lot of stuff from Intel: http://www.intel.com/products/processor/manuals/index.htm

    Thanks for your response Erik,

    It was for sure not my intention of optimizing this, but it was just a
    curiosity! You are absolutely right that this is more related to the
    compiler, assembler and the CPU.

    If that process would have been the slowest process in the code ... then
    I can imagine that something is seriously wrong with the code ;-)

    regards

    Klaas
     
    Klaas Vantournhout, Feb 1, 2007
    #4
  5. Klaas Vantournhout

    JLS Guest

    On Feb 1, 9:29 am, Klaas Vantournhout <> wrote:
    > Hi,
    >
    > I have a question, which is just out of interest.
    > What is the fastest way to do an odd/even check with c++ and if needed
    > assembler.
    >
    > Assume n is an unsigned integer like type (unsigned int, unsigned long
    > int), what is the fastest?
    >
    > using the modulo operator
    >
    > a) if (n%2 == 0) then even
    > b) if (n%2 == 1) then odd
    > c) if (n%2 != 1) then even
    > d) if (n%2 != 0) then odd
    >
    > using the bit shift operator
    >
    > e) if ((n >> 1) << 1 == n) then even
    > f) if ((n >> 1) << 1 != n) then odd
    > g) if (((n >> 1) << 1) - n == 0) then even
    > h) if (n - ((n >> 1) << 1) == 1) then odd
    >
    > They always told me that checking against '0' is the best for "speed",
    > if you can call it speed here ;-), thus this rules out b and c for sure.
    >
    > But what would it be? I think bitshifts are faster then modulo
    > calculations. Is this right?
    >
    > The most fast would be checking the last bit in the binary array. Is it
    > 1, then it is odd else it is even. Can you do bitchecks in a number
    > with c++?
    >
    > I can think of a rule, assume you want to check bit 5, you can do
    >
    > n & (1<<5) == (1<<5)
    >
    > but this is for sure not faster then just reading the bit. Because you
    > do 64 operations with the & and 64 operations with the checking, which
    > is much more then 2 operations.
    >
    > So I was just wondering.
    > Anybody an idea?
    >
    > Thanks
    > Klaas


    I worked at one job where this was a standard interview question, but
    that was many languages, many computers, and many years ago. It
    started a discussion of all the ways one could test for odd/even. Some
    languages contain an "IsOdd" method. The usual method at the time was
    to divide by 2, multply by two and see if you have the same number
    (even) or not (odd). Back then, there were different method of storing
    numbers so the shift method was not portable. When the moduler
    operation became standard, some people shifted to that.

    btw: The slowest method that I ever saw implemented was to subtract 2
    over and over again until the number was less than two and then the
    result was compared to 1. Needless to say, the implementer became an
    ex-programmer.
     
    JLS, Feb 1, 2007
    #5
  6. Klaas Vantournhout

    Heinz Ozwirk Guest

    "Erik Wikström" <> schrieb im Newsbeitrag
    news:...
    >> using the modulo operator
    >>
    >> a) if (n%2 == 0) then even
    >> b) if (n%2 == 1) then odd
    >> c) if (n%2 != 1) then even
    >> d) if (n%2 != 0) then odd

    >
    > I would assume all of those to take the same amount of time on a
    > modern CPU, though see my comment on comparing against 0 a bit down.
    >
    >> e) if ((n >> 1) << 1 == n) then even
    >> f) if ((n >> 1) << 1 != n) then odd
    >> g) if (((n >> 1) << 1) - n == 0) then even
    >> h) if (n - ((n >> 1) << 1) == 1) then odd

    >
    > These does not look particularly fast to me, many operations. But it
    > might be faster than modulo, I don't know how that's done in the CPU.

    ....
    > Bitwise compare:
    > if (n | 0x1) then odd
    > this is probably the fastest way.


    This is probably the fastes of all operations mentioned here. Any decent
    compile should recognize that n|1 is always true.

    >> I can think of a rule, assume you want to check bit 5, you can do
    >>
    >> n & (1<<5) == (1<<5)

    >
    > Better would be
    > if (n | 0x10)


    Both look terrible, but the second is plain wrong. To test a single bit you
    have to use & instead of |. Using | with a non-zero constant will give a
    non-zero result. My prefered way to test the state of the single bit is

    if (n & (1 << x)) // even if x is 0

    If the compiler cannot replace such constant sub-expressions at compile
    time, it shouldn't be used at all. Even the oldest C compilers could do
    that.

    To the OP: Most modern compilers should recognize what expressions like n%2
    or n&1 are suposed to do and optimize them, probably to the same code. So
    use whatever is more readable to you and those (humans) who are supposed to
    read your code. Using % looks like a mathmatican's approach, & like an
    assembly language programmer's. The shifting orgy in e - g, however, looks
    like a mad sicentist's code.

    Heinz
     
    Heinz Ozwirk, Feb 1, 2007
    #6
  7. "Heinz Ozwirk" <> wrote in message
    news:45c24ce5$0$18846$-online.net...
    > "Erik Wikström" <> schrieb im Newsbeitrag
    > news:...
    >> Better would be
    >> if (n | 0x10)

    >
    > Both look terrible, but the second is plain wrong. To test a single bit
    > you have to use & instead of |.


    Indeed. Besides, 1<<5 == 0x20, not 0x10
    >
    > To the OP: Most modern compilers should recognize what expressions like
    > n%2 or n&1 are suposed to do and optimize them, probably to the same code.


    For unsigned integers, perhaps, but certainly not always for signed integers
    as -1 % 2 == -1 on most architectures.

    - Sylvester
     
    Sylvester Hesp, Feb 2, 2007
    #7
    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. Patrick

    odd and even signals

    Patrick, Dec 21, 2004, in forum: VHDL
    Replies:
    1
    Views:
    2,810
    Jonathan Bromley
    Dec 21, 2004
  2. crazyrdx

    even or odd

    crazyrdx, Aug 31, 2005, in forum: VHDL
    Replies:
    3
    Views:
    1,733
  3. Stan Goodman

    Even older fart, even newer newbie

    Stan Goodman, Jul 3, 2003, in forum: Java
    Replies:
    11
    Views:
    710
    Stan Goodman
    Jul 4, 2003
  4. Lin
    Replies:
    25
    Views:
    39,189
    taraval
    Feb 4, 2011
  5. wswilson
    Replies:
    16
    Views:
    453
Loading...

Share This Page