### Thread: Quick algorithm to determine odd/even numbers

1. #### Quick algorithm to determine odd/even numbers

Here's my first contribution to the algorithm forum. Most of you have probably written a function to determine if a number is even or odd as follows:

Code:
```BEGIN PSEUDOCODE

function odd(input_val)
begin
x = input_val mod 2;
if x == 1 then
return true;
else
return false;
end

END PSEUDOCODE```
Note that this function uses a modulo operation to determine the reminder, if you divide the number by 2. If there is a reminder, then this is an odd number, otherwise it is even. Seems fairly obvious right? What's not so obvious is that the modulo operator has to perform division to determine the reminder. The division operation eats up quite a few more CPU cycles than say an add operation. The method below is even faster:

Code:
```BEGIN PSEUDOCODE

function odd(input_val)
begin
if (x AND 1) == 1 then
return true;
else
return false;
end

END PSEUDOCODE```
Notice that this method uses a bitwise AND operation. If you look at any number in binary notation, you'll note that the Least Significant Bit (LSB) will always be set for odd numbers and cleared for even numbers. Hence, all that is necessary to determine if a number is even or odd is to check the LSB. Since bitwise operations like AND, OR, XOR etc. are usually much faster than the arithmetic operations, this method will run a lot faster. In languages like C, Perl, PHP etc, it is not even necessary to compare the value of the AND operation, since 0 is considered false and non-zero is true in these languages. So the function would simplify itself to:

Code:
```  int odd(int inputval) {
return inputval & 1;
}```
Now if you use the C++ keyword inline in the function declaration, then a C++ compiler may not even compile it as a function, but merely embed the one line function body into the code directly.

All comments/criticisms are welcome. Flames will be redirected to /dev/null
2. Here is an example that can evidence it better from an "assembler" view:

This is a sample C file:
Code:
```int pippo(int val)
{
return val % 2;
}

int pluto(int val)
{
return val & 1;
}```
This is the assembler generated by my c compiler for the hitachi micro ( a 16bit microcontroller ) :
Code:
```      1          int pippo(int val)
\                     pippo:
2          {
\   00000000   79050002           MOV.W   #2,R5
\   00000004   17F6               EXTS.L  ER6
\   00000006   01D05356           DIVXS.W R5,ER6
\   0000000A   0DE6               MOV.W   E6,R6
3            return val % 2;
\   0000000C   5470               RTS
4          }
5
6          int pluto(int val)
\                     pluto:
7          {
\   0000000E   79660001           AND.W   #1,R6
8            return val & 1;
\   00000012   5470               RTS
9          }```
The total "cycles" inside pluto function are 4 states.

The total "cycles" inside pippo function are 32 states.

So running a slow 16mhz micro ( one state == 62.5 ns ) it can make sensitive differences.

PS
I put the codes inside functions only to isolate the code better and for explaining the concept better and to avoid compiler optimizations.
Last edited by pippo; February 1st, 2002 at 02:10 AM.
3. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Jul 2001
Location
Oslo
Posts
1,516
Rep Power
18
Kinda strange that % 2 isn't optimized by the compiler the way * 2 is? (bitshift).
4. Code:
```      1          int pippo(int val)
\                     pippo:
2          {
\   00000000   79050002           MOV.W   #2,R5
\   00000004   17F6               EXTS.L  ER6
\   00000006   01D05356           DIVXS.W R5,ER6
3            return val / 2;
\   0000000A   5470               RTS
4          }
5
6          int pluto(int val)
\                     pluto:
7          {
\   0000000C   1096               SHAL.W  R6
8            return val * 2;
\   0000000E   5470               RTS
9          }
10
11          unsigned pippo_uns(unsigned val)
\                     pippo_uns:
12          {
\   00000010   1116               SHLR.W  R6
13            return val / 2;
\   00000012   5470               RTS
14          }
15
16          unsigned pluto_uns(unsigned val)
\                     pluto_uns:
17          {
\   00000014   1096               SHAL.W  R6
18            return val * 2;
\   00000016   5470               RTS```
mmmhhh...it optimizes only for unsigned, even if there is an instruction that could do it ( arithmetic shift )

PS Same for value % 2
Last edited by pippo; February 1st, 2002 at 02:36 AM.
5. #### Re: Quick algorithm to determine odd/even numbers

Originally posted by Scorpions4ever
Now if you use the C++ keyword inline in the function declaration, then a C++ compiler may not even compile it as a function, but merely embed the one line function body into the code directly.
You can also acomplish this same task by turning the function into a macro.

----

on another note...
It is amazing what you see when you look at the optimized asm from the compiler.
6. I tried the following code, compiled in gcc under FreeBSD running on an x86 machine:

Code:
```int modulo_odd(int x) {
return x % 2;
}

int bitwise_odd(int x) {
return x & 1;
}

unsigned modulo_oddu(unsigned x) {
return x % 2;
}

unsigned bitwise_oddu(unsigned x) {
return x & 1;
}```
Interestingly, when I compiled it with the -O2 optimization flags, the code generated for modulo_oddu and bitwise_oddu was IDENTICAL!:

Code:
```modulo_odd:
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%edx
movl %edx,%eax
shrl \$31,%eax
andb \$254,%al
subl %eax,%edx
movl %edx,%eax
leave
ret

bitwise_odd:
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax
andl \$1,%eax
leave
ret

modulo_oddu:
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax
andl \$1,%eax
leave
ret
bitwise_oddu:
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax
andl \$1,%eax
leave
ret```
7. Yeah, having to determine the sign make the difference, which is skipped for an unsigned variable, but some languages like php doesn't handle unsigned.
8. Quick method to test for odd/even numbers in PHP...

PHP Code:
``` <?php   function is_odd (\$i) {     if (is_int(\$i / 2)) {         return 0;     } else {         return 1;     }   } ?> ```
Last edited by deepspring; February 20th, 2002 at 08:32 PM.
9. deepspring? You lost me, what are you talking about?
10. Quick algorithm to determine odd/even numbers
Never mind, I will remove/edit/rewrite the post if you want... obviously I made a mistake. Was half asleep when typing it... I should never post when bored.

Funny thing is that I spent most of the night writting test scripts / apps on the subject in Python and Java...
11. No need in removing it. I know what you mean about doing thing half a sleep. I just didn't understand why you were doing it that way with the other examples in this thread.
12. Thankyou onslaught. Doing things half asleep can be pain for others, can't it. I wasn't sure if my post was on par with the thread...
13. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
May 2001
Location
dallas, texas
Posts
2
Rep Power
0
shift a
jc odd
14. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2003
Posts
1
Rep Power
0
Wouldn't this be the fastest routine?

Code:
```ROR eax,1
JS my_jump
stuff_if_even
JMP finished
my_jump:
stuff_if_odd
finished:```