Viết chương trình kiểm tra một số có phải lũy thừa của 2 không bằng Python

Đề bài: Cho một số nguyên dương, hãy viết một hàm để xác định xem nó có phải là lũy thừa của 2 hay không.

Ví dụ:

Input : n = 4
Output : Yes
22 = 4

Input : n = 7
Output : No

Input : n = 32
Output : Yes
25 = 32

Trong bài viết này, Quản Trị Mạng sẽ hướng dẫn bạn cách viết chương trình kiểm tra xem một số có phải là lũy thừa của 2 hay không bằng Python.

Cách 1:

Phương thức đơn giản nhất cho vấn đề này là chỉ cần lấy logarit (log) của số đó trên cơ số 2 và nếu kết quả trả về một số nguyên thì số đó là lũy thừa của 2.

Code cụ thể như sau:

# Python3 Program to find
# whether a no is
# power of two
import math
# Function to check
# Log base 2
def Log2(x):
    return (math.log10(x) /
            math.log10(2));
# Function to check
# if x is power of 2
def isPowerOfTwo(n):
    return (math.ceil(Log2(n)) == math.floor(Log2(n)));
# Driver Code
if(isPowerOfTwo(31)):
    print("Yes");
else:
    print("No");
if(isPowerOfTwo(64)):
    print("Yes");
else:
    print("No");
# This code is contributed
# by mits

Cách 2:

Một giải pháp khác là liên tiếp chia số nhập vào cho 2, tức là thực hiện n = n/2 lặp đi lặp lại. Trong bất kỳ phép lặp nào, nếu n%2 khác 0 và n không phải là 1 thì n không phải là lũy thừa của 2. Nếu n trở thành 1 thì đó là lũy thừa của 2.

Code chi tiết như sau:

# Python program to check if given
# number is power of 2 or not
# Function to check if x is power of 2
def isPowerOfTwo(n):
    if (n == 0):
        return False
    while (n != 1):
            if (n % 2 != 0):
                return False
            n = n // 2
    return True
# Driver code
if(isPowerOfTwo(31)):
    print('Yes')
else:
    print('No')
if(isPowerOfTwo(64)):
    print('Yes')
else:
    print('No')
# This code is contributed by Danish Raza

Cách 3:

Tất cả các số lũy thừa của 2 chỉ có một kiểu thiết lập bit duy nhất. Do vậy, hãy đếm số lượng của bit 1 trong biểu diễn dạng nhị phân của số được nhập vào. Nếu chỉ có 1 số 1 thì số đó là lũy thừa của 2.

Code đếm số lượng của bit 1 trong biểu diễn nhị phân của một số:

# Python3 program to Count set
# bits in an integer
# Function to get no of set bits in binary
# representation of positive integer n */
def  countSetBits(n):
    count = 0
    while (n):
        count += n & 1
        n >>= 1
    return count
# Program to test function countSetBits */
i = 9
print(countSetBits(i))
# This code is contributed by
# Smitha Dinesh Semwal

Hoặc:

# Python3 implementation of recursive
# approach to find the number of set
# bits in binary representation of
# positive integer n
def countSetBits( n):
    # base case
    if (n == 0):
        return 0
    else:
        # if last bit set add 1 else
        # add 0
        return (n & 1) + countSetBits(n >> 1)
# Get value from user
n = 9
# Function calling
print( countSetBits(n))    
# This code is contributed by sunnysingh

Cách 4:

Nếu chúng ta trừ một số lũy thừa của 2 cho 1 thì tất cả các bit 0 ở đằng sau bit 1 duy nhất sẽ chuyển thành bit 1 còn bit 1 duy nhất đó sẽ chuyển thành bit 0.

Ví dụ: Cho 4 (biểu diễn dạng nhị phân là 100) và 16 (10000) sau khi trừ đi 1 ta được kết quả sau:

• 3 biểu diễn nhị phân là 011
• 15 biểu diễn nhị phân là 01111

Do đó, nếu một số n là lũy thừa của 2 thì toán tử thao tác bit AND (&) của n và n-1 sẽ bằng 0. Chúng ta có thể xác định n có phải là lũy thừa của 2 hay không dựa trên giá trị của n&(n-1). Biểu thức n&(n-1) sẽ không hoạt động khi n = 0. Để xử lý trường hợp này, biểu thức của chúng sẽ phải thay bằng biểu thức n&(!n&(n-1)).

Dưới đây là code chi tiết cho phương pháp này:

# Python program to check if given
# number is power of 2 or not
# Function to check if x is power of 2
def isPowerOfTwo (x):
    # First x in the below expression
    # is for the case when x is 0
    return (x and (not(x & (x - 1))) )
# Driver code
if(isPowerOfTwo(31)):
    print('Yes')
else:
    print('No')
if(isPowerOfTwo(64)):
    print('Yes')
else:
    print('No')
# This code is contributed by Danish Raza   

Hy vọng rằng bài viết này sẽ có ích với bạn!