位运算进阶

目录

编码

在 m 位二进制数中,通常称最低位为 0 位,从右到左以此类推,最高位为 \(m-1\) 位。

当无符号整数 (unsigned) 爆了的时候,它会自动 %,不会爆出负数。

C++ 的十六进制常常以 “0x” 开头,“0x” 后面的部分对应具体的十六进制的数值。当使用 memset 时,memset 只能赋值出 “每 8 位都相同的数”。当需要把一个数组中的数值初始化为正无穷时,为了避免加法算术上溢出或者繁琐的判断,我们经常用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3F 3F 3F 3F 的值来代替。

对于数字 0x3F 3F 3F 3F,它是满足以下两个条件的最大整数:

  1. 整数的两倍不超过 0x7F 7F 7F 7F,即 int 能表示的最大正整数。
  2. 整数的每 8 位(每个字节) 都是相同的。

光速大整数乘法

  • 时间复杂度为 \(O(1)\)

    ull mul(ull a,ull b,ull p)
    {
        a%=p;
        b%=p;
        ull c=(long double) a*b/p;
        ull x=a*b;
        ull y=c*p;
        ll ans=(ll)(x%p)-(ll)(y%p);
        if(ans<0) ans+=p;
        return ans;
    }
    
  • 时间复杂度为 \(O(\log_2b)\)

    ll mul(ll a,ll b,ll p)
    {
        ll ans=0;
        for(;b;b>>=1)
        {
            if(b&1) ans=(ans+1)%p;
            a=a*2%p;
        }
        return ans;
    }
    

二进制状态压缩

位运算操作

二进制状态压缩,是指将一个长度为 m 的 bool 数组用一个 m 位二进制整数表示并存储的方法。利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。

操作 运算
取出 n 的第 k 位 ( n >> k ) & 1
取出 n 的后 k 位( 0 ~ k-1 位) n & ( ( 1 << k ) - 1 )
将第 k 位取反,赋值到 n n = n xor ( 1 << k )
将第 k 位变为 1,赋值到 n n |= ( 1 << k )
将第 k 位变为 0,赋值到 n n &= ( ~ ( 1 << k ) )

这种方法运算简便,比暴力从十进制算出二进制的每一位节省了大量的时间和空间。

推荐题目:CSP-S2020 动物园

运算符优先级

从高到低排列:

加减 移位 比较大小 按位与 按位异或 按位或
+ , - << , >> > , < , == , != & xor ( C++ ^ ) |

如果不确定优先级,则可以加一些括号,以保证运算顺序的正确性。

\(lowbit\) 计算

lowbit(n) 定义为非负整数 n 在二进制表示下 “最低位的 1 及其后边所有的 0 构成的数值”。

推导

\(n>0\)\(n\) 的第 \(k\) 位是 \(1\),第 \(0\) ~ \(k-1\) 位都是 \(0\)

为了实现 lowbit 运算,先把 \(n\) 取反,此时第 \(k\) 位变为 0, 第 \(0\) ~ \(k-1\) 位都是 1。再令 \(n=n+1\) ,此时因为要进位,第 k 位变为 1 ,第 \(0\) ~ \(k-1\) 位都是 0。

在上面的取反加 1 操作后,\(n\) 的第 \(k+1\) 到最高位恰好与原来相反,所以 \(n ~\& ~(\sim n+1)\) 仅有第 \(k\) 位为 1,其余位都是 0。而在补码表示下,\(\sim n = -1-n\),因此:

\[lowbit(n)=n ~\& ~(\sim n+1) = n ~\& ~(-n) \]

Code

配合 Hash 代替 \(\log\) 运算,可以使复杂度降低。

const maxn = 1 << 20;
int H[maxn];
for(int i=0; i<=20; ++i)
    H[1 << i] = i; //预处理

while(cin >> n) //对多组数据进行求解
{
    while(n > 0)
    {
        cout << H[n & -n] << ' ';
        n -= n & -n;
    }
    puts("");
}

内置函数

下面这些仙术可以高效计算 lowbit 以及二进制中 1 的个数。但是,部分竞赛禁止 使用下划线开头的库函数,所以这些内置函数在竞赛里不要使用。

  • 返回 \(x\) 的二进制表示下最低位的 1 后面有多少个 0:
    int __builtin_ctz (unsigned int x)
    long long __builtin_ctzll (unsigned long long x)

  • 返回 \(x\) 的二进制表示下有多少位为 1:
    int __builtin_popcount (unsigned int x)
    int __builtin_popcountll (unsigned long long x)

参考文献

李煜东 《算法竞赛 进阶指南》

EdisonBa

2021.1.15

发表评论

评论已关闭。

相关文章