"~"运算符在C++中的作用

时间:2024-11-12 07:29:03

我们在学习新的知识或是观看某些代码时常常看到 “~” 的符号,它是什么意思,有什么作用呢?

1:“~”的作用
“~”的解释为:对某一常数转化为二进制时对各位进行取反,是一种位运算。
举个例子 “4”的二进制码为 “100” 取反之后——》变为 “011”同时正负颠倒,于是“~4”在数值上等于“-5”;
同理“~1046”=“-1047” ,“~0”=“-1”,
等等。

细心的读者已经发现了 “~a”="-(a+1)".
没错,的确是这样。(至少计算结果一样)

2:“~”的应用
我们常常会看到这样的代码

while(~scanf("%d%d",&n,&m))
{
	-------
	***
	-------
}

在这里 当进程读入“n,m”失败后,有些系统会返回一个值,我们称之为“EOF”
这里“~EOF”实际上是等于“0”的。
所以

while(scanf("%d%d",&n,&m)!=EOF)
{
	-------
	***
	-------
}

两段代码是等效的。

除此之外,“~”还可以这么用
以下是一道关于AC自动机的题目的代码(节选)

const int N=1000;
struct AC_automaton
{
	int tr[N][26],cnt;//TRIE
	int e[N];//标记字符串结尾
	int fail[N];//fail指针

	void insert(char * s) //插入模式串
	{
		int p=0;
		for(int i=0; s[i]; i++)
		{
			int k=s[i]-'a';
			if(!tr[p][k])tr[p][k]=++cnt;
			p=tr[p][k];
		}
		e[p]++;
	}
	void build()
	{
		queue<int>q;
		memset(fail,0,sizeof(fail));
		for(int i=0; i<26; i++)if(tr[0][i])(tr[0][i]);
		//首字符入队
		//不直接将0入队是为了避免指向自己
		while(!())
		{
			int k=();
			();//当前结点
			for(int i=0; i<26; i++)
			{
				if(tr[k][i])
				{
					fail[tr[k][i]]=tr[fail[k]][i];//构建当前的fail指针
					(tr[k][i]);//入队
				}
				else tr[k][i]=tr[fail[k]][i];
				//匹配到空字符,则索引到父节点fail指针对应的字符,以供后续指针的构建
				//类似并差集的路径压缩,把不存在的tr[k][i]全部指向tr[fail[k]][i]
				//这句话在后面匹配主串的时候也能帮助跳转
			}
		}
	}
	int query(char *t)
	{
		int p=0,res=0;
		for(int i=0; t[i]; i++)
		{
			p=tr[p][t[i]-'a'];
			for(int j=p; j&&~e[j]; j=fail[j])res+=e[j],e[j]=-1;
		}
		return res;
	}
};
AC_automation ac;

(不准说我水字数 =v=)
我们主要看这一段

int query(char *t)
	{
		int p=0,res=0;
		for(int i=0; t[i]; i++)
		{
			p=tr[p][t[i]-'a'];
			for(int j=p; j&&~e[j]; j=fail[j])res+=e[j],e[j]=-1;
//			这里 当e[j]=-1时,~e[j]==-(-1+1)==0
//			那么e[j]=-1的操作就相当于标记了。 
		}
		return res;
	}
}

这里的~e[j]同样是可以替代的

那么有的读者可能会问了:““~”运算符一点也不直观,我们为什么要用它呢?”

因为位运算快啊!

2019.7.24进行了修改

“~”还可以这么用

//for(int i=0;i<n;i++)
  for(int i=0;i<n;i=-~i)

反正更快就是了(雾)