Mastering Bitwise Operations: 4 Essential Algorithms

Discover the power of bitwise operations in this comprehensive guide. Explore four essential algorithms that leverage bitwise operations to solve complex problems efficiently. Enhance your understanding of data structure and algorithms with this insightful post. In this blog post, we will examine numerous bitwise algorithms and how they are used in software engineering and computer science. We will go over the key ideas and methods that each software engineer should be familiar with, from bit manipulation techniques to optimization tactics. Prepare yourself to enter the realm of bits and bytes! You can run this post in Google Colab using this link:

Bitwise operations in Python

Bitwise operations are a group of elementary operations that deal with a binary number’s constituent bits. These operations include left shift, right shift, bitwise AND, OR, XOR, and NOT. These operations are used to efficiently manipulate bits at the bit level and can be applied to tasks like determining whether a particular bit is set or clearing a particular bit. Bitwise operations are particularly useful in low-level languages such as C and C++, but are also available in high-level languages such as Python. Here is the operator of bit manipulation in Python:

• Bitwise AND:

10 (Binary: 1010) & 4 (Binary: 0100) = 0 (Binary: 0000)

• Bitwise OR:

10 (Binary: 1010) | 4 (Binary: 0100) = 14 (Binary: 1110)

• Bitwise NOT:

~10 (Binary: 1010) = -(1010 + 1) = 11 (Binary: 1011)

• Bitwise XOR:

10 (Binary: 1010) ^ 4 (Binary: 0100) = 14 (Binary: 1110)

• Bitwise right shift:

Shifts the bits of the number to the right and fills 0 on voids left( fills 1 in the case of a negative number) as a result. Similar effect as of dividing the number with some power of two.

10 (Binary: 00001010) >> 1 = 5 (Binary: 000001010)

-10 (Binary: 11110110) >> 1 = -5 (Binary: 11111011)

• Bitwise left shift:

Shifts the bits of the number to the left and fills 0 on voids right as a result. Similar effect as of multiplying the number with some power of two.

5 (Binary: 00000101) << 1 = 10 (Binary: 00001010)

5 (Binary: 00000101) << 2 = 20 (Binary: 00010100)

1. Find $n^{th}$ magic number

Question

A “magic number” is a number that has a specific mathematical property. A magic number is defined as a number that can be expressed as a power of 5 or the sum of unique powers of 5.

For example, the first few magic numbers are 5, 25, 30 (5 + 25), 125, 130 (125 + 5), and so on. The number 5 is a magic number because it is a power of 5 (5^1). The number 25 is also a magic number because it is a power of 5 (5^2). The number 30 is a magic number because it is the sum of unique powers of 5 (5^1 + 5^2). See the table for more detail.

Write a function to find the nth Magic number.

Code

def nth_magic_number(n: int) -> int:
    """
    Finds the nth magic number. A magic number is defined as a number
    which can be expressed as a power of 5 or sum of unique powers of 5.
    """
    pow_of_5 = 1
    magic_number = 0

    # Go through every bit of n
    while n:
        pow_of_5 *= 5

         # If last bit of n is set
        if n & 1:
            magic_number += pow_of_5

        # proceed to next bit
        n >>= 1
    return magic_number

Explanation

The function finds the magic number by utilizing bit manipulation and a mathematical property of magic numbers.

The function starts by setting two variables, pow and answer to 1. The variable pow is used to keep track of the current power of 5, and answer is used to store the final magic number.

The function then enters a while loop that runs as long as the value of n is greater than 0. Inside the while loop, pow is multiplied by 5 on each iteration. This is done to calculate the next power of 5.

If the last bit of n is set (i.e. if n & 1 evaluates to True), the current power of 5 stored in pow is added to the answer variable.

The last step of each iteration is to proceed to the next bit of n by using the bitwise right shift operator n >>= 1 (or n = n/2). This effectively divides n by 2 and discards the least significant bit.

When the while loop finishes, the final magic number is stored in the answer variable, and the function returns it.

The time complexity of this function is O(log(n)) because the while loop runs for log(n) times. This is because for each iteration, it is checking the next bit of n, which doubles the number of bits being checked. The space complexity is O(1) because the function only uses a constant amount of space, regardless of the input size.

Test

import unittest

class TestNthMagicNumber(unittest.TestCase):

    def test_nth_magic_number(self):
        self.assertEqual(nth_magic_number(1), 5)
        self.assertEqual(nth_magic_number(2), 25)
        self.assertEqual(nth_magic_number(3), 30)
        self.assertEqual(nth_magic_number(4), 125)
        self.assertEqual(nth_magic_number(5), 130)

