1356. Sort Integers by The Number of 1 Bits

Sort Integers by The Number of 1 Bits

題目描述：給定整數陣列 arr，按照每個整數的二進位表示中「1 的個數（popcount）」升序排列；若兩個整數的 popcount 相同，則按照數值大小升序排列。回傳排序後的陣列。

解題思路：這是一道自訂排序鍵的題目。使用 C++ 的 std::sort 搭配自訂比較函式：比較兩個元素時，先計算各自的 popcount，若不同則以 popcount 升序為主鍵；若相同則以數值升序為次鍵。

計算 popcount 有多種方式：

1. __builtin_popcount(x)：GCC 內建函式，編譯器自動生成 POPCNT 指令，最快。
2. Brian Kernighan 演算法：迴圈 x &= x - 1 每次消除最低位的 1，迴圈次數等於 1 的個數。
3. C++20 std::popcount：標準函式庫支援。

由於每個元素值不超過 10^4 < 2^14，popcount 最大為 14，比較操作非常輕量。

時間複雜度：O(N log N)——std::sort 的比較次數為 O(N log N)，每次比較呼叫 __builtin_popcount 為 O(1)（單條 CPU 指令），整體由排序主導。

空間複雜度：O(log N)——std::sort 的遞迴 stack 深度（introsort 實作），就地排序不需額外陣列空間。

方法一：預計算 popcount 陣列 先用一個額外陣列 bits[i] = popcount(arr[i]) 儲存所有元素的 popcount，排序時直接查表而非重複計算。在 N 很大時可避免重複呼叫 popcount（雖然本題 popcount 已是 O(1)），程式碼清晰但多用 O(N) 空間。

方法二：計數排序（Counting Sort by popcount） 由於 popcount 範圍僅 0–14（元素值 ≤ 10^4 < 2^14），可先將元素按 popcount 分桶（14 個桶），每桶內再排序，最後合併。時間複雜度 O(N log N)，但分桶使局部排序的元素更少，常數因子更小。

方法三：Radix Sort 變體 將 (popcount, value) 作為 2-tuple 進行 radix sort，先按 value 穩定排序，再按 popcount 穩定排序。整體 O(N)，但實作複雜度遠超題目難度，不推薦。

1. 若需要按「popcount 降序、數值降序」排列，比較函式需要如何修改？能否使用 std::stable_sort 分兩次排序來達到同樣效果？
2. __builtin_popcount 在不同 CPU 架構（如不支援 POPCNT 指令的舊處理器）上的行為是什麼？是否有可移植的替代方案？
3. 若輸入陣列中有重複元素，且要求排序結果穩定（相同鍵值的元素保持原始相對順序），應使用 std::stable_sort 還是 std::sort？兩者的時間複雜度差異是什麼？