~是按位取反运算符
这里先说一下二进制在内存的存储：二进制数在内存中以补码的形式存储
另外，正数的原码、补码和反码都相同
负数的反码与原码符号位相同，数值为取反；补码是在反码的基础上加1
比如：
~9的计算步骤：
转二进制：0 1001
计算补码：0 1001
按位取反：1 0110
转为原码：1 0110
按位取反：1 1001 反码
末位加一：1 1010 补码
符号位为1是负数，即-10
规律：~x=-（x+1）；
因此，t=~9（1001）并不能输出6（0110），而是-10；
牛客网暑假训练第七场A题：
链接：https://www.nowcoder.com/acm/contest/145/A
来源：牛客网
题目描述
The weight of the edge connecting two vertices with numbers x and y is 
(bitwise AND).
Your task is to find a minimum cost perfect matching of the graph, i.e. each vertex on the left side matches with exactly one vertex on the right side and vice versa. The cost of a matching is the sum of cost of the edges in the matching.
denotes the bitwise AND operator. If you're not familiar with it, see {https://en.wikipedia.org/wiki/Bitwise_operation#AND}.
输入描述:
The input contains a single integer n (1 ≤ n ≤ 5 * 10
5
).
输出描述:
Output n space-separated integers, where the i-th integer denotes p
i
(0 ≤ p
i
≤ n - 1, the number of the vertex in the right part that is matched with the vertex numbered i in the left part. All p
i
should be distinct.
Your answer is correct if and only if it is a perfect matching of the graph with minimal cost. If there are multiple solutions, you may output any of them.
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
const int N=5e+5;
int a[N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin>>n;
memset(a,-1,sizeof(a));
for(int i=n-1;i>=0;i--)
{
int t=~i,k=0;//此时t是以补码输出的，是负数
/***********************
9 1001
取反 0110
& 1111
得: 0110
*/cout<<t;
while(1<<k<i)k++;
cout<<(1<<k)-1;
t=t&((1<<k)-1);cout<<t<<endl;
if(a[i]==-1)
a[i]=t,a[t]=i;
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/zhgyki/p/9452637.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/279107
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
