leetcode算法總結 —— 位運算

文章目錄

• • 異或
  • • a ^ b = n
    • a ^ a = 0； a ^ 0 = a
  • 與運算
  • • a & b = n
    • (n & 1) == 0
    • n = n & (n - 1)
    • n = n & (-n)
    • (a&b)<<1
  • 左右移位

異或

二進制中異或，0^0 = 0 , 0異或1 和1異或1都為1

a ^ b = n

a = 8 的二進制是 1000，b = 13 的二進制是 1101。

得到 n = 0101

1. 在n的二進制中：ab不同的位為1，相同的位為0
   • 1. 漢明距離
2. a^b----還相當于 二進制的無進位相加，得到0101

a ^ a = 0； a ^ 0 = a

• 1. 隻出現一次的數字

與運算

二進制位對應& 則1&1為1，1&0，0&0都為0

a & b = n

在n的二進制中：ab位都是1的時候n對應的位為1，其餘的位為0

(n & 1) == 0

判斷最後一位是0還是1

(n & 1) == 0說明n是偶數

(n & 1) == 1則n是奇數

• 1. Pow(x, n)

n = n & (n - 1)

這個操作是算法中常見的，作用是去掉數字 n 的二進制表示中的最後一個 1。

統計整數n二進制中1的個數

while(n != 0) {
        n = n & (n - 1); //消除n的二進制的最後一個1
        count++;
    }
           

• 1. 位1的個數
• 1. 比特位計數(dp)
• 1. 2的幂（2的n次方，則說明這個數二進制隻有第一位是1，反之也成立）
• 1. 4的幂（先判斷是否是2的幂，然後判斷奇數位是1）

n = n & (-n)

類似于上面的但是他是隻保留了n的二進制中的最後一個1，比如0010，前面的1都去掉，隻保留最後一個1

• 1. 隻出現一次的數字 III

(a&b)<<1

求的是a+b的二進制進位數，得到10000

• 1. 兩整數之和
• 劍指 Offer 65. 不用加減乘除做加法

左右移位

位運算速度要大于乘除法

n>>1 是n/2

n<<1是n*2