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]

Re: Quickest way for even numbers

Darksun4 <darky4sun@yaho o.gr> wrote:[color=blue]
> 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 )
> {[/color]
return !(number % 2);[color=blue]
> }[/color]

Alternatively: return (number & 1)^1

Ciao Chriss

[Emmanuel Delahaye]

Re: Quickest way for even numbers

Darksun4 a exprimé avec précision :[color=blue]
> 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 )[/color]

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

is_even() is fine (and additionally, readable).
[color=blue]
> {
> int first;
> int tempnum;
>
> tempnum = number;
>
> first = number >> 1;[/color]

Bitwise operators only work portably with unsigned integers.
[color=blue]
> number = first << 1;[/color]

DOn't shift anything if you want to go fast.
[color=blue]
> if ( tempnum == number )
> return 0;
>
> return 1;
> }
> Thanks in advance[/color]


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

[Emmanuel Delahaye]

Re: Quickest way for even numbers

Emmanuel Delahaye avait prétendu :
[color=blue]
> inline int is_even (long long number)
> {
> return (number & 0x1ull) == 0:[/color]

return ((unsigned long long) number & 0x1ull) == 0:
[color=blue]
> }[/color]

--


Emmanuel

[Christopher Benson-Manica]

Re: Quickest way for even numbers

Darksun4 <darky4sun@yaho o.gr> spoke thus:
[color=blue]
> 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 ).[/color]

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.
[color=blue]
> int iseven ( int number )
> {
> int first;
> int tempnum;[/color]
[color=blue]
> tempnum = number;[/color]
[color=blue]
> first = number >> 1;[/color]

If number happens to be negative, the results of this shift operation
are implmentation-defined.
[color=blue]
> number = first << 1;[/color]
[color=blue]
> if ( tempnum == number )
> return 0;[/color]
[color=blue]
> return 1;
> }[/color]

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Christopher Benson-Manica]

Re: Quickest way for even numbers

Emmanuel Delahaye <emdel@yourbran oos.fr> spoke thus:
[color=blue]
> Bitwise operators only work portably with unsigned integers.[/color]

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

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Eric Sosman]

Re: Quickest way for even numbers

Emmanuel Delahaye wrote:[color=blue]
> Darksun4 a exprimé avec précision :
> [color=green]
>> I want to check whether a number is odd or even. [...][/color]
>
>
> 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.[/color]

"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.

--
Eric.Sosman@sun .com

[Dan Pop]

Re: Quickest way for even numbers

In <40FD236E.50708 00@sun.com> Eric Sosman <Eric.Sosman@su n.com> writes:
[color=blue]
>Emmanuel Delahaye wrote:[color=green]
>> Darksun4 a exprim=E9 avec pr=E9cision :
>>=20[color=darkred]
>>> I want to check whether a number is odd or even. [...][/color]
>>=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.[/color]
>
> "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.[/color]

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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

[Old Wolf]

Re: Quickest way for even numbers

Emmanuel Delahaye <emdel@YOURBRAn oos.fr> wrote:[color=blue]
> Emmanuel Delahaye avait prétendu :
>[color=green]
> > inline int is_even (long long number)
> > {
> > return (number & 0x1ull) == 0:[/color]
>
> return ((unsigned long long) number & 0x1ull) == 0:
>[color=green]
> > }[/color][/color]

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]

Re: Quickest way for even numbers

Dan.Pop@cern.ch (Dan Pop) wrote in news:cdjdde$2de $6@sunnews.cern .ch:
[color=blue]
> 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[/color]

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

[Mark F. Haigh]

Re: Quickest way for even numbers

"Mark A. Odell" <odellmark@hotm ail.com> wrote in message news:<Xns952CAF 99864A4Copyrigh tMarkOdell@130. 133.1.4>...[color=blue]
> Dan.Pop@cern.ch (Dan Pop) wrote in news:cdjdde$2de $6@sunnews.cern .ch:[/color]
<snip>[color=blue]
>
> with Diab 5.0.3. I guess Diab's not as smart as it could be. The var.
> 'number' is in r3 of course.[/color]

