Testing Odd/Even Using Bitwise AND

I came to the programming world by way of an Apple II, TI 99/4A, BASIC, VB/VBA and on to C#. But my academic experience is in the world of economics, not computer science. So occasionally I come across things that are really basic (I assume) which I have clearly forgotten somewhere between Apple Basic, High School Electronics, and the ensuing decades of other trivia crammed into my brain.

The Bitwise AND is the operator that left me feeling stupid today.

Many times in my career I’ve come across code to test whether a number is odd or even. Usually I have done or seen modulo division by 2 and a comparison of the remainder.

public static bool IsOdd(int i)
{
    return ((i % 2) == 1);
}

Today I came across:

public static bool IsOdd(int i)
{
    return ((i & 1) == 1);
}

I had no idea why that worked. I looked at the ms help:

Binary & operators are predefined for the integral types and bool. For integral types, & computes the bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.

Not particularly enlightening without doing some math, so I dug a little deeper. Reviewing binary counting I made a table on a 3x5 card, assuming a 4-bit number for simplicity:

Decimal	0	1	2	3	4	5	6	7	8
Binary	0000	0001	0010	0011	0100	0101	0110	0111	1000

Then I started thinking about the operation, but I initially processed it in my head as a binary addition not as the proper bitwise operation:

3 + 1
	0011
+	0001
=	0100

But that was clearly not right, since the result is 4, and for any positive integer greater than 0 the test would fail if addition was the underlying action. I looked up a couple more definitions for bitwise AND and finally understood this:

A bitwise AND operation (a & b) returns a one in each bit position for which the corresponding bits of both a and b are positive.

The result is a logical test for each bit:

3 & 1
	0	1	0	1
	&0	&0	&0	&1
=	0	0	0	1

Since the binary representation of decimal 1 is 0001, (front padded with as many zeros as necessary to match the bit size of the number), the only way the operation ([any integer] & 1) will return 1 is if the rightmost bit is one – all odd numbers.

The following table describes the bitwise operators in C# I find myself using now.

Operator	Usage	Description
Bitwise AND	a & b	Returns a one in each bit position for which the corresponding bits of both a and b are ones.
Bitwise OR	a | b	Returns a one in each bit position for which the corresponding bits of a OR b or both a AND b are ones.
Bitwise XOR	a ^ b	Returns a one in each bit position for which the corresponding bits of either a OR b but not both a AND b are ones.
Bitwise NOT	!a	Inverts each bit of a.

For more on how Binary works, see swansontec.com/binary.html.

As an aside - I had never really thought about whether zero is even or odd. Turns out zero is even, and here’s why wikipedia.org/wiki/Parity_of_zero.