【语法相关】基本位运算
Audrey_Hall
·
·
算法·理论
位与（&）
给定两个长度相同的二进制串 A,B（不同则在前面补0），A\&B 的结果的每一位由 A 与 B 的对应位决定，如果 A 与 B 的对应位均为 1，则结果的那一位为 1，否则为 0。
位或（|）
**位异或（xor/^）**
$A$ ^ $B$ 的结果的每一位同样由 $A$ 与 $B$ 的对应位决定，如果 $A$ 与 $B$ 的对应位不相同，则结果的那一位为 $1$，否则为 $0$。
**左移（<<）**
$a<<b,b$ 以十进制表示，表示将 $a$ 的最右边（最低位）加上 $b$ 个 $0$（相当于乘上了 $2^n$）。
**右移（>>）**
$a>>b,b$ 以十进制表示，表示将 $a$ 的最右边（最低位）的 $b$ 位删掉（相当于整除 $2^n$）。
$x<<y=x·2^{y}
x>>y=\dfrac x{2^{y}}
2^a+1=(1<<a)|1
a\%2=a$ & $1
| 运算类型 |
符号表示 |
速度单位量 |
| 逻辑运算 |
&& \|\ ! |
1 个单位 |
| 位运算 |
& | ^ <<\ >> |
32 个单位 |
| 关系运算 |
==\ !=\ <\ \le\ >\ \ge |
60 个单位 |
| 算数运算 1 |
+\ - |
100 个单位 |
| 算数运算 2 |
×(\ast) |
1000 个单位 |
| 算数运算 3 |
÷(/)\ \% |
10000 个单位 |
lowbit()
lowbit(x) 是 x 的二进制表达式中最低位的 1 所对应的值。
lowbit(0)=0;
常用写法
inline int lowbit(int x){
return x&(-x);
//return (x^(x-1))&x;
}
//利用了负整数的补码特性
x&(-x); 通过计算机编码特性（负整数的补码特性）得出；(x^(x-1))&x 通过数学 + 二进制的方式得出。
用法
维护区间
即树状数组。
n-lowbit(n)
**常用写法**
`n&(n-1)`