res = unittest.main(argv=[''], verbosity=3, exit=False)
assert len(res.result.failures) == 0

test_nth_magic_number (__main__.TestNthMagicNumber) ... ok

----------------------------------------------------------------------
Ran 1 test in 0.002s

OK

2. Swap all odd and even bits

Given an unsigned integer N. The task is to swap all odd bits with adjacent even bits.

Examples:

• Input: 23
• Output: 43
  • Explanation: 23 (00010111) should be converted to 43 (00101011)

Code

def swap_bits(x: int) -> int:
    """
    Swaps the even and odd bits of a given number.
    """
    # Get all even bits of x
    even_bits = x & 0xAAAAAAAA
    # Get all odd bits of x
    odd_bits = x & 0x55555555
    # Right shift even bits
    even_bits >>= 1
    # Left shift odd bits
    odd_bits <<= 1
    # Combine even and odd bits
    return (even_bits | odd_bits)

Explanation

The above code is a Python function that takes an integer x as input and returns an integer that is obtained by swapping the even and odd bits of the input number x.

The function starts by using bitwise AND operator & to extract the even bits and the odd bits of the input number x. It creates two 32-bit numbers, 0xAAAAAAAA and 0x55555555, to represent all even bits set as 1 and all odd bits set as 0 and vice-versa.

It then uses the bitwise AND operator & with the input number x to extract the even and odd bits respectively.

Next, the function uses the right shift operator >>= to shift the even bits to the right by one position, effectively swapping the even bits with their next odd bit. Similarly, it uses the left shift operator <<= to shift the odd bits to the left by one position, effectively swapping the odd bits with their next even bit.

Finally, the function uses the bitwise OR operator | to combine the even bits and the odd bits and returns the resulting integer.

This function can be used to swap the even and odd bits of any 32-bit integer, while keeping the time and space complexity of the function O(1)

Test

class TestSwapBits(unittest.TestCase):
    def test_swap_bits(self):
        self.assertEqual(swap_bits(23), 43)

res = unittest.main(argv=[''], verbosity=3, exit=False)
assert len(res.result.failures) == 0

test_nth_magic_number (__main__.TestNthMagicNumber) ... ok
test_swap_bits (__main__.TestSwapBits) ... ok

----------------------------------------------------------------------
Ran 2 tests in 0.004s

OK

even_bite: 23 = 00010111

23 & 0xAAAAAAAA: 00010111 & 10101010 = 00000010 ---> 2

even_bits >>= 1: = 00000001 ---> 1

odd_bits: 23 & 0x55555555: 00010111 & 01010101 = 00010101 ---> 21

odd_bits <<= 1: = 00101010 ---> 42

return: 00000001 | 00101010 = 00101011 ---> 43

3. Binary representation of a given number

Question

Binary representation of a given number is a way to represent a decimal number (base 10) in the binary system (base 2). In the binary system, only two digits are used: 0 and 1. Each digit in a binary number represents a power of 2, with the rightmost digit representing 2^0 (1) and each digit to the left representing the next power of 2.

For example, the decimal number 8 can be represented in binary as 1000. This is because 8 = 12^3. Similarly, the decimal number 11 can be represented in binary as 1011. This is because 11 = 12^3 + 02^2 + 12^1 + 1*2^0.

Write a function to return binary representation of a number

Code

def dec_to_bin(n: int) -> str:
    """
    Convert decimal number to binary representation.
    """
    result = []

    # Start from 31th bite by shifting one to
    i = 1 << 31
    while i > 0:

        # check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”
        # if  n & i >= 1 means 31th bit is ON (1) else 0th bit is OFF
        if n & i >= 1:
            result.append("1")
        else:
            result.append("0")

        # Go to 30th bit and keep while loop until i == 0
        i = i // 2
    return "".join(result)

Explanation

The above code defines a function dec_to_bin(n: int) -> str that converts a decimal number to its binary representation. The function takes a single argument n which is an integer, and returns a string containing the binary representation of the input number.

The function starts by initializing an empty list called result and a variable i as 1 << 31. The variable i is used to check each bit of the decimal number, starting from the leftmost (most significant) bit. The left shift operator << is used to shift the value of 1 to the 31th position (i = 10000000000000000000000000000000 in binary) so that it can be used to check the 31th bit of the decimal number.

The function then enters a while loop which will continue until i becomes 0. Inside the while loop, the function uses the bitwise operator & to check whether the 31th bit of the decimal number is ON or OFF. The expression n & i >= 1 checks whether the result of the bitwise & operator is greater than or equal to 1, which means that the 31th bit is ON. If the condition is true, the function appends “1” to the result list. If the condition is false, the function appends “0” to the result list instead.

