Quickest way for even numbers

[Darksun4]

Hi all!
I want to check whether a number is odd or even. I've made an algorithm
but I believe there should be a faster one ( maybe a macro ).
Here it goes :

int iseven ( int number )
{
int first;
int tempnum;

tempnum = number;

first = number >> 1;
number = first << 1;

if ( tempnum == number )
return 0;

return 1;
}
Thanks in advance

 

[Christian Haselbach]

I want to check whether a number is odd or even. I've made an algorithm
but I believe there should be a faster one ( maybe a macro ).
Here it goes :

int iseven ( int number )
{ return !(number % 2);
}

Alternatively: return (number & 1)^1

Ciao Chriss

 

[Emmanuel Delahaye]

Darksun4 a exprimé avec précision :

I want to check whether a number is odd or even. I've made an algorithm
but I believe there should be a faster one ( maybe a macro ).
Here it goes :

int iseven ( int number )

Identifiers beginning with is followed by lowercases are reserved for
future language extensions.

is_even() is fine (and additionally, readable).

{
int first;
int tempnum;

tempnum = number;

first = number >> 1;

Bitwise operators only work portably with unsigned integers.

number = first << 1;

DOn't shift anything if you want to go fast.

if ( tempnum == number )
return 0;

return 1;
}
Thanks in advance

What about

int is_even (long number)
{
return ((unsigned long) number & 0x1ul) == 0:
}

or

inline int is_even (long long number)
{
return (number & 0x1ull) == 0:
}

if you have C99.

Also consider an unsigned version of the functions

int is_even_ul (unsigned long number)

etc.

 

[Emmanuel Delahaye]

Emmanuel Delahaye avait prétendu :

