leetcode算法总结之位运算

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算法总结之位运算

定义

位运算就是数据的0,1表示形式进行的整数(32位))计算。包括除了boolean以外的基本类型均可以进行位运算（其中包括一次类型转换）。位运算特点是：效率高(中间转换环节省略)，耗费CPU资源较少。

常用操作

• 或（|）
• 与（&）
• 非（|）
• << (无符号左移） <<< (有符号左移)
• >> (无符号右移动) >>> (有符号右移)
• ^ 亦或操作

常用公式

• 运算后为数字本身
  
  n ^ 0 = n ; n | 0 = n； n & 1=n
• 运算后为数字的取反
  
  n ^ 1 = ~n
• 运算后为0
  
  n & 0 = 0;n ^ n = 0;n & n =n;n | n = n
• 运算后为1
  
  n | 1 = 1

使用场景以及部分问题解决方案

• 判断数据奇偶性(其实是判断数字二进制是否为1)
  1. 奇数 n & 1 == 1
  2. 偶数 n & 1 == 0
• 交换数字
  A = A^B
  B = A^B
  A = A^B
• 数组中无重复数字
• 相反数
  (~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槽点计算（除留余数法）
2. 后期补充.....

leetcode 相关题目

在这里插入图片描述

1. 汉明距离（计算两数字比特位置不同的个数）

   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. 数组中唯一的数字

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

3. 翻转32位数字

   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的个数

   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虽好，请不要贪杯呦。

关注我（公众号中包括多线程，分布式，高并发等知识点梳理）

微信公众号：看相声也要敲代码