我们在学习新的知识或是观看某些代码时常常看到 “~” 的符号,它是什么意思,有什么作用呢?
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)
反正更快就是了(雾)