「轉載】擅長位運算的王大同學

轉載自火星大王在他自己搭建的蒟蒻雲上的相關篇目¹。

Basic Operations

Shifting Left

將A的二進製表示的每一位向左移B位，左邊超出的位截掉，右邊不足的位補0

1 2	A = 1100 A << 2 = 110000

Shifting Right

右移操作分為算數右移和邏輯右移
算術右移是帶符號的右移，邏輯右移是不帶符號的右移。
算術右移：將A的二進製表示的每一位向右移B位，右邊超出的位截掉，左邊不足的位補符號位。
邏輯右移：將A的二進製表示的每一位向右移B位，右邊超出的位截掉，左邊不足的位補0。
在C語言中，當操作的變量類型有unsigned修飾時，是邏輯右移，否則是算術右移。

1 2	A = 11111111111111111111111110000001 A >> 2 = 11111111111111111111111111100000

Exceptions during Shifting

人們在“長期實踐”中發現，對於以下代碼

#include <stdio.h>
void display(unsigned x)
{
    for(int i=31;i>=0;i--)
        printf("%d", (x>>i)&1);
    putchar('\n');
}
int main()
{
    int a=1;
    display(1<<32);
    display(a<<32);
    display(1<<-4);
    display(a<<-4);
    return 0;
}

輸出是

00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000000
00010000000000000000000000000000

看起來似乎很奇怪。
我们使用GDB查看以下汇编代码

Assembly

0x000000000040159c <+0>:     push   %rbp
0x000000000040159d <+1>:     mov    %rsp,%rbp
0x00000000004015a0 <+4>:     sub    $0x30,%rsp
0x00000000004015a4 <+8>:     callq  0x4016b0 <__main>
0x00000000004015a9 <+13>:    movl   $0x1,-0x4(%rbp)
0x00000000004015b0 <+20>:    mov    $0x0,%ecx
0x00000000004015b5 <+25>:    callq  0x401550 <_Z7displayj>
0x00000000004015ba <+30>:    mov    $0x20,%edx
0x00000000004015bf <+35>:    mov    -0x4(%rbp),%eax
0x00000000004015c2 <+38>:    mov    %edx,%ecx
0x00000000004015c4 <+40>:    shl    %cl,%eax
0x00000000004015c6 <+42>:    mov    %eax,%ecx
0x00000000004015c8 <+44>:    callq  0x401550 <_Z7displayj>
0x00000000004015cd <+49>:    mov    $0x0,%ecx
0x00000000004015d2 <+54>:    callq  0x401550 <_Z7displayj>
0x00000000004015d7 <+59>:    mov    $0xfffffffc,%edx
0x00000000004015dc <+64>:    mov    -0x4(%rbp),%eax
0x00000000004015df <+67>:    mov    %edx,%ecx
0x00000000004015e1 <+69>:    shl    %cl,%eax
0x00000000004015e3 <+71>:    mov    %eax,%ecx
0x00000000004015e5 <+73>:    callq  0x401550 <_Z7displayj>
0x00000000004015ea <+78>:    mov    $0x0,%eax
0x00000000004015ef <+83>:    add    $0x30,%rsp
0x00000000004015f3 <+87>:    pop    %rbp
0x00000000004015f4 <+88>:    retq
0x00000000004015f5 <+89>:    nop
0x00000000004015f6 <+90>:    nop
0x00000000004015f7 <+91>:    nop

可以看到有4个callq 0x401550 <_Z7displayj>
我們用這個可以把代碼分成四節，可以看到，對於1<<32和1<<-4,是沒有移位指令shl的，也就是說，GCC幫我們直接算出來了，都是0，然後當成常數直接編譯到了代碼裡。
這個操作很符合直覺，1<<32把1唯一一個1移出去了，1<<-4應該等價於1>>4，也把1唯一一個1移出去了。
也就是說GCC算的是對的，而代碼運行時算的是“錯”的。
之所以說是“錯”的，是因為，代碼運行時的移位隱含了一個取模操作，移動的位數首先要對變量長度取模，再參與運算。
筆者因為這種不合常理的運算方式，和一個題死磕了四個鐘，一度懷疑是題目出錯了。
為了解決這個問題，我們引入SRM (safe right move)和SLM (safe left move)

