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



cialis generika kamagra australia cialis preise cialis kaufen cialis bestellen levitra generika viagra online kaufen kamagra bestellen cialis generika kamagra oral jelly kamagra 100mg prix cialis cialis generique kamagra gel viagra prix viagra pour homme acheter cialis kamagra prix viagra pas cher cialis 20mg levitra 20
Levitra Generika kaufen Kaufen Levitra Generika Online Cialis ohne Rezept kaufen Viagra online Viagra Generika kaufen Cialis Soft Tabs kaufen Sildenafil kaufen Apcalis Oral Jelly kaufen Viagra Soft Tabs bestellen Cialis Original kaufen Viagra bestellen Viagra bestellen Propecia Generika kaufen Viagra und seine Analoga Original Testpakete Levitra und Kamagra Erfahrungen Viagra Soft Tabs Kamagra kaufen
kamagra kopen in de winkel viagra werking cialis kopen in nederland cialis bijwerkingen kamagra bijsluiter levitra bijwerkingen viagra kopen apotheek cialis erfaring cialis i norge viagra effekt hva er kamagra viagra nettbutikk levitra eller cialis kamagra gel comprar cialis efeitos secundarios viagra farmacia cialis bula viagra infarmed levitra comprimidos cialis vs viagra cialis flashback kamagra tjejer kamagra effekt levitra fass kamagra oral jelly opiniones levitra generico precio cialis venta kamagra sobres cialis efectos secundarios