Em có hàm kiểm tra 1 số có phải là lũy thừa bậc n với cơ số là 2 hay không:
def is_Power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
print(is_Power_of_two(4))
print(is_Power_of_two(36))
print(is_Power_of_two(16))
Trong đoạn code e chưa hiểu ý nghĩa của dòng lệnh (n & (n - 1)) == 0
Nhờ các anh chị giúp gải thích e với ạ .
Nói kiểu này hơi xoắn não. Hàm này là hàm kiểm tra một số xem căn bậc n của nó có phải là 2 hay không.
Với a là một số nguyên dương và căn bậc n của nó là 2 thì a & (a - 1) bằng 0.
Vì sao lại thế? Cái này liên quan tới hai số 1 và 0.
Hãy quay trở lại cách mà các con số ở dạng nhị phân.
x | 4 3 2 1 0
Và đương nhiên còn tăng lên 5 6 7 8... nữa. Với số 0. Thì sẽ là
x | 4 3 2 1 0 # với x là số mũ của 2
----------------------
0 | 0
1 | 1 # 1 ở chỗ 0, nên sẽ là 2^0 = 1
2 | 1 0 # 1 ở chỗ 1, nên sẽ là 2^1 = 1
3 | 1 1 # 1 ở chỗ 1 và 0 nên sẽ là 2^0 + 2^1 = 3
4 | 1 0 0 # 1 ở chỗ 2 nên sẽ là 2^2 = 4
Đó là cách mà các số binary được tạo nên.
Dựa vào cái trên, ta thấy được, 4 bên binary là 100. Vậy còn số 4 - 1 là gì? Đó chính là 011.
Và nó cứ thế, nếu 2^x = n. Thì n bên binary có dạng 100000... bắt đầu với số 1 và toàn bộ phía sau là 0. Còn n - 1 thì sẽ có dạng 011111... bắt đầu với số 0 và toàn bộ phía sau là số 1.
Hãy tạm gác lại đó, bạn nên biết về bitwise này. Nó là bitwise and và thao tác với binary. Hãy giả sử ta có 2 số dạng binary là 10101 và 01101 đi, nếu ta dùng & thì sẽ là
1 0 1 0 1
0 1 1 0 1 # 0 là False, 1 là True, chắc bạn biết với and thì 2 cái cùng True mới ra True đúng chứ?
------------------
0 0 1 0 1 # đây chính là kếu quả của 21 & 13 = 5
Quay trở lại vấn đề trên, ta sẽ có
0 1 1 1 ...
1 0 0 0 ...
--------------------
0 0 0 0 ... # luôn là một dãy số 0. Và đương nhiên, kết quả của nó là 0.
Hope it helps.
Híc 
, xin lỗi anh, em viết lộn, ý em là kiểm tra 1 số có phải lũy thừa bậc n với cơ số 2 hay không.
Cám ơn anh nhiều ạ
Dễ thấy rằng 10000… - 1 = 01111… Mà 1 & 0 = 0 nên các lũy thừa của 2 được nhận đúng (0).
Ngược lại, nếu số có hai bit 1 trở lên thì những bit cao hơn bit 1 có giá trị thấp nhất sẽ không đổi, vì vậy AND lại không thể bằng 0 do còn ít nhất một bit 1.
Phiền các anh giúp e thêm đoạn dưới đây nữa ạ:
def is_Power_of_four(n):
while n and not (n & 0b11):
n >>= 2
return (n == 1)
print(is_Power_of_four(4))
print(is_Power_of_four(16))
print(is_Power_of_four(255))
Đoạn Code cũng tương tự như Code bên trên nhưng với cơ số là 4 ạ (kiểm tra 1 số có phải lũy thừa bậc n với cơ số 4 hay không.)
em không hiểu cái 0b11 và >>= 2 nghĩa là gì ạ ?
Cám ơn mọi người !
Số nhị phân 11 = số 3 ở hệ thập phân.
a >>= 2 <=> a //= 4
Cám ơn anh nhiều ạ. Mà sao lại phải thêm 0b ở phía trước vậy anh, em thử bỏ nó đi thì không thấy kq có gì khác biệt cả.
Số 11 với số 3 (0b11) khác nhau xa lắm 
not(n & 0b11) = true, hay n & 0b11 = false (0), vậy hai bit cuối phải 0 hết vòng lặp mới chạy. Nếu số bit có nghĩa là chẵn thì cuối cùng n = 0b10, ngược lại n = 0b01. Mà 4^n thì có 2n bit 0 phía sau số 1. Nếu n = 0b11 thì loại, và n không thể bằng 0b00, vì số 0 bị loại.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?