题解

位运算拆分

• n >> 16：把原高 $16$ 位移动到结果的低 $16$ 位；
• n << 16：把原低 $16$ 位移动到结果的高 $16$ 位，超出 32 位的原高位会被舍弃；
• 使用按位或合并两部分。

公式为：

(n << 16) | (n >> 16)

应使用 uint32_t 或其他 32 位无符号整数，避免有符号数溢出和符号右移问题。

正确性说明

右移后的每一位恰好来自原数高半段，左移后的每一位恰好来自原数低半段。两部分占据互不重叠的 16 位区域，按位或后正好构成交换后的 32 位数。

复杂度

• 时间复杂度：$O(1)$；
• 空间复杂度：$O(1)$。