Testing Odd/Even Using Bitwise AND
Gary Ray Originally published at agilecoder.net on γ»3 min read
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 4bit 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.