6 Python Examples using bit manipulation for beginners

Numbers are represented using bits internally in computers, each bit can contain a boolean value 0 or 1 i.e., whether the bit is set or not. Bit manipulation is a concept where the individual bits within a given number are modified and/or looked at. There are quite a few cases where bit manipulation provides effective coding while consuming less memory. While bit manipulation is very popular in languages like C/C++, the article highlights some usage of bit manipulation using beginner-friendly examples.

Disclaimer: The examples provided in the article are run on Python version 3.12, other versions of Python may not run the same code as expected, under such cases please refer to the official Python documentation for fixing the issues.

Finding if a given number is even
The well-known one-liner for finding, whether a given number is even (return n % 2 == 0), can be further optimized by using bitwise operators. When a number is divided by 2, it yields a remainder or either 0 or 1; both of these can be represented using a single bit. Thus, by only looking at the last bit of the given number, even or odd property can be determined. Python provides the '&' operator to perform bitwise AND on two integers. Doing a bitwise AND with one yields the last bit's value of a given integer, the value of the last bit determines whether the given number is even.

def is_even(num):
    return num & 1 == 0


def is_odd(num):
    return num & 1 != 0


def run_tests():
    odds = [9, 11, 39, 91, 10201, 321, 75, 63, 201]
    evens = [56, 654, 98, 872, 482, 8976, 5423324]

    for num in odds:
        assert is_odd(num)
        assert not is_even(num)

    for num in evens:
        assert is_even(num)
        assert not is_odd(num)


run_tests()

Multiplication, Division, and Modulo by powers of two
Bitwise operators shine when it comes to operating with powers of 2. Some of the basic arithmetic with powers of 2 can be performed using bitwise operators. Examples include multiplication, division (integer division to be precise), and modulo. When a given number is shifted to the right by one position, the number halves, while shifting one position to the left doubles the number.  The same logic can be extended to other powers of 2, which can be generalized by computing the number of shifts required (N shifts, where N is the power of 2). For example, to divide a number by 4, the bits have to be shifted to the right by two positions (22 = 4). The left and right shift operations can be done using '<<' and '>>' operators in Python. Coming to the modulo by powers of two, taking a bitwise AND of 2n - 1 will yield the modulo. The example provides the functions that operate on two, but the same can be extended to other powers of 2.

def mul_by2(num):
    return num << 1


def div_by2(num):
    return num >> 1


def mod_by2(num):
    return num & 1


def run_tests():
    num_array = [1, 2, 4, 8, 16, 18, 19, 52, 99, 122]
    for num in num_array:
        assert mul_by2(num) == 2 * num
        assert div_by2(num) == num // 2
        assert mod_by2(num) == num % 2


run_tests()

Finding if a given number is power of 2
A one line Python code can find out whether an input number is power of two. When a bitwise AND is performed on the input number N and N-1, the result will be 0 if the input number is a power of two. To note, any power of two will have only one bit set in the number.

def is_power_of2(num):
    return num & (num - 1) == 0


def run_tests():
    pow2 = [1, 2, 4, 8, 16, 32, 64, 128, 1024, 8192, 1048576]
    for num in pow2:
        assert is_power_of2(num)

    not_pow2 = [19, 43, 462, 1342, 632532, 23124, 1235, 636]
    for num in not_pow2:
        assert not is_power_of2(num)


run_tests()

Manipulating individual bits
With bitwise operators, individual bits can be got, set, cleared or toggled. The core operation involves shifting 1 to the desired position where the bit to be manipulated is, followed by a specific bit-wise operation will modify the bit as needed. In the examples below, the position is assumed to be from the Least Significant Bit (LSB). The below diagram depicts the operations involved in bit manipulation for each case.

def set_bit(num, pos):
    return num | (1 << pos)


def clear_bit(num, pos):
    return num & ~(1 << pos)


def toggle_bit(num, pos):
    return num ^ (1 << pos)


def is_set(num, pos):
    return num & (1 << pos) > 0


def run_tests():
    assert set_bit(6, 0) == 7
    assert clear_bit(6, 1) == 4
    assert toggle_bit(6, 0) == 7
    assert toggle_bit(6, 3) == 14
    assert not is_set(6, 0)
    assert is_set(6, 1)
    assert is_set(6, 2)


run_tests()

Count the number of bits set in a given number
The easiest approach to count the number of bits is to shift the number to the right by one position, and performing a bitwise AND with 0x1, till the number becomes 0. But an efficient algorithm is described in K & R C book where, by doing a bitwise AND of n and n - 1, the last set bit is cleared during every iteration. When the number drops down to zero, the number of iterations indicates the number of bits set on the number.

def num_1s(num):
    count = 0
    while num > 0:
        num = num & (num - 1)
        count += 1
    return count


def run_tests():
    set_1 = [1, 2, 4, 8, 16, 32, 64, 128, 256, 4096]
    for num in set_1:
        assert num_1s(num) == 1

    set_2 = [3, 5, 6, 9, 12, 17, 33, 65, 129, 4097]
    for num in set_2:
        assert num_1s(num) == 2

    set_3 = [7, 19, 35, 67, 131, 4099]
    for num in set_3:
        assert num_1s(num) == 3


run_tests()

Swap two numbers using bitwise operations
The popular one-liner in Python a, b = b, a does the swapping of two numbers. Interestingly, two numbers can also be swapped using bitwise operators. By using the two properties a XOR a = 0 and a XOR 0 = a by doing a set of XOR operations, two numbers can be swapped. In the example code below, the following operations happen,

• First, a xor b is computed
• Then, a xor b xor b will give a, which is assigned to b (one number swapped)
• Then, a xor b xor a will give b, which is assigned to a (both numbers swapped)

def swap_using_bits(num1, num2):
    num1 = num1 ^ num2
    num2 = num1 ^ num2
    num1 = num1 ^ num2

    return num1, num2


def run_tests():
    assert swap_using_bits(5, 9) == (9, 5)
    assert swap_using_bits(19032, 9131) == (9131, 19032)
    assert swap_using_bits(421, 42421) == (42421, 421)


run_tests()

Thanks for reading the article, please leave suggestion or comments down below.