題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2074C. XOR and Triangle

tags: `位運算(Bitwise Operation)` `貪心(Greedy)`

題意

題目給你一個整數 $x \geq 2$ ，請你找一個正整數 $y$ ，滿足：

$y$ 必須比 $x$ 小
$x$ 、 $y$ 、以及 $x \oplus y$ （ $x$ 和 $y$ 的位元XOR結果）這三個數，能當作三角形的三邊，且這個三角形是非退化的（也就是任意兩邊的和要大於第三邊）

如果有符合條件的 $y$ ，輸出其中一個即可；如果沒有，輸出不存在。

約束條件

$2 \le x \le 10^9$

思路：位運算

設 $z = x \oplus y$ （其中 $\oplus$ 表示 XOR 運算）

三角形成立的條件

根據三角形不等式，三邊長 $x, y, z$ 必須滿足：

$\begin{cases} x + y > z \\ y + z > x \\ z + x > y \end{cases}$

由於需要滿足 $y < x$ ，故：

$z + x > y$ 恆成立
$y + z > x$ 可化為 $z > x - y$

綜合條件，得到：

$x - y < z < x + y$

利用位運算的性質，有：

$\begin{cases} x + y = (x \oplus y) + 2 \times (x \& y) \\ x - y = (x \oplus y) - 2 \times (\sim x \& y) \end{cases}$

其中 $\&$ 表示 AND 運算、 $\sim x$ 表示對 $x$ 逐位取反。

接著，考慮兩種特殊情況：

當 $x \& y = 0$ 時， $x + y = x \oplus y$
當 $\sim x \& y = 0$ 時， $x - y = x \oplus y$
這兩種情況會導致 $z$ 等於邊界值，使得三角形不等式不成立。

為了避免上述兩種情況，可以選擇：

$x$ 的最低位 1
$\sim x$ 的最低位 1

來確保 $z$ 落在嚴格的不等式範圍內，使三角形成立。

複雜度分析

時間複雜度： $O(1)$
空間複雜度： $O(1)$

t = int(input())
lowbit = lambda x: x & -x

for _ in range(t):
    x = int(input())
    y = lowbit(x) | lowbit(~x)
    print(y if y < x else -1)

寫在最後

PROMPT

masterpiece, best quality, high quality, highres, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style, cover art,

1girl, solo, Koyori, Hakui Koyori, Hakui Koyori (hololive), pink hair, long hair, braids in hair, purple eyes, fox ears, fox tail, black choker, white short-sleeved blouse, pink bow, pink trim on blouse, pink and purple plaid pleated skirt, white thigh garter on left leg, white knee-high socks, lace-trimmed socks, brown loafers,

reaching up to touch cherry blossoms, sitting on stone wall, spring season, cherry blossom trees in full bloom, soft dreamy lighting, urban background with buildings, gentle breeze, sakura petals falling, peaceful atmosphere, outdoors, clear spring day, looking up with wonder

In this enchanting spring scene, Hakui Koyori sits gracefully on a stone wall beneath a canopy of blooming cherry trees. The soft pink petals create a dreamlike atmosphere around her as she reaches up with one hand to gently touch the blossoms. Her expression captures a moment of serene wonder as she gazes upward at the beautiful sakura, with delicate petals occasionally drifting down in the gentle spring breeze.

~~不能只有我做到的位運算題目~~，話說這真的只有 1100 嗎？