算法篇之位运算

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

基本位运算

1. <<：左移1位
2. >>：右移1位
3. ~：按位取反
4. &：有0就是0/全1才是1
5. |：有1就是1
6. ^：相同为0，相异为1 / 无进位相加
   

给一个数n，确定他的二进制中的第x位是0还是1

（n>>x)&1 前面的二进制&0全部变成0，所以决定答案是0还是1在于 &1的是0还是1.

将一个数n的二进制表示的第x位修改为1

n | (1<<x) 利用 | 的有1就是1的特性，其他二进制位 | 上0，保持不变

将一个数n的二进制表示的第x位修改为0

n & (~(1<<x）） 要想将x位变成0，就要 & 上0，有0就是0；而其他位要保持不变，只要 & 上1，原本是1的还是1，原本是0的还是0.

提取出一个数n二进制表示的最右侧的1

n & -n

-n意味着将 最右侧这个1 的左边区域都取反

那么右侧区域原本是1的变0，0变1 经过 & 全变成0了， 1右侧本来就全是0.

干掉一个数n二进制表示的最右侧的1

n & (n - 1)

n-1 意味着将 最右侧这个1 的右边区域全部取反，包括这个1

右侧区域由0变成1， 经过& 还是0，最右侧的1变成0，经过&，变成0

1的个数

题目链接：1的个数

算法思路：

32位二进制，遍历每一位，通过(n >> i) & 1统计有多少位为1.

代码：

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int result = 0;// 遍历每一位for(int i = 0; i < 32; i++) {if(((n >> i) & 1) == 1) {result++;}}return result;}
}

汉明距离

题目链接：汉明距离

算法思路：

x，y两个数进行按位异或^，得到tmp，在计算tmp二进制中有多少个1

代码：

class Solution {public int hammingDistance(int x, int y) {int tmp = x ^ y; // 相同为0，相异为1// 计算tmp中有多少个1int result = 0;for(int i = 0; i < 32; i++) {if(((tmp >> i) & 1) == 1 ) {result++;}}return result;}
}

异或的运算规律

1. a ^ 0 = a
2. a ^ a = 0
3. a ^ b ^ c = a ^ (b ^ c)
   

只出现一次的数

题目链接：只出现一次的数

算法思路：

利用按位异或的特性，相同为0，相异为1.就能把所有的重复的数字消掉，只剩下不重复的数。

代码：

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

只出现一次的数Ⅲ

题目链接：只出现一次的数Ⅲ

算法思路：

1. 将所有数^{，得到的数(tmp)就是那两个不同的数}的结果，因为相同的数进行^，就会被消掉
2. 计算tmp二进制第一位出现1的位置(index)，说明一个数在index为0，另一个数在index位置为1
3. 这样我们就可以把数组分为两类
   1. 在index位置为1的数
   2. 在index位置为0的数
4. 在遍历数组，与index进行&操作，结果为0的分为一组，结果非0的分为一组
5. 最后在组内进行^操作
   

代码：

class Solution {public int[] singleNumber(int[] nums) {// 1. 将所有数^,得到的数就是那两个不同的数的^// 因为相同的数进行^，就会被消掉int tmp = nums[0];int n = nums.length;for(int i = 1; i < n; i++) {tmp ^= nums[i];}// 2. 计算tmp二进制第一位出现1的位置(index)，说明一个数在index为0，另一个数在index位置为1int index = tmp & (-tmp);// 3. 这样我们就可以把数组分为两类，1. 在index位置为1的数。2. 在index位置为0的数int num1 = 0, num2 = 0;for(int num : nums) {if((num & index) == 0) {num1 ^= num;}else {num2 ^= num;}}return new int[]{num1, num2};}
}

位图

一个int类型有32位，每一位可以取0或1, 0表示不存在，1表示存在
如果第一次出现可以置为1（即 将n的第x位置为1，使用n | (1<<x) )；
判断是否已经存在（即 判断n的第x位是0还是1，使用（n>>x) & 1)

判断字符是否唯一

题目链接：判断字符是否唯一

算法思路：

利⽤「位图」的思想，每⼀个「⽐特位」代表⼀个「字符，⼀个 int 类型的变量的 32 位⾜够 表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ， 表⽰该字符出现过。 那么我们就可以⽤⼀个「整数」来充当「哈希表」。

代码：

class Solution {public boolean isUnique(String astr) {// 利用鸽巢原理做优化if(astr.length() > 26) {return false;}int bitMap = 0;for(int i = 0; i < astr.length(); i++) {int index = astr.charAt(i) - 'a';if(((bitMap >> index) & 1 )== 1) {return false;}bitMap |= (1 << index);}return true;}
}

这篇关于算法篇之位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---