玄关(违规紫衫)
  • 板块灌水区
  • 楼主_Tatsu_
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/8/12 13:19
  • 上次更新2024/8/12 14:35:36
查看原帖
玄关(违规紫衫)
1224895
_Tatsu_楼主2024/8/12 13:19

LaTeX求调

### 思路
观察样例 `12 4`,$12 \oplus 4=(1100)_2 \oplus (100)_2=(1000)_2=8$,毫无头绪。

而 ``57 37`` 中,$57 \oplus 37=(111001)_2\oplus(100101)_2=(011101)_2=4$。
这么一看,好像有点规律了。

异或后的结果进行 $\text {lowbit}$ 函数的处理,返回值不就对上了吗?

所以我们输入 $x$,$y$,输出 $(x \oplus y)\land(-(x \oplus y))$ 即可。

### 关于 $\text {lowbit}$ 的简要说明
$\text {lowbit} (n)$ 的定义为非负整数 $n$ 在二进制表示下“最低位的 $1$ 及其后面的所有的 $0$”的二进制构成的数值。

我们假设 $n > 0$,设 $n$ 的二进制表示中,第 $k$ 位为 $1$,第 $0$ 至第 $k-1$ 位都为 $0$。

现在我们对 $n$ 的二进制进行取反操作,可以得到 $\neg {n}$ 的二进制中第 $k$ 位为 $0$,第 $0$ 至第 $k-1$ 位都为 $1$,然后我们再将 $n$ 进行加 $1$ 操作,可以得到一个结果为 $\neg n+1$ 的第 $k+1$ 位至其最高位都为 $n$ 的二进制表示中相反的数字,然后我们再将 $\neg n+1$ 与 $n$ 进行与运算,就可以得到我们想要的结果了。又因为 $\neg n=-1-n$,所以 $-n = \neg {n+1} $。

### AC Code

```cpp
#include <bits/stdc++.h>
#define int long long
#define fro for//防手滑
using namespace std;
signed main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
    int t;
    cin>>t;
    while (t--)
	{
        int x,y;
        cin>>x>>y;
        int xorr=(x^y)&-(x^y);//先异或,再lowbit函数
        cout<<xorr<<endl;
    }
	return 0;
}
2024/8/12 13:19
加载中...