0m3lrq
Last Updated: February 25, 2016
·
1.301K
· dmichaelavila
Photo

Determine Parity without Modulus

A common technique for determining the parity of a number (is it even or odd?) is to divide the number by 2 and check to see if anything is left over. This makes sense of course. Typically the modulus operator is used (e.g. my_value % 2 == 0). However, you can achieve the same goal, with the same number of characters, without incurring the costs associated with modulus. Here is how:

my_value & 1 == 0

It turns out that the least-significant bit (LSB) of any given number defines the parity of that number. Let's look at the bits associated with a few numbers (1, 2, 3, 4, and 5)

1 = 001
2 = 010
3 = 011
4 = 100
5 = 101

If you look at the LSB (or right-most bit) for each number you'll see that all the odd numbers end in 1 and all of the even numbers end with 0. Bitwise &'ing that one bit will result in either a 0 (if the number is even) or a 1 (if the number is odd). If this is confusing you probably don't understand bitwise &. Google it. Any better language neutral options out there?

Say Thanks
Respond

2 Responses
Add your response

10853
Photo

After having spent quite a bit of time doing benchmarks in a bunch of different languages I'm here to report that there is no significant performance improvement in a lot of the common languages. I still like this approach!

over 1 year ago ·
11452
6c5051ff6ef5eff9f5567ac546a415f1

This is the same thing as num % 2 as binary is base 2, so the rightmost bit would be what's left over when divided by two. Perhaps compilers and interpreters take this into account when performing optimization on mod operations, giving little difference (performance wise) between the two.

over 1 year ago ·