<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
mfhaigh@sbcglob al.net

[Dan Pop]

Re: Quickest way for even numbers

In <843a4f78.04072 01250.76af95d5@ posting.google. com> oldwolf@inspire .net.nz (Old Wolf) writes:
[color=blue]
>Emmanuel Delahaye <emdel@YOURBRAn oos.fr> wrote:[color=green]
>> Emmanuel Delahaye avait prétendu :
>>[color=darkred]
>> > inline int is_even (long long number)
>> > {
>> > return (number & 0x1ull) == 0:[/color]
>>
>> return ((unsigned long long) number & 0x1ull) == 0:
>>[color=darkred]
>> > }[/color][/color]
>
>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;[/color]

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.
[color=blue]
>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.[/color]

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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

[Old Wolf]

Re: Quickest way for even numbers

Dan.Pop@cern.ch (Dan Pop) wrote:[color=blue]
> oldwolf@inspire .net.nz (Old Wolf) writes:[color=green]
> >Emmanuel Delahaye <emdel@YOURBRAn oos.fr> wrote:
> >[color=darkred]
> > > inline int is_even (long long number)
> > > {
> > > return (number & 0x1ull) == 0:[/color]
> >
> > return ((unsigned long long) number & 0x1ull) == 0:
> >[color=darkred]
> > > }[/color]
> >
> >More readable, would be:
> >
> > return (number & 1) == 0;[/color]
>
> More readable, but less portable, as long as number has a signed type,
> as is actually the case in the code under discussion.[/color]

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).
[color=blue]
> Ever heard of one's complement? According to your version, -1 is an
> even number on implementations using this representation.[/color]

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]

Re: Quickest way for even numbers

Old Wolf wrote:[color=blue]
>
> Dan.Pop@cern.ch (Dan Pop) wrote:[color=green]
> > oldwolf@inspire .net.nz (Old Wolf) writes:[color=darkred]
> > >Emmanuel Delahaye <emdel@YOURBRAn oos.fr> wrote:
> > >
> > > > inline int is_even (long long number)
> > > > {
> > > > return (number & 0x1ull) == 0:
> > >
> > > return ((unsigned long long) number & 0x1ull) == 0:
> > >
> > > > }
> > >
> > >More readable, would be:
> > >
> > > return (number & 1) == 0;[/color]
> >
> > More readable, but less portable, as long as number has a signed type,
> > as is actually the case in the code under discussion.[/color]
>
> 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).
>[color=green]
> > Ever heard of one's complement? According to your version, -1 is an
> > even number on implementations using this representation.[/color]
>
> 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.[/color]

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

--
pete

[Dan Pop]

Re: Quickest way for even numbers

In <843a4f78.04072 11507.55b4b238@ posting.google. com> oldwolf@inspire .net.nz (Old Wolf) writes:
[color=blue]
>Dan.Pop@cern.c h (Dan Pop) wrote:[color=green]
>> oldwolf@inspire .net.nz (Old Wolf) writes:[color=darkred]
>> >Emmanuel Delahaye <emdel@YOURBRAn oos.fr> wrote:
>> >
>> > > inline int is_even (long long number)
>> > > {
>> > > return (number & 0x1ull) == 0:
>> >
>> > return ((unsigned long long) number & 0x1ull) == 0:
>> >
>> > > }
>> >
>> >More readable, would be:
>> >
>> > return (number & 1) == 0;[/color]
>>
>> More readable, but less portable, as long as number has a signed type,
>> as is actually the case in the code under discussion.[/color]
>
>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).
>[color=green]
>> Ever heard of one's complement? According to your version, -1 is an
>> even number on implementations using this representation.[/color]
>
>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 .[/color]

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.
[color=blue]
>I haven't ever had access to anything other than 2's c.,
>so was unable to test it out.[/color]

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

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de