unsigned SLM(unsigned x, int n) { //安全左移
    return (n >= 32) ? 0 : n < 0 ? SRM(x, -n) : x << n;
}
unsigned SRM(unsigned x, int n) { //安全右移
    return (n >= 32) ? 0 : n < 0 ? SLM(x, -n) : x >> n;
}

容易看出，這兩個函數特殊處理了n>=32和n<0的情況，讓移位操作更符合直覺。

Bitwise AND

將A和B的二進製表示的每一位進行與操作，只有兩個對應的二進制位都為1時，結果位才為1，否則為0.

1
2
3

A     = 001010
B     = 101100
A & B = 001000

Bitwise OR

將A和B的二進製表示的每一位進行或操作，只要兩個對應的二進制位有一個為1，結果位就為1，否則為0.

1
2
3

A     = 001010
B     = 101100
A | B = 101110

Bitwise Negation

將A的二進製表示每一位進行取反操作，如果對應的二進制位為0，結果位為1，否則為0.

1 2	A = 00000000000000000000000000001010 ~A = 11111111111111111111111111110101

Bitwise XOR

將A和B的二進製表示的每一位進行異或操作，如果對應的二進制位不同，結果位為1，否則為0.

1
2
3

A     = 001010
B     = 101100
A ^ B = 100110

A few Advanced Operations

Conventions for Binary Digits

筆者所在學校使用PTA評測代碼，PTA上對於二進制的描述是這樣的：例如從p開始的n位

首先是p，p從右開始數，為0,1,2,3···，也就是說，對於一個二進制串，p是31 30 29 28···3 2 1 0
然後是n，n指的是這些位：p,p-1...p+1-n

高級操作——把x從p開始的n位設置成1

unsigned set_bits(unsigned x, int p, int n) { //把從p開始的n位設置成1
    return x | SLM(~SLM(~0, n), p + 1 - n);
}
/**
 * 對於set_bits(0,4,3):
 *                              (~0)
 *  獲得一個32個1的東西              => 11111111111111111111111111111111
 *                              (~0) << n
 *  把上一個東西右邊搞出n個0         => 11111111111111111111111111111000
 *                              (~((~0) << n))
 *  把上一個東西0和1反過來           => 00000000000000000000000000000111
 *                              ((~((~0) << n)) << (p + 1 - n))
 *  把上一個東西右邊搞出(p+1-n)個0   => 00000000000000000000000000011100
 * 與x或運算即可設置1
 */

高級操作——獲取x從p開始的n位

1
2
3

unsigned get_bits(unsigned x, int p, int n) { //獲取從p開始的n位
    return SRM(x, p + 1 - n) & (~SLM(~0, n));
}

高級操作——把x從p開始的n位設置成0

unsigned unset_bits(unsigned x, int p, int n)  //把從p開始的n位設置成0
    return x & ~(set_bits(0, p, n));
}
//                            對於unset_bits(0,4,3)
//用set_bits(0,4,3)得到       00000000000000000000000000011100
//取反得到                    11111111111111111111111111100011
//與x與運算即可清0

高級操作——反轉x從p開始的n位

unsigned reverse_bits(unsigned x, int p, int n) { //反轉從p開始的n位
    return x ^ set_bits(0, p, n);
}
//                            reverse_bits(0,4,3)
//用set_bits(0,4,3)得到       00000000000000000000000000011100
//與x異或運算即可

高級操作——把x最後一個0刪掉

1
2
3

unsigned delete_last_0(unsigned x) { //把最後一個0刪掉
    return x & (x - 1);
}

Summary

把這一坨背過就好了

