การตรวจสอบเลขยกกำลังสองในภาษา C

สมมติว่าเรามีตัวเลข n เราต้องการตรวจสอบว่าเป็นเลขยกกำลังสองหรือไม่ เช่น n = 16 ผลลัพธ์คือ true แต่ n = 12 ผลลัพธ์คือ false

เราจะใช้การดำเนินการตรรกะ (Logical Operations) ในการแก้ปัญหา หากสังเกตตัวเลขที่เป็นกำลังของสอง ในรูปแบบไบนารี จะมีบิตที่สำคัญที่สุด (MSB) เป็น 1 และบิตอื่นๆ เป็น 0 ทั้งหมด ดังนั้น หากเราทำ [n AND (n – 1)] จะได้ 0 หาก n เป็นกำลังของสอง

ตัวอย่าง: n = 16 = 10000 (ไบนารี), (n – 1) = 15 = 01111 (ไบนารี), 10000 AND 01111 = 00000 = 0

ตัวอย่างโค้ด (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");
    printf("\n");
    return 0;
}

อินพุต

16 12 1 32

เอาต์พุต

true false true true