inline int is_even (long long number)
{
return (number & 0x1ull) == 0:

return ((unsigned long long) number & 0x1ull) == 0:

 

[Christopher Benson-Manica]

I want to check whether a number is odd or even. I've made an algorithm
but I believe there should be a faster one ( maybe a macro ).

I suspect that you're not gaining much performance advantage over

!(number%2)

at the expense of quite a bit of clarity (IMHO). The overhead of the
function call probably more than offsets the possible penalty of using
the modulo operator.

int iseven ( int number )
{
int first;
int tempnum;

tempnum = number;

first = number >> 1;

If number happens to be negative, the results of this shift operation
are implmentation-defined.

number = first << 1;

 

[Christopher Benson-Manica]

Bitwise operators only work portably with unsigned integers.

According to my reading of K&R2, the result is also portable for
signed integers with positive values.

 

[Eric Sosman]

Darksun4 a exprimé avec précision :

I want to check whether a number is odd or even. [...]

What about

int is_even (long number)
{
return ((unsigned long) number & 0x1ul) == 0:
}

or

inline int is_even (long long number)
{
return (number & 0x1ull) == 0:
}

if you have C99.

"Premature optimization is the root of all evil," but
why not

inline int is_even(long long number) {
return ((unsigned int /* yes, int */) number & 1u) == 0;
}

... on the assumption that operations on `int'-sized data
may well be faster than on wider types.

 

[Dan Pop]

Darksun4 a exprim=E9 avec pr=E9cision :
=20

I want to check whether a number is odd or even. [...]

=20
=20
What about
=20
int is_even (long number)
{
return ((unsigned long) number & 0x1ul) =3D=3D 0:
}
=20
or
=20
inline int is_even (long long number)
{
return (number & 0x1ull) =3D=3D 0:
}
=20
if you have C99.

"Premature optimization is the root of all evil," but
why not

inline int is_even(long long number) {
return ((unsigned int /* yes, int */) number & 1u) =3D=3D 0;
}

=2E.. on the assumption that operations on `int'-sized data
may well be faster than on wider types.

Both are going to be unnecessarily slow on machines using
sign-magnitude, where the conversion from negative values to unsigned
values is actually changing representation. Unless the compiler is
smart enough to figure out the obfuscated intent, of course.

How about "return number % 2 == 0"; and letting the compiler choose the
best machine code sequence? We're no longer in the dark seventies, when
compilers had to fit into 64 KB and run on pathetically slow hardware...

The code generated from my version by gcc on x86, for a long int
parameter, is:

xorl %eax, %eax
testb $1, 4(%esp)
sete %al
ret

Dan

 

[Old Wolf]

Emmanuel Delahaye avait prétendu :


return ((unsigned long long) number & 0x1ull) == 0:

Why would you do that? Since one operand of the '&' is unsigned
long long, the other will be promoted to it without a cast.

More readable, would be:

return (number & 1) == 0;

or !(number & 1) if you prefer, as then the 1 (1 decimal = 1 hex)
will be promoted to match 'number'. I would even go for
'int' instead of 'long long' since I don't care about any
bits other than the least-significant one.

 

[Mark A. Odell]

The code generated from my version by gcc on x86, for a long int
parameter, is:

xorl %eax, %eax
testb $1, 4(%esp)
sete %al
ret

Pretty tight, with return (number % 2) == 0 I get

srawi r0,r3,1
addze r0,r0
mulli r0,r0,2
subf r12,r0,r3
cntlzw r3,r12
rlwinm r3,r3,27,5,31
blr

and with return (number & 1U) == 0;
rlwinm r12,r3,0,31,31
cntlzw r3,r12
rlwinm r3,r3,27,5,31
blr

with Diab 5.0.3. I guess Diab's not as smart as it could be. The var.
'number' is in r3 of course.

 

[Mark F. Haigh]

(e-mail address removed) (Dan Pop) wrote in news:[email protected]:

with Diab 5.0.3. I guess Diab's not as smart as it could be. The var.
'number' is in r3 of course.

<OT>
Given the absolutely shameful code I've seen in parts of certain
WindRiver products, I'm not too surprised. This is Compilers-101
stuff. Ugh.
</OT>


Mark F. Haigh
(e-mail address removed)

 

[Dan Pop]

Why would you do that? Since one operand of the '&' is unsigned
long long, the other will be promoted to it without a cast.

More readable, would be:

return (number & 1) == 0;

More readable, but less portable, as long as number has a signed type,
as is actually the case in the code under discussion.

I agree that Emmanuel is baroque, as usual, and his idea only requires

return (number & 1ULL) == 0;

because 1ULL is enough to force the conversion of number to unsigned
long long. But you're simplifying too much.

or !(number & 1) if you prefer, as then the 1 (1 decimal = 1 hex)
will be promoted to match 'number'. I would even go for
'int' instead of 'long long' since I don't care about any
bits other than the least-significant one.

Ever heard of one's complement? According to your version, -1 is an
even number on implementations using this representation. For maximal
portability, any micro-optimisation based on examining the LS bit must
ensure that the number is converted to an unsigned integer type.
And the cheapest way of doing that is by choosing the right type for
the mask.

Dan

 

[Old Wolf]

More readable, but less portable, as long as number has a signed type,
as is actually the case in the code under discussion.

I saw that he was casting to unsigned, which seemed indicate a lack of
interest in negative values. (But in fact doesn't, as you pointed out).

Ever heard of one's complement? According to your version, -1 is an
even number on implementations using this representation.

I wasn't sure. I've often heard "C works on values, not representations"
mentioned here, ie. (x & 1) should be the same regardless of
representation. I haven't ever had access to anything other than 2's c.,
so was unable to test it out.

 

[pete]

I saw that he was casting to unsigned, which seemed indicate a lack of
interest in negative values. (But in fact doesn't, as you pointed out).


I wasn't sure. I've often heard "C works on values,
not representations" mentioned here,
ie. (x & 1) should be the same regardless of
representation.

C works on values,
but sometimes representation counts for something,
especially with bitwise operators.

If you have
signed char integer = -1;
then
((unsigned char)integer)
would equal UCHAR_MAX on any implementation,


but
(*(unsigned char *)&integer)
would be equal to:
(UCHAR_MAX) on two's complement
(UCHAR_MAX - 1) on one's complement
(UCHAR_MAX / 2 + 2) on signed magnitude

 

[Dan Pop]

I saw that he was casting to unsigned, which seemed indicate a lack of
interest in negative values. (But in fact doesn't, as you pointed out).


I wasn't sure. I've often heard "C works on values, not representations"
mentioned here, ie. (x & 1) should be the same regardless of
representation.

4 Some operators (the unary operator ~, and the binary operators
<<, >>, &, ^, and |, collectively described as bitwise
operators) are required to have operands that have integer
type. These operators return values that depend on the internal
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
representations of integers, and have implementation-defined
^^^^^^^^^^^^^^^^^^^^^^^^^^^
and undefined aspects for signed types.

I haven't ever had access to anything other than 2's c.,
so was unable to test it out.

Neither had I, but I have a brain and can use it.

Dan

 

[Chris Torek]

[given a "test for even" program that just does "(number % 2) == 0"]

(e-mail address removed) (Dan Pop) wrote in news:[email protected]:

Pretty tight, with return (number % 2) == 0 I get

srawi r0,r3,1
addze r0,r0
mulli r0,r0,2
subf r12,r0,r3
cntlzw r3,r12
rlwinm r3,r3,27,5,31
blr

and with return (number & 1U) == 0;
rlwinm r12,r3,0,31,31
cntlzw r3,r12
rlwinm r3,r3,27,5,31
blr

with Diab 5.0.3. I guess Diab's not as smart as it could be.

I am not sure why we seem to consider Diab so wonderful myself.
Here is what I get using GCC ("ccpcc ... -O2 ...") for a tiny
"return (number % 2) == 0" function:

andi. 0,3,1
stwu 1,-16(1)
addi 1,1,16
mfcr 3
rlwinm 3,3,3,1
blr

I do not see the point of the manipulation of r1 here, but you can
see that the "mod 2" has been changed to "mask with constant 1"
(assuming you realize that "andi" takes two register numbers and
a constant, so that 0,3,1 means "put result in r0, mask r3 with
literal constant 1" -- ppc assembly gives me a headache -- and
in this case we really only want the condition codes for the later
mfcr).

If you use "(n & 1) == 0" you get an "xor" instead of an "and"
(with gcc), turning the code into "return (n ^ 1) & 1" in effect.
(The pointless stack manipulations -- stwu and addi -- persist.)