Power of Two

Q: Làm thế nào để kiểm tra xem một số có phải là lũy thừa của hai không?

Trả về true khi n > 0 và n & (n-1) bằng 0. Lũy thừa của hai có đúng một bit 1, và n & (n-1) xóa bit đó. Nếu không dùng phép toán bit, hãy chia đôi n khi nó là số chẵn rồi kiểm tra xem kết quả cuối cùng có bằng 1 không.

Q: Độ phức tạp thời gian của Power of Two là gì?

Phép kiểm tra n & (n-1) chạy trong thời gian và không gian O(1) . Vòng lặp chia đôi chạy trong thời gian O(log n) , tối đa 31 bước với số nguyên 32 bit.

Q: 1 có phải là lũy thừa của 2 không? 0 thì sao?

1 là lũy thừa của 2, vì 2^0 = 1 . 0 thì không phải: không có số mũ nguyên nào cho kết quả bằng 0, và nó không có bit 1 nào cả. Các số âm cũng không bao giờ là lũy thừa của 2.

DễThao tác bit

+10

Bạn nhận được một số nguyên n. Trả về true nếu n là lũy thừa của hai, nghĩa là n = 2^k với một số nguyên k ≥ 0, và trả về false nếu không phải. Vậy nên 1, 2, 4 và 8 được tính, còn 0, 6 và mọi số âm thì không.

Hàm

isPowerOfTwo(n: integer) → boolean

ninteger: số nguyên (integer) cần kiểm tra, có thể bằng không hoặc âm
Trả vềboolean: đúng nếu n bằng 2^k với một k ≥ 0, ngược lại là sai

Ràng buộc

-2³¹ ≤ n ≤ 2³¹-1

Ví dụ

Đầu vào: n = 16
Đầu ra: true
Giải thích: 16 = 2 × 2 × 2 × 2 = 2^4. Trong hệ nhị phân, số này là 10000, gồm một bit 1.

Đầu vào: n = 24
Đầu ra: false
Giải thích: 24 = 8 × 3. Chia đôi ta được 12, 6 rồi đến 3, là số lẻ nhưng không phải 1. Trong hệ nhị phân, 24 là 11000, có hai bit 1.

Đầu vào: n = 1
Đầu ra: true
Giải thích: 1 = 2^0, vì vậy đây là một lũy thừa của 2. Dạng nhị phân 1 có đúng một bit 1.

Câu hỏi mở rộng

Với những mẹo thao tác bit tương tự, bạn có thể kiểm tra xem n có phải là lũy thừa của 4 mà không cần dùng vòng lặp không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Trong hệ nhị phân, lũy thừa của hai có dạng một bit 1 theo sau là các số 0, chẳng hạn 10000 là 16. Bạn có thể xác nhận dạng này bằng cách chia đôi n cho đến khi nó trở thành số lẻ, hoặc kiểm tra chỉ trong một bước với n & (n-1). Phép toán này xóa bit 1 thấp nhất và chỉ cho kết quả 0 khi đó là bit 1 duy nhất. Hãy kiểm tra số 0 và các số âm trước.

Chia cho 2 khi số đó là số chẵn

Ý tưởng

Chia 2^k cho 2 đúng k lần sẽ được 1, và mọi giá trị trên đường đi đều là số chẵn. Một số có thừa số lẻ lớn hơn 1 sẽ dừng chia đôi ở một số lẻ khác 1.

Trả về false nếu n ≤ 0 trước vòng lặp. Không có lũy thừa nào của 2 là số 0 hoặc số âm, còn 0 là số chẵn và khi chia đôi vẫn bằng 0, nên vòng lặp sẽ không bao giờ kết thúc. Mỗi bước chia đôi n, vì vậy đầu vào 32 bit cần tối đa 31 bước.

Thuật toán

Nếu n ≤ 0, trả về false.
Khi n là số chẵn, chia nó cho 2.
Trả về kết quả cho biết n hiện có bằng 1 hay không.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Xóa bit 1 thấp nhất bằng n & (n-1)

Ý tưởng

Trừ đi 1 sẽ đổi bit 1 thấp nhất thành 0 và mọi bit 0 bên dưới nó thành 1, đồng thời giữ nguyên các bit cao hơn. Lũy thừa của 2 không có bit cao hơn: 16 là 10000, 15 là 01111, và 16 & 15 bằng 0. Mọi số dương khác đều có một bit 1 cao hơn xuất hiện trong cả hai số, nên phép AND không bằng 0. Với 24, bạn nhận được 11000 & 10111, bằng 10000.

Trước tiên, hãy kiểm tra n > 0. 0 & -1 bằng 0, và trong phép tính 32 bit, -2^31 là một bit 1 đơn độc theo sau bởi 31 bit 0, nên chỉ phép AND thôi sẽ chấp nhận cả hai giá trị. Toàn bộ phép kiểm tra gồm một phép so sánh, một phép trừ và một phép AND.

Thuật toán

Nếu n ≤ 0, trả về false.
Tính n & (n-1), đây là n sau khi xóa bit 1 thấp nhất.
Trả về kết quả kiểm tra xem giá trị đó có bằng 0 hay không.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Lỗi thường gặp và trường hợp biên

Bỏ qua bước kiểm tra dấu. 0 vượt qua phép kiểm tra AND, và với số nguyên 32 bit, -2^31 cũng vậy vì nó chỉ có một bit 1. Cả hai đều phải trả về false.
Chạy vòng lặp chia đôi với 0. Số 0 là số chẵn và chia đôi vẫn bằng 0, nên vòng lặp không bao giờ kết thúc.
Bỏ dấu ngoặc đơn. == có độ ưu tiên cao hơn &, nên trong C, C++ và JavaScript, n & n - 1 == 0 có nghĩa là n & ((n - 1) == 0) và cho kết quả sai mà không báo lỗi. Hãy viết (n & (n - 1)) == 0.
Dùng logarit. Với độ chính xác kép, log(536870912) / log(2) cho kết quả 29.000000000000004, nên phép kiểm tra số nguyên cho rằng 2^29 là false.

Câu hỏi thường gặp3

Làm thế nào để kiểm tra xem một số có phải là lũy thừa của hai không?

Trả về true khi n > 0 và n & (n-1) bằng 0. Lũy thừa của hai có đúng một bit 1, và n & (n-1) xóa bit đó. Nếu không dùng phép toán bit, hãy chia đôi n khi nó là số chẵn rồi kiểm tra xem kết quả cuối cùng có bằng 1 không.

Độ phức tạp thời gian của Power of Two là gì?

Phép kiểm tra n & (n-1) chạy trong thời gian và không gian O(1). Vòng lặp chia đôi chạy trong thời gian O(log n), tối đa 31 bước với số nguyên 32 bit.

1 có phải là lũy thừa của 2 không? 0 thì sao?

1 là lũy thừa của 2, vì 2^0 = 1. 0 thì không phải: không có số mũ nguyên nào cho kết quả bằng 0, và nó không có bit 1 nào cả. Các số âm cũng không bao giờ là lũy thừa của 2.

def isPowerOfTwo(n):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 16

Đầu ra mong đợi

true