一文讀懂位運算

• 2021 年 9 月 26 日
• 筆記

概述

在電腦程式中所有的數都是以二進位形式存儲的。位運算就是直接對整數在二進位進行計算操作。作為一名程式設計師掌握位運算的基本使用是很重要的，而對於演算法程式設計師來說，位運算的靈活使用能夠更靈活高效的解決很多問題。

位運算都有哪些

運算符邏輯

按為與（&）

參加運算的兩個數按二進位進行與運算。

0&0=0
0&1=0
1&1=1

用途：

清零

任何數與0做與運算結果都為0。

取指定位

比如要取一個數的低4位，則只需使用該數與（0000 1111）做與運行，結果就是這個數的低4位的值。

奇偶判斷

只要二進位的末尾為0則是偶數，為1則為奇數。因此可用 (x&1)==0判斷是否是偶數。

按位或（|）

參加運算的兩個數按二進位進行或運算。

0|0=0
0|1=1
1|1=1

用途：

將某位設置為1

如X=0101，需要將第2位設置為1，結果變為0111，則只需和（0010）進行或運算，0101|0010=0111。

按位異或（^）

參加運算的兩個數按二進位進行異或運算。

0^0=0
0^1=1
1^1=0

用途：

翻轉指定位

如要將X=0101 1010的低4位翻轉為0101，則只需和Y=0000 1111進行異或運行，X^Y=0101 0101 。

交換兩數值

如X=0101，Y=0100，需要將X和Y的值進行交換。

x ^= y; // x= 0101 ^ 0100  = 0001
y ^= x; // y = 0100 ^ 0001 = 0101
x ^= y; // x = 0001 ^ 0101 = 0100

按位取反（~）

參加運算的1個數據各位值0變1,1變0.

~0101=1010

用途：

取反運算和用於快速獲得某個特定值，如獲取一個最低位為0其他位為1的數，則對1進行取反即可，~1。

左移運算符（<<）

參與運算的1個數據各位左移，高位丟棄，低位補0。

0101 << 1 = 1010

如果左移的數最高位不等於1，則相當於乘2。

右移運算符（>>）

參與運算的1個數據各位右移，如果該數為正則高位補0，反之補1，低位丟棄。

0101 >> 1 = 0010

某數進行右移運算相當於除以2。

無符號右移運算符（>>>）

又稱邏輯右移，不管正負，高位補0。

0101>>>1=0010

如負數-5進行右移操作，結果如下。(-5的二進位表示為11111111111111111111111111111011)

11111111111111111111111111111011>>>1=01111111111111111111111111111101

註：負數的二進位表示形式為補碼。

有哪些騷操作

技巧一

x & (x – 1) 用於消去x最後一位的1

應用：檢測整數x是否是2的次冪

思路：2的次冪滿足以下條件：

1. 大於0
2. 只有1個位是1

則x & (x – 1)的結果如果等於0則表示x是2的次冪。

技巧二

a ^ b ^ b = a

一個數據集合中，只有1個數字出現1次，其他數字都出現兩次，找出這個數。

思路：只需要將所有數據進行異或運算，結果就是這個數。

一個數據集合中，只有2個數字出現過1次，其他數字都出現過兩次，找出這兩個數。

思路：假設這兩個數是X,Y,所有數字進行異或的結果就是X^Y，因為異或運算邏輯是相同為0，不同為1，則找出這個結果的二進位中等於1的位置，然後將所有數字按照該位是否為1分成兩部分，那麼X和Y會被分開，然後分別做異或運算，結果便是X和Y.

小結

位運算在各大互聯網公司的面經中經常會出現，各種演算法題中也高頻使用，希望本文能讓你對位運算有一個初步的認識。

來都來了，點個贊再走啦~