Giả sử chúng ta có một số n. Chúng ta phải kiểm tra xem số đó có phải là lũy thừa của 2 hay không. Như vậy là n =16, thì kết quả sẽ là true, nếu n =12, nó sẽ là false.
Để giải quyết điều này, chúng ta sẽ sử dụng các phép toán logic. Nếu chúng ta thấy các số là lũy thừa của hai thì trong biểu diễn nhị phân của số đó sẽ là MSb là 1 và tất cả các bit khác là 0. Vì vậy, nếu chúng ta thực hiện [n AND (n - 1)], điều này sẽ trả về 0 nếu n là lũy thừa của 2. Nếu chúng ta thấy n =16 =10000 trong hệ nhị phân, (n - 1) =15 =01111 trong hệ nhị phân, thì 10000 VÀ 01111 =00000 =0
Ví dụ (C)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <stdio.h>
#include <math.h>
#define MAX 20
bool isPowerOfTwo(int n){
return(n>0 && !(n & (n-1)));
}
int main() {
printf("%s\n", isPowerOfTwo(16) ? "true" : "false");
printf("%s\n", isPowerOfTwo(12) ? "true" : "false");
printf("%s\n", isPowerOfTwo(1) ? "true" : "false");
printf("%s\n", isPowerOfTwo(32) ? "true" : "false");
printf("\n");
} Đầu vào
16 12 1 32
Đầu ra
true false true true