計算機中的數在内存中都是以二進制形式進行存儲的，用位操作就是直接對整數在内存中的二進制位進行操作，因此其執行效率非常高，在程序中盡量使用位運算進行操作，這會大大提高程序的性能。位操作是各大互聯網公司面試經常會問的一類問題。

位操作符

& 與運算 兩個位都是 1 時，結果才為 1，否則為 0，如：

| 或運算 兩個位都是 0 時，結果才為 0，否則為 1，如：

^ 異或運算，兩個位相同則為 0，不同則為 1，如：

~ 取反運算，0 則變為 1，1 則變為 0，如：

<< 左移運算，向左進行移位操作，高位丢棄，低位補 0，如：

>> 右移運算，向右進行移位操作，對無符号數，高位補 0，對于有符号數，高位補符号位，如：

常見位運算問題

1. 位操作實現乘除法

數 a 向右移一位，相當于将 a 除以 2；數 a 向左移一位，相當于将 a 乘以 2

---

2. 位操作交貨兩數

位操作交換兩數可以不需要第三個臨時變量，雖然普通操作也可以做到，但是沒有其效率高

位與操作解釋：

• 第一步：a ^= b ---> a = (a^b);
• 第二步：b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a
• 第三步：a ^= b ---> a = (a^b)^a = (a^a)^b = b

---

3. 位操作判斷奇偶數

隻要根據數的最後一位是 0 還是 1 來決定即可，為 0 就是偶數，為 1 就是奇數。

---

4. 位操作交換符号

交換符号将正數變成負數，負數變成正數

整數取反加 1，正好變成其對應的負數（補碼表示）；負數取反加一，則變為其原碼，即正數。

---

5. 位操作求絕對值

整數的絕對值是其本身，負數的絕對值正好可以對其進行取反加一求得，即我們首先判斷其符号位（整數右移 31 位得到 0，負數右移 31 位得到 -1,即 0xffffffff），然後根據符号進行相應的操作

上面的操作可以進行優化，可以将 i == 0 的條件判斷語句去掉。我們都知道符号位i隻有兩種情況，即 i = 0 為正，i = -1為負。對于任何數與 0 異或都會保持不變，與 -1 即 0xffffffff 進行異或就相當于對此數進行取反,因此可以将上面三目元算符轉換為 ((a^i)-i)，即整數時 a 與 0 異或得到本身，再減去 0，負數時與 0xffffffff 異或将 a 進行取反，然後在加上 1，即減去 i(i =-1)

---

6. 位操作進行高低位交換

給定一個 16 位的無符号整數，将其高 8 位與低 8 位進行交換，求出交換後的值，如：

從上面移位操作我們可以知道，隻要将無符号數 a >> 8 即可得到其高 8 位移到低 8 位，高位補 0；将 a << 8 即可将 低 8 位移到高 8 位，低 8 位補 0，然後将 a >> 8 和 a << 8 進行或操作既可求得交換後的結果。

---

7. 位操作進行二進制逆序

将無符号數的二進制表示進行逆序，求取逆序後的結果，如：

在字符串逆序過程中，可以從字符串的首尾開始，依次交換兩端的數據。在二進制中使用位的高低位交換會更方便進行處理，這裡我們分組進行多步處理。

• 第一步：以每 2 位為一組，組内進行高低位交換

• 第二步：在上面的基礎上，以每 4 位為 1 組，組内高低位進行交換

• 第三步：以每 8 位為一組，組内高低位進行交換

• 第四步：以每 16 位為一組，組内高低位進行交換

對于上面的第一步，依次以 2 位作為一組，再進行組内高低位交換，這樣處理起來比較繁瑣，下面介紹另外一種方法進行處理。先分别取原數 10000110 11011000 的奇數位和偶數位，将空餘位用 0 填充：

再将奇數位右移一位，偶數位左移一位，此時将兩個數據相或即可以達到奇偶位上數據交換的效果：

上面的方法用位操作可以表示為：

• 取 a 的奇數位并用 0 進行填充可以表示為：a & 0xAAAA
• 取 a 的偶數為并用 0 進行填充可以表示為: a & 0x5555 因此，上面的第一步可以表示為：
• a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
• 同理，可以得到其第二、三和四步為：
• a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
• a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
• a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
• 因此整個操作為：

---

8. 位操作統計二進制中 1 的個數

統計二進制 1 的個數可以分别獲取每個二進制位數，然後再統計其 1 的個數，此方法效率比較低。這裡介紹另外一種高效的方法，同樣以 34520 為例，我們計算其 a &= (a-1) 的結果：

• 第一次：計算前：1000 0110 1101 1000 計算後：1000 0110 1101 0000
• 第二次：計算前：1000 0110 1101 0000 計算後：1000 0110 1100 0000
• 第二次：計算前：1000 0110 1100 0000 計算後：1000 0110 1000 0000 我們發現，每計算一次二進制中就少了一個 1，則我們可以通過下面方法去統計：

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部