C/C++ 面試經典十題詳解：從位運算到記憶體模型

前言

整理十道高頻面試題，涵蓋陣列、位運算、字串比較、指標算術、作業系統、網路協定、型別轉換、絕對位址操作，附完整解析與程式碼。

1. O(N) 找出重複數字

陣列 a[N] 含 1~N-1 共 N-1 個數，其中一個重複一次。利用輔助陣列標記：

int find_duplicate(int a[], int n)
{
    int *seen = calloc(n, sizeof(int));
    for (int i = 0; i < n; ++i) {
        if (seen[a[i]]) { free(seen); return a[i]; }
        seen[a[i]] = 1;
    }
    free(seen);
    return -1; /* 不應到達 */
}

時間 O(N)、空間 O(N)。進階：若不可用額外空間，可用「快慢指標」環偵測（Floyd 判圈）O(1) 空間。

2. 一行判斷 2 的冪次

bool is_pow2(int x) { return x > 0 && (x & (x - 1)) == 0; }

原理：2 的冪次二進位只有單一 1（如 1000），減 1 變全 1（0111），按位與為 0。

3. 字串指標 vs 陣列比較

char str1[] = "abc", str2[] = "abc";
const char *p1 = "abc", *p2 = "abc";
printf("%d %d %d %d\n", str1==str2, p1==p2, str1==p1, p1==str2);

輸出：0 1 0 0（視編譯器最佳化而定）。
解析：陣列各自在堆疊有獨立記憶體，指標指向唯讀常數區同一字面常數（編譯器合併）。

4. 指標算術陷阱

int a[5] = {1,2,3,4,5};
int *ptr = (int*)(&a + 1);
printf("%d,%d\n", *(a+1), *(ptr-1));  /* 輸出 2,5 */

&a 型別為 int (*)[5]，+1 跳過整個陣列（20 bytes），ptr 指向 a[5]（越界）。ptr-1 退回 sizeof(int) 落在 a[4] = 5。

5. 死鎖四必要條件

1. 互斥
2. 請求與保持
3. 不可搶佔
4. 循環等待

6. 死鎖處理策略

• 鴕鳥策略（忽略，如 Linux）
• 預防（破壞四條件之一）
• 避免（銀行家演算法）
• 偵測與恢復

7. 行程排程演算法

• FCFS（先來先服務）
• 優先權
• 時間片輪轉
• 多層回授隊列

8. TCP vs UDP

9. (void*)ptr vs (*(void**))ptr

兩者結果相同。前者直接強轉；後者先轉 void**（二級指標），再解參考取內容（一級指標），最後隱式轉 void*。

10. 絕對位址讀寫與跳轉

/* 寫入 0x100000 */
*(unsigned int*)0x100000 = 1234;

/* 跳轉執行 0x100000 */
typedef void(*func_ptr)();
((func_ptr)0x100000)();

嵌入式/核心開發常用，應用層受 MMU 保護通常失敗。