Finding if a number is even or odd, in C

[jcgalang]

Hi,

This is actually a C question, but I couldn't find a math section on codeguru's forums, so this is pretty much the only place I could find a math section. Anyways, we are supposed to write a recursive function that checks if the given parameter is even and returns 1 if it is, otherwise if it is odd, it will return 0. This is easy, except I cannot use division or modulo.

I was hoping someone could tell me the formula or the code for this. I have been racking my brains all day.

Thanks in advance,

John

[DiGiTaIErRoR]

Use bit logic:

(Number And 1) = 0 Then Even Else Odd

[Dreamlax]

Or in C:

inline int IsEven (int x)
{
    if ((x & 1) == 0) return 1;
    return 0;
} 

EDIT 1:
Wait... recursion?! Why would you want do multiple steps when it can be done in one? Did you consider the bit-shift operators? Technically it's division but not in the same sense...

EDIT 2:
Wait, perhaps if you wanted to calculate the number of 1-bits in an integer, you'd go:

inline int HasEvenBits (int x);
{
    int bitcount = 0;
    int counter = sizeof (int) * 8 - 1;
    while (counter--)
    {
        x >>= 1;
        bitcount += (x & 1);
    }
    if ((bitcount & 1) == 0) return 1;
    return 0;
} 

[DiGiTaIErRoR]

In binary if a number is odd the right bit(big endian) is 1, as this is the only 1 in binary. All the other bits represent powers of 2 which are of course, even.

1 = 1
10 = 2
11 = 3
100 = 4
101 = 5
110 = 6
111 = 7
1000 = 8
10000 = 16
100000 = 32
1000000 = 64
10000000 = 128
11111110 = 254

The only way a number can be odd, is if it has the plus one.

[sql_lall]

would this work:

inline bool IsEven (int x)
{
    return ( ( ( x >> 1 ) << 1 ) == x);
}

I know the AND one is better, but this looks nice. (however, not sure if it would work)

BTW, a recursinve one:

bool IsEven(int x)
{
    int absX = (x < 0) ? -1*x : x; // get absolute value
    return (absX > 1) ? !IsEven(absX-3) : (absX==0);
}

I haven't checked this, but it should *work*.
BTW, does C have () ? : ; ability. if not, can rewrite easily...

[kedaman]

inline bool IsEven (int x){
return !(x & 1);
}
can't get any simpler than that

[Dreamlax]

Only problem with kedaman's is that it does not entirely fit his requests. It must return 1, not true, if it is even :P. Just me being a fussy boots.

[kedaman]

true, and then we would have to put in the recursion somehow as well

[Dreamlax]

int IsEven (int x)
{
    if (x == 1) return 0;
    if (x == 0) return 1;
    return (IsEven (x - 2));
}

Just don't blame me when you get a stack overflow .

[jcgalang]

Hi,
I didn't except this many reply but they really did help. Since its a C program, I am thinking of doing it something like this:

Step 1. Gets the number (lets call it nNum)
Step 2. Starts from 0 and starts adding 2 (lets call this variable nEvenOdd)

Every time it will check If nEvenOdd < nNum, and if so it will continue adding 2. Else If nEvenOdd > nNum it will return 0, Else If nEvenOdd = nNum, it will return 1.

In theory if the nNum is say 16, then 0 + 2 + 2 + 2....= 16, therefore meaning that nNum = nEvenOdd, therefore even.

Any suggestions to iprove this theory.

John

[sw_is_great]

in c/c++

if (x%2==0)
even
else
odd

[sw_is_great]

i think 0 is a special case

[kedaman]

sw_is_great: read the question before you post

jcgalang: go with dreamlax one, it is the same thing but top down rather than bottom up (recursion is most intuitively top-down) start with something asked, and then go toward the special case.

[sw_is_great]

sorry boss

i went by the subject name

[DiGiTaIErRoR]

So... you can't use division, what's stopping you from:

If CInt(Num * .5) * 2 = Num Then do_something

Where Num is an integer.

[Dreamlax]

Perhaps because that isn't recursive, but still, any function must be more efficient than the one I wrote.