位运算

逻辑运算符

$and$, & 两者都为真才是真，否则都是假

$or$, | 一者为真则为真，两者为假才为假

$xor$ 两者相同则为假，两者不同则为真 (^ 在程序里表示异或运算，但它是乘方运算)

$a$ $xor$ $b$ = $b$ $xor$ $a$; $a$ $xor$ $b$ $xor$ $a$ = $b$;

$not$, ~ 真取反为假，假取反为真

移位运算

左移

$1$ << $n$ = $2^n$ ; $n$ << $1$ = $2n$

算数右移

$n$ >> $1$ = $\left\lfloor\frac{n}{2.0}\right\rfloor$

c++中“/”是向“0”取整，“>>”是向下取整。比如$\left(-3\right) >> 1 = -2$, $\left(-3\right) / 2 = -1$。

逻辑右移

在二进制补码下把数字向右移动，高位补0，低位直接丢掉。

一些骚操作

二进制状态压缩

$n$为整数，操作在二进制下。

取$n$的第$k$位：($n$ >> $k$) & $1$;

取$n$的$0$~$k - 1$位：$n$ & (($1$ << $k$) - $1$)

$n$的第$k$位取反： $n$ $xor$ ($1$ << $k$)

$n$的第$k$位赋值1： $n$ | ($1$ << $k $)

$n$的第$k$位赋值0： $n$ & (~($1$ << $k$))

成对变换

当$n$为偶数时， $n$ $xor$ $1$ = $n$ + $1$;

当$n$为奇数时，$n$ $xor$ $1$ = $n$ - $1$。

这个性质经常会用于图论的存边里。

求平均数

$a$ $b$ 不大的时候： $mid$ = ($a$ + $b$) >> $1$;

$a$ $b$ 相加爆$long$ $long$时：$mid$ = ($a$ & $b$) + (($a$ $xor$ $b$) >> $1$);~~(好像没用过)~~

为啥呢？它的原理就是相同位加上不同位除以二。

找一个集合只出现一次的数（其它数都是两次）

int single_num(int a[]) {
    int res = a[1];
    for(int i = 2;i <= n; i++) res ^= a[i];
    return res;
}

例题

位运算一般不会单独考，它会用到很多地方，例如线段树，树状数组，dp，图论, 数论等。

~~（所以没有例题啦）~~咳

P4310 绝世好题

题目大意：给定一个长度为$n$的数列 $a_i$，求 $a_i$ 的子序列 $b_i$ 的最长长度 $k$，满足 $b_i$&$b_{i - 1}$$\ne$0，其中 $2\leq i\leq k$，& 表示位运算取与。

我们考虑用一个数组$f$[$j$]表示当前状态下最后一个数为止二进制第$j$位满足条件的最长子序列长度，设新加入的数为$x$，上一个数为$y$，只要$x$， $y$二进制下有一位都为$1$，那么长度就能更新$max$($f$[$j$] + $1$)。设更新完的最大长度为$max$，那么$x$所有为$1$的发$f$[$j$]都可以更新为$max$。我们在找一个数的每一位时，可以用刚刚讲的那个$x$ & ($1$ << $j$)。

#include <iostream>
#include <cstdio>

using namespace std;

inline int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * f;
}

const int N = 33;
int n, x, ans;
int f[N];

int main() {
	
	n = read();
	for(int k = 1;k <= n; k++) {
		x = read(); int maxn = 0;
		for(int i = 0;i < 32; i++) {
			if(x & (1 << i)) {
				f[i]++; maxn = max(f[i], maxn);
			}
		}
		for(int i = 0;i < 32; i++) {
			if(x & (1 << i)) f[i] = maxn;
		}
	}																					
	for(int i = 0;i < 32; i++) ans = max(ans, f[i]); 
	printf("%d", ans);
	
	
	return 0;
}