Checking if a Number is Odd with a Bitwise Operator

Dec 20, 2022

system

linux

3kb

We can use the bitwise operator & to check if an integer is odd. Bitwise operators operate on element wise on bits. You can think of it has asking:

Are both bits 1?

Example

For example, take the bitwise and operation below:

The result has only the 5th position set as both have 1s set in that position.

What Does This Have to Do with Even and Odd Numbers?

We can use this operator to check if an integer is odd. We do this by AND any integer with 1. The idea is if the least significant bit (the right most bit) is 'on' (equal to 1) then we are just adding one to powers of two which is odd. Otherwise it's even.

Take 17. In binary it is 10001. If we AND this with one

10001 &
00001
-----
00001

We get a 1, meaning it is odd.

Contrast that with 12. We get 0, which means the number is even.

1100 &
0001
----
0000

Next time you want to check even and odd numbers, this may be a quicker way then using n % 2 == 0. Or better yet just run the code below and see for yourself.

speed_test.py

import numpy as np
import random
import time
 
def even_bit(n):
    if (n & 1) == 1:
        return "Odd"
 
    else:
        return "Even"
 
def even_mod(n):
    if (n % 2) == 0:
        return "Even"
 
    else:
        return "Odd"
 
def test_even_bit():
    higher = (2**31) / 2
    lower = -higher
    for _ in range(100):
        time_start = time.time()
     
        arr = np.random.randint(
            lower, 
            higher, 
            size=random.randint(0, 10**3), 
            dtype=np.int32
        )
 
        for num in arr:
            even_bit(num)
 
    print(f'100 iterations testing even with bits {time.time() - time_start}')
 
def test_even_mod():
    time_start = time.time()
    higher = (2**31) / 2
    lower = -higher
    for _ in range(100):
        arr = np.random.randint(
            lower, 
            higher, 
            size=random.randint(0, 10**3), 
            dtype=np.int32
        )
 
        for num in arr:
            even_mod(num)
        
    print(f'100 iterations testing even with mod {time.time() - time_start}')
 
def main():
    test_even_bit()
    test_even_mod()
 
if __name__ == "__main__":
    main()

Results

On one of the runs on my Macbook Pro M1:

100 iterations testing even with bits: $0.0006432533264160156s$
100 iterations testing even with mod: $0.0687568187713623s$

Pretty nifty I think.

Contact

If you have any comments or thoughts you can reach me at any of the places below.

email ↗github ↗x ↗linkedin ↗