First learn computer science and all the theory. Next develop a programming style. Then forget all that and just hack.
<p align="right">- George Carrette</p>

leetcode算法總結(jié)之位運算

定義

位運算就是數(shù)據(jù)的0,1表示形式進行的整數(shù)(32位))計算。包括除了boolean以外的基本類型均可以進行位運算（其中包括一次類型轉(zhuǎn)換）。位運算特點是：效率高(中間轉(zhuǎn)換環(huán)節(jié)省略)，耗費CPU資源較少。

常用操作

• 或（|）
• 與（&）
• 非（|）
• << (無符號左移） <<< (有符號左移)
• >> (無符號右移動) >>> (有符號右移)
• ^ 亦或操作

常用公式

• 運算后為數(shù)字本身
  
  n ^ 0 = n ; n | 0 = n； n & 1=n
• 運算后為數(shù)字的取反
  
  n ^ 1 = ~n
• 運算后為0
  
  n & 0 = 0;n ^ n = 0;n & n =n;n | n = n
• 運算后為1
  
  n | 1 = 1

使用場景以及部分問題解決方案

• 判斷數(shù)據(jù)奇偶性(其實是判斷數(shù)字二進制是否為1)
  1. 奇數(shù) n & 1 == 1
  2. 偶數(shù) n & 1 == 0
• 交換數(shù)字
  A = A^B
  B = A^B
  A = A^B
• 數(shù)組中無重復(fù)數(shù)字
• 相反數(shù)
  (~N+1)
• 乘、除、取模
  1. 除：n / (2^i) 等價于 n>>i
  2. 乘：n * (2^i) 等價于 n<<i 其中^代表冪
  3. 取模：a % (2^n) 等價于 a & (2^n - 1)
• math.pow(m,n),m的n次方

Java中使用痕跡

1. hashmap等集合中中hash槽點計算（除留余數(shù)法）
2. 后期補充.....

leetcode 相關(guān)題目

在這里插入圖片描述

1. 漢明距離（計算兩數(shù)字比特位置不同的個數(shù)）

   public int hammingDistance(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while(z != 0){
            count += z & 1;
            z >>= 1;
        }
        return count;
    }

2. 數(shù)組中唯一的數(shù)字

   public int singleNumber(int[] nums) {
        int ans = nums[0];
        for(int i = 1; i < nums.length; i++){
            ans ^= nums[i];
        }
        return ans;
    }

3. 翻轉(zhuǎn)32位數(shù)字

   public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans <<= 1;
            ans += n & 1;
            n >>= 1;
        }
        return ans;
    }

4. 從0~n二進制中1的個數(shù)

   public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        bits[0] = 0;
        for(int i = 1; i <= num; i++){
            bits[i] = (i & 1) == 1 ? bits[i-1] + 1 : bits[i>>1];
        }
        return bits;
    }

當自己封裝插件或框架的時候，當進行加、減、乘、除或進行奇和偶判斷的時候就可以使用bit運算，但是bit雖好，請不要貪杯呦。

關(guān)注我（公眾號中包括多線程，分布式，高并發(fā)等知識點梳理）

微信公眾號：看相聲也要敲代碼