[LeetCode] 一些位操作类的算法

本文主要是介绍[LeetCode] 一些位操作类的算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 出处

找列表中唯一出现一次的元素
汉明重量/数1出现的次数
汉明距离

2. 说明

2.1 基本规则

从二进制数开始分析有一些有趣的基本操作：

• 乘2: 右移动1位
• 除2: 左移1位
• 0 & 0 = 0， 1 & 0 = 0， 1 & 1 = 0，这个用来处理数1出现的位数，后边会写
• 0 ^ 0 = 0, 1 ^ 0 = 1, 1 ^ 1 = 0 ，只要位不相同就为1，这里用来数唯一出现的数字
• java中的Integer是32位有符号整数，因此100000000…..0 = -2147483648 即 Integer.MIN_VALUE
• Integer 的1000000….0 继续左移动以为则为0。
• Integer.MIN_VALUE = 100000….00 而 Integer.MAX_VALUE = 0111111….111 因此快速获得 Integer.MAX_VALUE = (1 << 31) -1

2.2 技巧

2.2.1 唯一出现一次的元素

因为异或操作的特性，任何数异或0都是自己，自己异或自己就是0。因此对一个列表用0异或第一个元素，然后逐次向下异或即可得到唯一出现的元素了。

class Solution {public int singleNumber(int[] nums) {if(nums.length==1) {return nums[0];} else {int initNum = 0;for(int num: nums) {initNum ^= num;}return initNum;}}
}

2.2.2 汉明重量

通过1作为游标进行与运算，当1出现的位置与游标重合时，与的结果不为0。

public class HammingWeight {public int hammingWeight(long n) {int tag = 1;int count = 0;while (tag != 0) {//由于int类型的函数是32位因此要循环32次if ((n & tag) != 0)count++;tag = tag << 1;}return count;}
}

2.2.3 汉明距离

找出不相同的位数量，在2.2.2 的基础上，将两数做一次异或运算就变成了2.2.2的题目了～～～

public class HammingDistance {public int hammingDistance(int x, int y) {int dif = (x ^ y);int tag = 1;int count = 0;while (tag != 0) {//由于int类型的函数是32位因此要循环32次if ((dif & tag) != 0)count++;tag = tag << 1;}return count;}
}

2.2.4 其它技巧

• 判断是否是偶数: n & 1 == 1
• 不用临时变量交换两个数的位置: a ^= b; b ^= a; a ^= b;
• 判断符号是否相同: (x ^ y) >= 0;
• -

这篇关于[LeetCode] 一些位操作类的算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---