题意

·给定一条边的长度x, 求满足条件的长度y（y < x），使得x, y, x⊕y 构成非退化的三角形的三条边。

分析

·首先对x, y,和x⊕y， 要构成非退化三角形 需要满足 x + y > x⊕y , y + x⊕y > x, x⊕y + x > y;

·我们先看看y + x⊕y > x 的，因为：

·对二进制表示的x,y ：

·对应为 x 位为 0 ， y 位为 0 时， x⊕y该位也为 0， 大小与x一致

·对应为 x 位为 0 ， y 位为 1 时， x⊕y该位为 1， 比x大

·对应为 x 位为 1 ， y 位为 0 时， x⊕y该位也为 1，大小与x一致

·对应为 x 位为 1 ， y 位为 1 时， x⊕y该位为 0，虽然比x小， 但是最后 + y 可以补回来而且其他位x⊕y绝对不小于x

·所以y + x⊕y > x 成立， 需要有对应为 x 位为 0 ， y 位为 1

·又由题目条件 y < x

·所以x⊕y + x > y也必然成立

·这样以来题目就变成了找小于x的y， 同时有对应为 x 位为 0 ， y 位为 1 使得 x + y > x⊕y 成立

·我们知道当x 与 y 没有位数都为1时， x + y = x⊕y

·所以当x y 有位数都为1时，则都是一的那一位会变为0， 此时就有 x + y > x⊕y 了

·所以我们就知道了满足条件的y的条件

·有对应位数x为0而y为1， 且有对应位数 与 x都为1， 且 y < x

算法实现

·结合样例里输出-1的情况，我们可以发现：

·当x 为 2 ^ k - 1 ，即 x二进制为全1时， 我们找不到对应的y对应位数x为0而y为1, 因为此时没有 < x 的数有位数为1， 而对应x的位数为0

·当x 为 2 ^ k , 即 x二进制为单个1后面全0时，我们找不到对应的y有对应位数 与 x都为1， 因为唯一能与x对应位数都为1， 必须包含x那个1的一位， 即一定比x大

所以我们特判这两种情况即可

我们可以发现，全1的情况 + 1 可以转化为1后全0的情况

而对1后全0的情况，我们可以使用lowbit， 取x最后一位1对应的数与x是否相等来判断

// lowbit 利用补码特性，不知道且感兴趣可以自行学习，总之 -x = ~x （x的反码，即01都反过来） + 1， 所以 x & -x 即为x从右往左第一个1对应的数

int lowbit(int x)
{
	return x & (-x);
}

bool check(int x)
{
	return x == lowbit(x);
}

·然后构建可行的y,我们知道只要满足对应位数x为0而y为1， 且有对应位数 与 x都为1， 且 y < x的y 都是可行的

·所以可以找到x的最后一个0和最后一个1， 对应位为1其他位为0也是可以是满足条件的y

而找最后一个0， 可以用 x反码的lowbit实现

找最后一个1，可以用x的lowbit实现

printf("%d\n", lowbit(~n) + lowbit(n));

这样一来，我们通过lowbit，让成功实现了O(1)的可行判定， 和O(1)的结果计算

·时间复杂度O(T), 空间复杂度O(1);

完整代码

// n 即为 x 习惯了(

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 

using namespace std;

int n;

int lowbit(int x)
{
	return x & (-x);
}

bool check(int x)
{
	return x == lowbit(x);
}

int main()
{
	int T;
	scanf("%d", &T);
	
	while(T -- )
	{
		scanf("%d", &n);
		if (check(n) || check(n + 1))
		{
			puts("-1");
			continue;
		}
		printf("%d\n", lowbit(~n) + lowbit(n));
	}
	
	return 0;
}

希望对大家有所帮助qwq.