//位運算模板庫
//7個標準函數
// 安全左移
unsigned SLM            (unsigned x, int n)        { return (n >= 32) ? 0 : n < 0 ? SRM(x, -n) : x << n; }
// 安全右移
unsigned SRM            (unsigned x, int n)        { return (n >= 32) ? 0 : n < 0 ? SLM(x, -n) : x >> n; }
// 把從p開始的n位設置成1
unsigned set_bits       (unsigned x, int p, int n) { return x | SLM(~SLM(~0, n), p + 1 - n); }
// 獲取從p開始的n位
unsigned get_bits       (unsigned x, int p, int n) { return SRM(x, p + 1 - n) & (~SLM(~0, n)); }
// 把從p開始的n位設置成0
unsigned unset_bits     (unsigned x, int p, int n) { return x & ~(set_bits(0, p, n)); }
// 反轉從p開始的n位
unsigned reverse_bits   (unsigned x, int p, int n) { return x ^ set_bits(0, p, n); }
// 把最後一個0刪掉
unsigned delete_last_0  (unsigned x)               { return x & (x - 1); }

A few Simple Instances

Actual Problem 2-6-4

Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p(count from left to right, p, p-1…p+1-n, make sue p+1-n>=0) set to the rightmost n bits of y, leaving the other bits unchanged. We make sure that x∈[0,2^32−1] and y∈[0,2^32−1]. Note that 0 <= n && n <= 32 due to unsigned is 32-bit type.

題目拆分:
把x從p開始的n位清空
獲取y從n-1開始的n位，並挪到(p+1-n)的位置上
啪的一下就寫出來了啊，很快啊

unsigned setbits(unsigned x, unsigned y, int p, int n)
{
    return unset_bits(x, p, n) | (get_bits(y, n - 1, n) << (p + 1 - n));
}

Actual Problem 2-6-5

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

題目拆分:
模板
啪的一下就寫出來了啊，很快啊

unsigned invert(unsigned x, int pos, int n)
{
    return reverse_bits(x, pos, n);
}

筆者在提交此題的時候發現，這個題目的左移操作，視溢出為正常現象，所以補充兩個不安全的SRM和SLM，如果你不能通過題目，請嘗試換這兩個函數

unsigned SLM(unsigned x, int n) {
    return x << n;
}
unsigned SRM(unsigned x, int n) {
    return x >> n;
}

Actual Problem 2-6-6

Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions.

題目拆分:
獲取x從n-1開始的n位，並挪到32-n的位置上
獲取x從31開始的32-n位
啪的一下就寫出來了啊，很快啊

unsigned rightrot(unsigned x, int n)
{
    n %= 32;
    return (get_bits(x, n - 1, n) << (32 - n)) | get_bits(x, 31, 32 - n);
}

Simple Problem IV

給出兩個32位的整數N和M，以及兩個二進制位的位置i和j。寫一個方法來使得N中的第i到j位等於M（M會是N中從第i為開始到第j位的子串

Lintcode179 - Update Bits

唯一需要注意的就是這個題關於二進制位數的定義和PTA不大一樣
啪的一下就寫出來了啊，很快啊

int updateBits(int n, int m, int i, int j)
{
    return unset_bits(n,j,j-i+1)|(m<<i);
}

Simple Problem V

用 O(1) 時間檢測整數 n 是否是 2 的冪次。

Lintcode142 - O(1) Check Power of 2

啪的一下就寫出來了啊，很快啊

bool checkPowerOf2(int n)
{
    return (n>0)&&(delete_last_0(n)==0);
}

Simple Problem VI

計算在一個 32 位的整數的二進製表示中有多少個 1。

Lintcode365 - Count 1 in Binary

啪的一下就寫出來了啊，很快啊

int countOnes(int num)
{
    int ans=0;
    while(num)++ans,num=delete_last_0(num);
    return ans;
}

Simple Problem VII

如果要將整數n轉換為m，需要改變多少個bit位？

Lintcode181 - Flip Bits

首先異或，AB不一樣的位就變成1了，然後統計1的個數
啪的一下就寫出來了啊，很快啊

int countOnes(int num)
{
    int ans=0;
    while(num)++ans,num=delete_last_0(num);
    return ans;
}
int bitSwapRequired(int a, int b)
{
    return countOnes(a^b);
}

Authorization

References

¹. 火星大王的蒟蒻雲文章擅長位運算的王大同學 ↩