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, HS 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, 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)
0011
&0&0&0&1
=0001

Since the binary representation of decimal 1 is 0001, (front padded with as manyzeros 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.

OperatorUsageDescription
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 http://www.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 http://en.wikipedia.org/wiki/Parity_of_zero



viagra wirkung viagra wirkstoff viagra naturel viagra homme viagra pour homme viagra alkohol viagra dosering viagra precio viagra precio en farmacia viagra masculina viagra effetti collaterali viagra generico viagra generico prezzo