5 Best Ways to Check if N Is Divisible by a Power of 2 Without Using Arithmetic Operators in Python

Rate this post

πŸ’‘ Problem Formulation: Determining whether a given positive integer n is divisible by a power of 2 is a common technical problem, particularly in areas such as computer science and digital systems. The conventional approach would be using arithmetic operators like division or modulus. However, this article explores alternative methods without relying on them, focusing on bitwise operations and logical reasoning. An example of input could be n=4, and the desired output would indicate True, as 4 is divisible by 2^2.

Method 1: Bitwise AND Operation

This method takes advantage of the fact that powers of two in binary form consist of a single ‘1’ followed by zeros (e.g., 2 is 10 in binary, 4 is 100). Thus, a number n is divisible by a power of 2 if n & (n-1) equals zero. The function specification: is_divisible_by_power_of_2(n: int) -> bool.

Here’s an example:

def is_divisible_by_power_of_2(n):
    return n & (n-1) == 0

# Testing the function
print(is_divisible_by_power_of_2(4))  # Expect True
print(is_divisible_by_power_of_2(5))  # Expect False

Output:

True
False

The function defined checks if a number n is equal to 0 when a bitwise AND operation is performed between n and n-1. This is effective because only powers of 2 satisfy this condition. It’s a fast and straightforward method since bitwise operations are usually more efficient than arithmetic operations.

Method 2: Right Shift Operation

Using the bitwise right shift operator on a power of two will eventually result in the value 1, assuming an integer type without overflow. We test that n is greater than 0 and check repeatedly if the right shift result is 1. Function specification: is_power_of_2_shift(n: int) -> bool.

Here’s an example:

def is_power_of_2_shift(n):
    if n  1:
        n >>= 1
    return n == 1

# Testing the function
print(is_power_of_2_shift(8))  # Expect True
print(is_power_of_2_shift(10)) # Expect False

Output:

True
False

Here, we continuously shift the number to the right and terminate if the number becomes 1. This method mimics division by 2 without an arithmetic operator to check if the result is a power of two. However, unlike the previous method, it involves a loop which might be a tad slower for large numbers.

Method 3: Counting Trailing Zeros

Every power of two has exactly one non-zero bit in binary, with all other bits being zero. Leveraging Python’s built-in functions, the bin() function returns the binary string of a number, and the str.count() method can be used to count how many times a substring appears in the string. Function specification: is_power_of_2_trailing_zeros(n: int) -> bool.

Here’s an example:

def is_power_of_2_trailing_zeros(n):
    return bin(n).count('1') == 1

# Testing the function
print(is_power_of_2_trailing_zeros(16))  # Expect True
print(is_power_of_2_trailing_zeros(18))  # Expect False

Output:

True
False

The function capitalizes on the fact that a binary representation of a power of 2 has only one ‘1’. By counting the number of ‘1’s in the binary string of n, we can determine if n is a power of 2. This approach is concise but slightly less efficient due to the conversion to string and counting operation.

Method 4: Inverse Bitwise AND Operation

An ingenious way to check if n is divisible by a power of 2 is using the complement operator to invert the bits of n-1 and then perform a bitwise AND with n. If n is a power of 2, this operation will result in n. Function specification: is_divisible_by_inverse_and(n: int) -> bool.

Here’s an example:

def is_divisible_by_inverse_and(n):
    return n & (~n + 1) == n

# Testing the function
print(is_divisible_by_inverse_and(32))  # Expect True
print(is_divisible_by_inverse_and(34))  # Expect False

Output:

True
False

This function leverages the fact that the complement of n-1 is a number with all bits inverted up to the rightmost ‘1’ bit of n. For powers of 2, only one bit is set, so this method yields n when the input is a power of 2. It’s a smart, albeit slightly confusing method for those unfamiliar with bitwise operations.

Bonus One-Liner Method 5: Logical AND with Ones’ Complement

As a bonus, Python allows neat one-liners. Exploiting the same principle used in Method 4, we can compress the function into a single line by combining the bitwise AND and complement operators. Function specification: lambda n: n & (-n) == n.

Here’s an example:

is_divisible_by_power_of_2_oneliner = lambda n: n & (-n) == n

# Testing the function
print(is_divisible_by_power_of_2_oneliner(64))  # Expect True
print(is_divisible_by_power_of_2_oneliner(65))  # Expect False

Output:

True
False

The one-liner is essentially the same as Method 4 but written as a lambda function. This technique is highly concise and maintains the efficiency of the bitwise operation. It’s great for quick checks but may reduce readability for some developers.

Summary/Discussion

  • Method 1: Bitwise AND Operation. Efficient. May not be immediately intuitive for new programmers.
  • Method 2: Right Shift Operation. Iterative. Simple to understand but potentially slower for large numbers.
  • Method 3: Counting Trailing Zeros. Utilizes built-in Python functions. Less performant due to string operations.
  • Method 4: Inverse Bitwise AND Operation. Clever utilization of bitwise complement. Requires a deeper understanding of bitwise operations.
  • Bonus Method 5: Logical AND with Ones’ Complement. Compact and efficient. Lack of named function may hinder readability.