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