『算法-ACM 竞赛-疯子的算法总结』1 位运算（快速幂、快速乘）

一、预备知识（补码，反码）

计算机通过二进制表示整形数，比如 int 型 32 位有符号整形数：
1 表示为：0000…..00001(共 32 位）
-1 表示为：1111…..1111(共 32 位）
补码计算法定义：非负数的补码是其原码本身；
负数的补码是其绝对值的原码最高位符号位不变，其它位取反，再加 1。
表示原因：计算机逻辑运算没有减法，-1+1 最高为溢出，剩余 0000000000（32 位）即为 0；
则有 a-b=a+b 的（补码）；
计算方式：
-1 表示原码为 100…….0001(32 位），最高位位符号位。
-1 的反码表示为：1111………110(32 位），除符号位按位取反。
-1 的补码表示为：1111………1111(32 位），反码+1。
正数的补码为自己本身。
例子：
100 的补码 ‭00000000000000000001100100‬
-30 的补码 11111111111111111111111100010‬
100+（-30）=000000000000000000‭01000110‬
转换成 10 进制为 70；

二、基本操作

1、按位与(&)

参加运算的两个数，换算为二进制(0、1)后，进行与运算。只有当相应位上的数都是 1 时，该位才取 1，否则该为为 0。

将 10 与-10 进行按位与(&)运算：
|0000 0000 0000 1010
|——-
|1111 1111 1111 0110
|0000 0000 0000 0010
所以：10 & -10 = 0000 0000 0000 0010
2、按位或(|)

参加运算的两个数，换算为二进制(0、1)后，进行或运算。只要相应位上存在 1，那么该位就取 1，均不为 1，即为 0。

将 10 与-10 进行按位或(|)运算：

| 0000 0000 0000 1010
|——————
|1111 1111 1111 0110
|1111 1111 1111 1110

所以：10 | -10 = 1111 1111 1111 1110
3、按位异或(^)

参加运算的两个数，换算为二进制(0、1)后，进行异或运算。只有当相应位上的数字不相同时，该为才取 1，若相同，即为 0。

将 10 与-10 进行按位异或(^)运算：

| 0000 0000 0000 1010 |

|1111 1111 1111 0110|
1111 1111 1111 1100|
所以：10 ^ -10 = 1111 1111 1111 1100
可以看出，任何数与 0 异或，结果都是其本身。利用异或还可以实现一个很好的交换算法，用于交换两个数，算法如下：

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

4、取反(~)

参加运算的两个数，换算为二进制(0、1)后，进行取反运算。每个位上都取相反值，1 变成 0，0 变成 1。
对 10 进行取反()运算：
|0000 0000 0000 1010
|—————-|
|1111 1111 1111 0101
所以：10 = 1111 1111 1111 0101
5、左移(<<)

参加运算的两个数，换算为二进制(0、1)后，进行左移运算，用来将一个数各二进制位全部向左移动若干位。

对 10 左移 2 位(就相当于在右边加 2 个 0)：

0000 0000 0000 1010
0000 0000 0010 1000
所以：10 << 2 = 0000 0000 0010 1000 = 40
注意，观察可以发现，左移一位的结果就是原值乘 2，左移两位的结果就是原值乘 4。

6、右移(>>)

参加运算的两个数，换算为二进制(0、1)后，进行右移运算，用来将一个数各二进制位全部向右移动若干位。

对 10 右移 2 位(就相当于在左边加 2 个 0)：

0000 0000 0000 1010
0000 0000 0000 0010

所以：10 >> 2 = 0000 0000 0000 0010 = 2
注意，观察可以发现，右移一位的结果就是原值除 2，左移两位的结果就是原值除 4，注意哦，除了以后没有小数位的，都是取整。

三、延伸操作

1.快速幂（快速模幂）
① 求 a^b:

int pow(int a, int k)  {
    int ans = 1;
    while(k)  {
        if(k &1)  ans *= a;   //判断奇偶只用判断最后一位比取模快
        a *= a;
        k >>=1;		//比除法快多了
    }
    return ans;
}

② 求 a^b%p

int pow_mod(int a, int k,int mod)  {
     int ans = 1%mod;
     while(k)  {
         if(k &1)  ans =(long long) ans*a%mod;  //防止在对P取模前溢出
         a = (long long)a*a%mod;
         k >>=1;  //比除法快多了
     }
     return ans;
 }

例题：BZOJ1008
2.快速乘法
方法 ①

long long quickMul(long long a,long long b,long long mod)
{
    long long ans=0;
    while(b){
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;  //（计算机加法比乘法快，a+a比a*2快）
        b>>=1;
    }
    return ans;
}

方法 ②：高效算法

long long quickMul(long long a,long long b,long long mod)
{
    a%=mod;
    b%=mod;
    long long  ans=0;
    while(b){
        if(b&1){
            ans+=a;
            if(ans>=mod)
               ans-=mod;
        }
        b>>=1;
        a<<=1;
        if(a>=mod)  a-=mod;
    }
   return ans;
}

方法 ③：使用 long double 优化版

long long quickMul(long long a,long long b,long long mod)
{
    a%=mod;
    b%=mod;
    long long c=(long double) a*b/mod;
    long long ans=a*b-c*mod;
    if(ans<0) ans+=mod;
    else if(ans>=mod) ans-=mod;
    return ans
  }

在这里仅提到部分操作，在 ACM 学习中，还有更多的操作可以用位运算。