# Even numbers

Is

```int even(int n)
{
return (n & 1);
}
```

a valid way of determining the evenness of a number? For unsigned integers, yes. For signed positive integers also yes. However, C99 6.2.6.2-2 states

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. [...] If the sign bit is one, the value shall be modified in one of the following ways

• the corresponding value with the sign bit 0 is negated (sign and magnitude);
• the sign bit has the value -(2:sup:N)(two's complement);
• the sign bit has the value -(2:sup:N - 1)(one's complement).

In other words, there are three possible representations of a signed integer in C, and one of them (one's complement) has a negative representation that fails the above test. However, I don't think there are actually any one's complement machines, so you're pretty safe.

However, Murphy's law dictates that eventually your code will run on some bizarre device that uses one's complement. Thus the best bet is to use a remainder (%) and let the compiler figure it out for you. Have a look at what the compiler gets up to for the most straight forward case:

```\$ cat test.c
int function(int i)
{
return (i % 2);
}

\$ gcc -O2 -S test.c
\$ cat test.s
.file   "test.c"
.text
.p2align 4,,15
.globl function
.type   function, @function
function:
pushl   %ebp
movl    %esp, %ebp
movl    8(%ebp), %eax
andl    \$-2147483647, %eax
js      .L5
popl    %ebp
ret
.p2align 4,,15
.L5:
decl    %eax
orl     \$-2, %eax
incl    %eax
popl    %ebp
ret
.size   function, .-function
.ident  "GCC: (GNU) 4.0.2 20050821 (prerelease) (Debian 4.0.1-6)"
.section        .note.GNU-stack,"",@progbits
```

It's a bit tricky because that remainder needs to account for negative values. So \$-2147483657 == -0x7FFFFFFF, which in two's complement is binary 1000 0000 0000 0000 0000 0000 0000 0001. So the andl checks the last bit just like we did before, however having the top bit set means that if the top bit is set in the other operand (i.e. the sign bit, indicating it is a negative number), the sign flag will be set and the js (jump on sign bit) will be triggered (that next bit at .L5 is a consequence of C99 6.5.5 6 where we have the relation (a/b)*b + a%b == a).

We can reduce the even function down to

```\$ cat test.c
int function(int i)
{
return ((unsigned int)i % 2);
}

\$ gcc -O2 -S test.c

\$ cat test.s
.file   "test.c"
.text
.p2align 4,,15
.globl function
.type   function, @function
function:
pushl   %ebp
movl    %esp, %ebp
movl    8(%ebp), %eax
andl    \$1, %eax
popl    %ebp
ret
.size   function, .-function
.ident  "GCC: (GNU) 4.0.2 20050821 (prerelease) (Debian 4.0.1-6)"
.section        .note.GNU-stack,"",@progbits
```

Which is the same as the original on this two's complement x86. In this trivial case the cast to unsigned could have been used with the original & 1 check and would have been OK, but my feeling is this the % is a little more clear (and if you need to worry about negative values your hand is forced).

I think the moral is to be worried whenever you pull out a bitwise operator and try to pass it off the work to the compiler (with a quick sanity check).