LeetCode 342. 4 的冪：位運算特徵判斷

LeetCode 342. 4 的冪

題目描述

判斷有符號 32 位整數 num 是否為 4 的冪次方（即 4^k, k ≥ 0）。

數學特徵

1. 2 的冪次方：二進制中有且僅有**一個 1**。判斷：num > 0 && (num & (num-1)) == 0。
2. 1 所在奇數位：4 的冪次方在二進制中，唯一的 1 必出現在**奇數位**（從 0 開始計數：第 0, 2, 4... 位）。即 num & 0x55555555 != 0（0x55555555 = 01010101...0101，奇數位為 1）。

代碼實現

bool isPowerOfFour(int num) {
    if (num <= 0) return false;
    if (num & (num - 1)) return false;       // 非 2 的冪
    if (num & 0x55555555) return true;       // 1 在奇數位
    return false;
}

替代方案

• 模 3 判斷：4^k % 3 = 1^k % 3 = 1。2 的冪中，僅 4 的冪滿足 num % 3 == 1。
  代碼：return num > 0 && (num & (num-1)) == 0 && num % 3 == 1;
• 查表法：32 位整數中 4 的冪僅 16 個（4^0 ~ 4^15），預存集合查找。

複雜度分析

• 時間複雜度：O(1)，位運算常數時間。
• 空間複雜度：O(1)。

總結

判斷 4 的冪結合了「2 的冪特徵」與「1 位置奇偶性」，展示了位運算在數學屬性判斷中的強大表達力。掌握 0x55555555、0xAAAAAAAA 等掩碼模式，可解決「2 的冪、4 的冪、奇偶位檢測」等系列問題。