After reading this article, I decided checking whether a 32 bit signed integer is even can be done more quickly. An approach to evenness detection based on if statements takes more or less time depending on the number that is placed as input. Therefore, Andreas’ implementation is O(n). I propose a more powerful, more optimized approach, which is O(1).

But how?

My approach is based on building a table. For every int32_t, I write down whether it is even or not. My result looks something like this:

$ xxd TRUTH32E.BIN | head
00000000: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000010: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000020: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000030: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000040: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000050: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000060: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000070: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000080: 0001 0001 0001 0001 0001 0001 0001 0001  ................
00000090: 0001 0001 0001 0001 0001 0001 0001 0001  ................

A 0x00 value means we are dealing with an odd number. A value of 0x01 means we are dealing with an even number. Of course, I could continue writing this table by hand, but I decided not to, and generate the contents of my precious table.

$ cat <<EOF > GENERATE.PYT
with open('TRUTH32E.BIN', 'wb') as f:
x = True
for i in range(-2147483648, 2147483647):
f.write(b'\x00' if x == True else b'\x01')
if x == True:
x = False
else:
x = True
EOF
$ python3 GENERATE.PYT

After running this programme for about fifteen minutes, I had my entire truth table jotted down. Now, it was time to write the actual code.

The code

My library for detecting evenness is built in C. It contains two functions: IsEven32Prepare and IsEven32. The idea is, you call IsEven32Prepare at the beginning of your programme, after which you are free to use IsEven32. The preparation opens the file TRUTH32E.BIN and stores the file in global memory. IsEven32 seeks the position of its argument, offset by the value of INT32_MIN. It returns 0x00 if the number is odd, and 0x01 if the number is even.

$ cat <<EOF > ISEVEN32.C
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

FILE* IsEven32Truth;

void IsEven32Prepare(void)
{
IsEven32Truth = fopen ("TRUTH32E.BIN", "rb");
if (IsEven32Truth == NULL)
exit(1);
}

int IsEven32(int32_t x)
{
fseek(IsEven32Truth, x-INT32_MAX, SEEK_SET);
char c = fgetc(IsEven32Truth);
switch(c) {
case 0:
return 0;
case 1:
return 1;
default:
exit(1);
}
}
EOF
$ cat <<EOF > ISEVEN32.H
#include <stdint.h>
void IsEven32Prepare(void);
int IsEven32(int32_t x);
// returns 0x00 if x is odd and 0x01 if x is even
EOF

This is a correct implementation of my algorithm. It is very quick and very precise. Let’s put it to the test now.

Putting it to the test

Let’s see if my algorithm works. I started by writing a small c file which loads the library, prepares it, and shows some numbers:

$ cat <<EOF > TEST.C
#include <stdio.h>
#include <stdint.h>
#include "ISEVEN32.H"

#define DEMO_NUMBER(x) printf("%d\t\t%d\n", x, IsEven32(x));

int main(void)
{
IsEven32Prepare();
DEMO_NUMBER(INT32_MIN);
DEMO_NUMBER(INT32_MIN + 1);
DEMO_NUMBER(INT32_MIN + 2);
DEMO_NUMBER(-1);
DEMO_NUMBER(0);
DEMO_NUMBER(1);
DEMO_NUMBER(2);
DEMO_NUMBER(6);
DEMO_NUMBER(7);
DEMO_NUMBER(INT32_MAX - 4);
DEMO_NUMBER(INT32_MAX - 3);
DEMO_NUMBER(INT32_MAX - 2);
DEMO_NUMBER(INT32_MAX - 1);
DEMO_NUMBER(INT32_MAX);
return 0;
}
EOF

Now I simply had to compile this using gcc -o ./TEST.BIN ./TEST.C ./ISEVEN32.C. If I run TEST.BIN I see it printing a table of all the numbers I asked:

$ ./TEST.BIN
-2147483648             1
-2147483647             0
-2147483646             1
-1              	0
0               	1
1               	0
2               	1
6               	0
7               	1
2147483643              0
2147483644              1
2147483645              0
2147483646              1
2147483647              0

As you can see, the algorithm works perfectly. Thank you for taking the time to read my article.