Well, sometimes I guess 🙂 Today a friend asked me the difference between a modulo operation and a bitwise AND to figure out if a number is Odd or Even.
First things first, the modulo operation requires a division, which I’m sure you understand is slower than just comparing bits. Now for the real fun. Check out this image:
So if we were to represent the number 10, we would end up with something like this: 1010 (which is basically the 8’s bit plus the 2’s bit)
Now for an odd number like 7: 111 (which means we have the 1’s bit plus the 2’s bit plus the 4’s bit, and we get 7)
So if you keep doing this with a different set of numbers, and also just by looking at the image, you can easily see that to get any odd number you need the 1’s bit turned on (=1). This is great, easy and really fast to check.
You compare a 1 bit to the last bit of whatever number you need and magic happens! Hopefully this was clear enough, I struggled a bit (no pun intended) to understand it the first time, but when you get it, it makes perfect sense.
As usual, code follows to show the theory.
""" Check if lenght of a string is Odd or Even using two different methods """ data = '1234567' sizeData = len(data) print 'Len(data): n', sizeData bitsSizeData = bin(sizeData) bitsOne = bin(1) print 'Bits for sizeData: n', bitsSizeData print 'Bits for 1: n', bitsOne bitResult = sizeData & 1 print 'Bit result: n', bitResult def isOddorEven(number): """ Uses division to check if number is Odd or Even. We do a modulo operation, if the result is 0 number is Even """ if number % 2 != 0: print 'Odd' else: print 'Even' def isOddorEvenBitwise(number): """ Uses Bitwise AND to check if number is Odd or Even. We compare the last bit number to one bit. If the last bit is set we have an Odd number. 1 AND 1 returns 1 else returns 0 This method is faster, especially for large numbers, since it doesn't need to do divisions. """ if number & 1: print 'Bit Odd' else: print 'Bit Even' isOddorEven(sizeData) isOddorEvenBitwise(sizeData)
One Response
Rob Galanakis
If I saw this in a Python codebase, I’d kick the person responsible in the nuts.
– % 2 is a generally understood way to check if something is odd or even. & 1 is not.
– There is *no* performance difference between the modulo and AND. Try it.
– Calling a function is several times more expensive than the operation itself. So if your goal is speed, and you want to hide the AND behind a function to make it read better, you’ve shot yourself in the foot.