# Testing Odd/Even Using Bitwise AND

## A brief foray into elementary binary operations.

Posted by AgileCoder on July 31, 2012

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 &amp; 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.