the fastest way to do an odd/even check?

[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?

Thanks
Klaas

[Alf P. Steinbach]

* 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?

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

On Feb 1, 3:29 pm, Klaas Vantournhout <no_valid_em... @spam.comwrote:

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/proces...uals/index.htm

[Klaas Vantournhout]

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/proces...uals/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

[JLS]

On Feb 1, 9:29 am, Klaas Vantournhout <no_valid_em... @spam.comwrote:

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.

[Heinz Ozwirk]

"Erik Wikström" <er****@student .chalmers.sesch rieb im Newsbeitrag
news:11******** **************@ a75g2000cwd.goo glegroups.com.. .

>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

[Sylvester Hesp]

"Heinz Ozwirk" <SP*********@ar cor.dewrote in message
news:45******** *************** @newsspool4.arc or-online.net...

"Erik Wikström" <er****@student .chalmers.sesch rieb im Newsbeitrag
news:11******** **************@ a75g2000cwd.goo glegroups.com.. .

>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