After that, the function divides i by 2 using i = i // 2 to move to the next bit (30th bit) and continues the loop until i becomes 0.

Finally, the function uses the join() method to join all the elements of the result list and return a string containing the binary representation of the input number.

The time complexity is O(log(n)), where n is the decimal number being converted. This is because the while loop iterates log2(n) times.

In each iteration, the function performs a bitwise operation and a comparison operation, both of which have a constant time complexity of O(1). Therefore, the overall time complexity is O(log(n)).

The space complexity is O(log(n)) as well, as it creates a list of size log2(n) to store the binary digits of the input number. The space complexity of creating the list is O(log(n)).

Test

class TestDecToBin(unittest.TestCase):
    def test_decToBin(self):
        self.assertEqual(dec_to_bin(5), "00000000000000000000000000000101")
        self.assertEqual(dec_to_bin(10), "00000000000000000000000000001010")
        self.assertEqual(dec_to_bin(100), "00000000000000000000000001100100")
        self.assertEqual(dec_to_bin(255), "00000000000000000000000011111111")
        self.assertEqual(dec_to_bin(0), "00000000000000000000000000000000")

    def test_decToBin_negative(self):
        self.assertEqual(dec_to_bin(-5), "11111111111111111111111111111011")
        self.assertEqual(dec_to_bin(-10), "11111111111111111111111111110110")

res = unittest.main(argv=[''], verbosity=3, exit=False)
assert len(res.result.failures) == 0

test_decToBin (__main__.TestDecToBin) ... ok
test_decToBin_negative (__main__.TestDecToBin) ... ok
test_nth_magic_number (__main__.TestNthMagicNumber) ... ok
test_swap_bits (__main__.TestSwapBits) ... ok

----------------------------------------------------------------------
Ran 4 tests in 0.006s

OK

4. Count number of bits to be flipped to convert a to b

Question

Given two numbers A and B. Write a program to count the number of bits needed to be flipped to convert A to B.

• Input: a = 10 b = 20

• output: 4

  • Binary representation of a is 00001010
  • Binary representation of b is 00010100
  • We need to flip “0101” bits in a to make it b so we need to change 4 bits

def count_bits(a: int, b: int) -> int:
    """
    Count the number of bits that are different between two integers.

    :param a: an integer
    :param b: another integer
    :return: the number of bits that differ between the two integers
    """
    xor_result = a ^ b
    count = 0
    while xor_result:
        count += xor_result & 1
        xor_result >>= 1
    return count

Explanation

The function starts by calculating the bitwise XOR of a and b using the ^ operator. This operation compares each bit of the two numbers and if the bits are different, the corresponding bit in the result is set to 1, otherwise it is set to 0. For example, if a is 5 (binary: 101) and b is 3 (binary: 011), the XOR result will be 6 (binary: 110).

The function then initializes a variable called count to 0. This variable will be used to keep track of the number of bits that differ between the two integers.

Next, the function enters a while loop which continues until the xor_result is nonzero. Inside the loop, the function increments the count variable by 1 if the least significant bit (LSB) of the xor_result is 1. This can be achieved by using xor_result & 1 to check the LSB. Then it will shift the xor_result to right by 1 bit to check the next bit.

The time complexity of the above code is O(n), where n is the number of bits that differ between the two integers. The while loop will continue until all the bits of the xor_result have been checked. If the two integers have k different bits, the loop will run k times, resulting in a time complexity of O(k). Since k <= n , the time complexity is O(n).

The space complexity of the above code is O(1). The function only uses a single variable called count to keep track of the number of bits that differ between the two integers. This variable takes a constant amount of space, regardless of the size of the input integers. Therefore, the space complexity is O(1).

class TestCountBits(unittest.TestCase):
    def test_CountBits(self):
        self.assertEqual(count_bits(5, 3), 2)
        self.assertEqual(count_bits(0, 0), 0)
        self.assertEqual(count_bits(255, 0), 8)
        self.assertEqual(count_bits(2**31-1, 2**31-1), 0)

res = unittest.main(argv=[''], verbosity=3, exit=False)
assert len(res.result.failures) == 0

test_CountBits (__main__.TestCountBits) ... ok
test_decToBin (__main__.TestDecToBin) ... ok
test_decToBin_negative (__main__.TestDecToBin) ... ok
test_nth_magic_number (__main__.TestNthMagicNumber) ... ok
test_swap_bits (__main__.TestSwapBits) ... ok

----------------------------------------------------------------------
Ran 5 tests in 0.008s

OK