首页 > 代码库 > nyoj744(位运算)
nyoj744(位运算)
题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=744
思路:a^b可以得到a~b间任意两个数异或运算的长度的最大值,设为n,答案为:pow(2, n)-1;
(1):如果a,b长度相同的话,假设a^b得到的最高为1的位置为q(前面都是1异或值为0),我们可以通过对q前面的高位数退位得到q后面的数的所有情况,一定存在一种情况使得异或运算后q后面的数全部为1,此时得到最大值为pow(2, n)-1;
(2):如果a, b长度不同的话,那么a~b间任意两个数异或能得到最大的长度即为b的长度,设为n,那么一定存在一个数x使得x^b的结果二进制全部为1,即长度为n且所有位都为1,十进制表示为pow(2, n)-1;因为我们可以同过对b首位1退位得到满足上述条件的x;
代码:
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int main(void){ 6 ll a, b; 7 while(~scanf("%lld%lld", &a, &b)){ 8 ll c=a^b; 9 int ans=0;10 while(c){11 c/=2;12 ans++;13 }14 cout << (ll)(pow(2, ans)-1) << endl;15 }16 return 0;17 }
nyoj744(位运算)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。