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)
- 奇数 n & 1 == 1
- 偶数 n & 1 == 0
- 交换数字
A = A^B
B = A^B
A = A^B - 数组中无重复数字
- 相反数
(~N+1) - 乘、除、取模
- 除：n / (2^i) 等价于 n>>i
- 乘：n * (2^i) 等价于 n<<i 其中^代表幂
- 取模：a % (2^n) 等价于 a & (2^n - 1)
- math.pow(m,n),m的n次方
Java中使用痕迹
- hashmap等集合中中hash槽点计算（除留余数法）
- 后期补充.....
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虽好，请不要贪杯呦。
关注我（公众号中包括多线程，分布式，高并发等知识点梳理）
微信公众号：看相声也要敲代码
