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

àì夳堔傛蜴生んèń 2022-05-17 07:22 138阅读 0赞

# 1. 出处 #

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

# 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;
 *  \-

[Link 1]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
[1]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/26/others/64/
[Link 2]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/26/others/65/