目录

  • 位运算前言
  • 位运算应用
    • 1 快速幂
    • 2 最大公约数
    • 3 xor 一些应用
    • 4 其他

位运算前言

程序中所有东西在计算机中都是以二进制储存的。

位运算可以直接操作这些二进制。

所以位运算相对于普通运算要快。

这些是所有位运算及其优先级：

注意区分逻辑运算和按位运算的区别，逻辑运算视所有 \(\neq 0\) 的数为 \(\texttt{True}\)（\(1\)）。

对于全体运算来说：

运算
逻辑非（not，!）；按位取反（~ )
乘法（*）；除法（/）；取模（mod，%）
加法（+）；减法（-）
左移（<<）；右移（>>）
大于（>）小于（<），大于等于（>=），小于等于（<=）

转进制IO

一些格式化符：

进制 iomanip 格式化符 printf 格式化符
十进制 dec %d
八进制 oct %o
十六进制 hex %x

注意 cin 的格式化符延长至整个程序，用 dec 恢复！！

位运算应用

  1. 快速幂
  2. 最大公约数

1 快速幂

给定 \(a,n\) 计算 \(a^n\)。

最朴素的做法当然是 \(\mathcal{O}(n)\) 暴力乘。

typedef long long ll;
ll power(ll a,int n)
{
	ll ans=1;
    for (int i=0;i<n;i++) ans*=a;
    return ans;
}

我们优化一下。

如果我们计算 \(7^{31}\)。

我们做一下变式：

\(\begin{aligned} 7^{31}&=7^{2^0+2^1+2^2+3^3}\\ &=7^{1+2+4+16}\\ &=7^1\times 7^2\times 7^4\times 7^{16} \end{aligned}\)

我们对于这个变式，考虑二进制拆分。

\(31\) 正好分成了 \(2\) 的正整数次幂，是否所有数字都可以呢？

尝试 \(7^{11}\)，\(11=1+2+8\)，发现少了个 \(4\)。

\(11=(1101)_2\)，每一个幂都乘此数的每一位即可。

\[11=2^{\color{red}{1}\color{black}\times 1}\times2^{\color{red}{1}\color{black}\times 2}\times 2^{\color{red}{0}\color{black}\times 3}\times 2^{\color{red}{1}\color{black}\times 4} \]

所以这样模拟即可，\(\mathcal{O}(\log n)\) 时间复杂度。

其中 \(a^n\) 可以用一个 \(\texttt{base}=a^{n-1}\)，\(\texttt{base}=\texttt{base}*\texttt{base}\) 求得。

typedef long long ll;
ll qpow(ll a,ll b,ll mod)   //带上取模QAQ
{
	ll ans=1,base=a;
	while (b)                         //没有乘完
	{
		if (b&1) ans*=base,ans%=mod;  //如果这一位为 1，自乘
		base*=base;b>>=1;base%=mod;   //更新 base，进入下一位（b>>=1）
	}
	return ans%mod;    //如果 b=0，那么如果模数为 1 不加 %mod 就会 WA。
}

2 最大公约数

众所周知有辗转相除法：

\[\gcd(a,b)=\gcd(b,a\bmod\,b) \]

朴素算法也就是这个，最坏被卡 \(\mathcal{O}(\log n)\)。

int gcd(int a,int b){return b?gcd(b,a%b):a;}

我们知道有更相减损术：

\[\gcd(a,b)=\gcd(b,a-b) \]

我们能减半尽量要减半，具体看代码即可。

typedef long long ll;
ll gcd(ll a,ll b)  //优化后
{
    if (b==0) return 0;    //特判
    if (a<b) return gcd(b,a); //交换顺序
    if (a==b) return b;    //边界
    if (a&1)    //如果 a 是奇数
    {
        if (b&1) return gcd(b,a-b); //如果 b 也是奇数，只能更相减损
        else return gcd(a,b>>1);  //b 是偶数，减半
    }
    else  //如果 a 是偶数 
    {
        if (b&1) return gcd(a>>1,b);  //b 是奇数，a 减半
        else return 2*gcd(a>>1,b>>1); //都是偶数，一起减半，答案 *2。
    }
}

3 xor 一些应用

首先有个性质：

x^0=x，x^1=~x。

x^p^p=x，即异或为异或的逆运算。

因异或为异或的逆运算，所以异或是唯一的可逆运算（位运算中）。

所以可以进行简单加密：

  • 两人持有密钥
  • 第一人将自己的数字异或密钥后传至互联网
  • 第二人收到后再次异或密钥，获得原文。

异或还可以做一个交换：

a=a^b;b=a^b;a=a^b;

缺点：

  1. 慢
  2. 不能处理同一个变量

总之，别用这种交换。

4 其他

  • 取二进制末 \(k\) 位：a&((1<<k)-1)；
  • 取二进制第 \(k\) 位：(a>>(k-1))&1；
  • 取二进制第一个 \(1\) 与后面的 \(0\) 组成的数字（\(\texttt{lowbit}\)）：x&(-x)；
  • 将最后一个 \(1\) 去除：x&=(x-1)；
  • 将右数第 \(k\) 位置 \(1\)：a=(a|(1<<(k-1)))；
  • 将右数第 \(k\) 位置 \(0\)：a&=1<<(k-1)；
  • 将右数后 \(k\) 位置 \(1\)：a&=(1<<(k+1))-1；
  • 将右数后 \(k\) 位置 \(0\)：a&=~((1<<(k+1))-1)；
  • 将右数第 \(k\) 位取反：a^=(1<<k)；
  • 将右数后 \(k\) 位取反：a^=((1<<(k+1))-1)；
  • x==-1：~x
  • x==0：!x
  • x%2：x&1