位運算進階

2021 年 1 月 15 日
筆記
位運算

編碼
光速大整數乘法
二進位狀態壓縮
- 位運算操作
- 運算符優先順序
$lowbit$ 計算
- 推導
- Code
- 內置函數
參考文獻

編碼

在 m 位二進位數中，通常稱最低位為 0 位，從右到左以此類推，最高位為 $m-1$ 位。

當無符號整數 (unsigned) 爆了的時候，它會自動 %，不會爆出負數。

C++ 的十六進位常常以「0x」開頭，「0x」後面的部分對應具體的十六進位的數值。當使用 memset 時，memset 只能賦值出「每 8 位都相同的數」。當需要把一個數組中的數值初始化為正無窮時，為了避免加法算術上溢出或者繁瑣的判斷，我們經常用 memset(a, 0x3f, sizeof(a)) 給數組賦 0x3F 3F 3F 3F 的值來代替。

對於數字 0x3F 3F 3F 3F，它是滿足以下兩個條件的最大整數：

整數的兩倍不超過 0x7F 7F 7F 7F，即 int 能表示的最大正整數。
整數的每 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

Tags: 位運算