【练习】位运算思想

🎥 个人主页：Dikz12
🔥个人专栏：算法(Java)
📕格言：吾愚多不敏，而愿加学
欢迎大家👍点赞✍评论⭐收藏

1.判断字符串是否唯一

题目描述

讲解

代码实现

2.丢失的数字

题目描述

编辑讲解

代码实现

3.两整数之和

题目描述

讲解

代码实现

4.只出现一次的数字II

题目描述

讲解

代码实现

5.消失的两个数字

题目描述

讲解

代码实现

常见位运算总结

基础位运算

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

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

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

位图思想

异或运算规律

1.判断字符串是否唯一

题目描述

讲解

解法一：使用哈希表（只有小写字母可用数组模拟）

解法二：位运算（位图思想）.

利⽤「位图」的思想，每⼀个⽐特位代表⼀个字符，⼀个 int 类型的变量的 32 位⾜够;

表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ，

表⽰该字符出现过

代码实现

    public boolean isUnique(String astr) {
        if(astr.length() > 26) {
            return false;
        }
        int bitMap = 0;
        for(int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            if(((bitMap >> x) & 1) == 1) {
                return false;
            }
            //添加字符
            bitMap |= 1 << x;
        }
        return true;
    }

2.丢失的数字

题目描述

讲解

解法一：模拟哈希数组

解法二：高斯求和（推荐）

解法三：异或运算. （推荐）

把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」

运算的「消消乐」规律，最终的异或结果应该就是缺失的数.

代码实现

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

3.两整数之和

题目描述

讲解

解法一：return a+b;（开个玩笑） .

这里要求不使用运算符"+"、"-"，所以，也就只能使用位运算了.

解法二：位运算.

异或 ^ 运算本质是：⽆进位加法
按位与 & 操作能够得到进位
然后⼀直循环进⾏，直到进位变成 0 为⽌

代码实现

    public int getSum(int a, int b) {
        while(b != 0) {
            int ret = a ^ b;
            int carry = (a & b) << 1;
            a = ret;
            b = carry;
        }
        return a;
    }

4.只出现一次的数字II

题目描述

讲解

根据所有数的某⼀个⽐特位的总和 %3 的结果，快速定位到 ret 的⼀个⽐特位上的值是 0 还是 1
通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来.

代码实现

    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            //统计比特位个数
            int sum = 0;
            for(int x : nums) {
                if(((x >> i) & 1) == 1) {
                    sum++;
                }
            }
            if(sum % 3 != 0) {
                //修改比特位
                ret |= 1 << i;
            }
        }
        return ret;
    }

5.消失的两个数字

题目描述

讲解

将所有的数异或在一起 => 丢失的数字（ret = a^b）
找到 ret中，比特位 x 为 1 的那一位
根据 x位的不同，划分成两类异或.

代码实现

    public int[] missingTwo(int[] nums) {
        // 1.将所有的数异或在一起
        int tmp = 0;
        for(int i = 0; i < nums.length; i++) {
            tmp ^= nums[i];
        }
        for(int i = 1; i <= nums.length + 2; i++) {
            tmp ^= i;
        }
        //2.找出tmp中，比特位为一的那一位 tmp = a ^ b
        int index = 0;
        while(true) {
            if(((tmp >> index) & 1) == 1) {
                break;
            }else{
               index++;
            } 
        }
        // 3.根据index位不同,分为两类异或
        int[] ret = new int[2];
        for(int x : nums) {
            if(((x >> index) & 1) == 1) {
                ret[1] ^= x;
            }else{
                ret[0] ^= x;
            }
        }
        for(int i = 1; i <= nums.length + 2; i++) {
               if(((i >> index) & 1) == 1) {
                ret[1] ^= i;
            }else{
                ret[0] ^= i;
            }
        }
        return ret;
    }