Kiểm tra số nguyên là lũy thừa của 2 trong C

Mô tả bài toán

Cho một số nguyên n. Kiểm tra xem n có phải là lũy thừa của 2 hay không. Ví dụ: n = 16 → true; n = 12 → false.

Ý tưởng giải thuật

Sử dụng phép toán logic bitwise. Các số là lũy thừa của 2 trong nhị phân có dạng: bit cao nhất (MSB) là 1, các bit còn lại đều là 0.

Ví dụ: 16 = 10000 (nhị phân). Nếu thực hiện n & (n - 1), kết quả sẽ là 0 nếu n là lũy thừa của 2.

n = 16 = 10000
n - 1 = 15 = 01111
10000 & 01111 = 00000 = 0

Ví dụ mã nguồn (C)

#include <stdio.h>
#include <stdbool.h>

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");
    return 0;
}

Đầu vào

16 12 1 32

Đầu ra

true false true true