Check if an integer number is power of 2

Chào các bạn, hôm nay mình tiếp tục viết bài về một số câu hỏi phỏng vấn mà mình gặp, cũng như là các câu hỏi thường gặp về Algorithm mà mình đọc được trên một số forums, blog,...

Bài toán ngày hôm nay là:

Kiểm tra xem một số nguyên có phải có dạng 2^n hay không?

Thông thường, các mà mọi người nghĩ đến đầu tiên là: 2^n = 2*2*2*2*2*...*2 (n lần) Vậy nên tiếp theo bạn sẽ nghĩ là cứ lặp, mỗi lần lặp cứ nhân với 2, đến khi nào lớn hơn hoặc bằng n thì thôi, nếu lớn hơn thì return true; nếu bằng thì return false;

Cài đặt sẽ như sau:

def checkIsPower(n):
	if n <= 0:
		return False
	a = 1
	while a < n:
		a *= 2
	if a == n:
		return True
	return False

Tất nhiên, câu trả lời sẽ là đúng, chả có gì sai cả, chả có gì để nói. Nhưng đây chỉ với trình độ bình thường cũng nghĩ ra, chẳng có gì khác cả, đúng không?

Thế còn gì cool hơn không?

Xin thưa, có.

Để ý ta thấy: Các số nguyên dạng 2^n được biểu diễn dưới dạng số nhị phân sẽ có dạng: là sẽ có duy nhất giá trị 1 tại ví trí n khi được biểu diễn ở dạng nhị phân. Ví dụ: 4 = 100 (vị trí thứ 2, bắt đầu từ phải qua trái, tính từ 0), 16 = 10000 (vị trí thứ 4) Còn số 2^n-1 thì sao? Nó có 1 số 0 ở đúng cái vị trí trên và còn lại toàn là 1. Đúng không? Tóm lại: 2^n có dạng 1000...0, còn 2^n-1 có dạng 0111...1 Nên ta có (2^n)&(2^n-1) = 0

Cool !

Cài đặt:

def checkIsPower(n):
	return n&(n-1) == 0 and n>0

Tuyệt vời !

Reference:

http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/