特别注意：使用按位操作符时要注意(图)数-老王博客

注意

特别注意：使用位运算符时，请注意等式 (==) 和不等式 (!=) 优先于位运算符！！！！

这意味着按位运算符的优先级很小，所以在使用按位运算符时，最好加上括号（）

重要提示

我只是跳过了基本操作。以下是我认为必须掌握的技能：（注意我剪掉了一些不常见的技能，剩下的就是我认为应该能做到的）

使用 x & 1 == 1 来确定奇偶校验。（注意，有些编辑器的底层会自动优化使用 % 确定奇偶数的代码为按位运算。）不使用第三个数，而是交换两个数。x = x^y，y = x^y，x = x^y。（早年喜欢问，现在如果再问，大家会觉得很低落）两个相同的数异或的结果是0，一个数和0异或的结果就是自己。（对于求数四位二进制计数器有几个工作状态，异或往往还有其他用途。） x & (x – 1) ，可以把最右边的 1 设置为 0。（这个技巧可以用来检测 2 的幂，或者检测整数二进制中的 1，或者有人问你从一个数字到另一个数字有多少位变化，都是）i+（~i）=-1，将 i 取反，然后与 i 相加，相当于将所有二进制位设置为 1，十进制结果为 -1。对于 int32，使用 n >> 31 获得 n 的符号。并且可以通过 (n ^ (n >> 3< @1)) – (n >> 31)) 得到绝对值。 (n 为正数，n >> 31 的所有位都相等为0。如果n为负数，则n>>31的所有位都等于1，其值等于-1）使用(x^y)>=0判断符号是否相同。(如果两个数都是正数，二进制的第一位是0，x^y=0；如果两个数都是负数，二进制的第一位是1；x^y=0 如果两个数的符号相反，二进制的第一位相反，x^y=1。0也有例外，^同为0，不同的是1）”XOR”是无进位加法，说白了，就是切断了进位。例如，01^01=00。“与”可以用来获得进位，例如 01&01=01 ，然后将结果左移一位得到进位结果。使用掩码遍历二进制位

这种方法相对简单。我们遍历数字的 32 位。如果某位为 1，则将计数器加一。

我们使用位掩码来检查数字的第 ith 位。一开始，掩码 m=1 因为 1 的二进制表示是

0000 0000 0000 0000 0000 0000 0000 00010000 0000 0000 0000 0000 0000 0000 0001

0000 0000 0000 0000 0000 0000 0000 0001

显然，用掩码 11 对任何数字进行逻辑与运算将得到该数字的最低有效位。检查下一位时，我们将掩码左移一位。

0000 0000 0000 0000 0000 0000 0000 00100000 0000 0000 0000 0000 0000 0000 0010

0000 0000 0000 0000 0000 0000 0000 0010

重复这个过程，我们可以依次遍历所有位。

爪哇

public int hammingWeight(int n) {
    int bits = 0; // 用来储存 1 的个数
    int mask = 1;  // 掩码，从最低位开始
    for (int i = 0; i < 32; i++) {
        // 注意这里是不等于0，而不是等于1，因为我们的位数是不断在变化的，可能等于2、4、8...
        // 使用按位操作符时要注意，相等（==）与不相等（!=）的优先级在按位运算符之上！！！！
        // 使用按位运算符时，最好加上括号()
        if ((n & mask) != 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}

注意：这里判断n&mask的时候，不要写错(n&mask)==1，因为这里是比较十进制数。（我之前写过这个，为了记录......）

无符号右移迭代二进制位

一点一点的判断

根据AND运算的定义，设置二进制数n，则有：

根据以上特点，考虑如下循环判断：

判断n的最右边是否为1，根据结果计数。将 n 右移一位（此题要求将数 n 视为无符号数，因此使用无符号右移操作）。

算法流程：

初始化数量统计变量res = 0。循环逐位判断：当n = 0时跳出。 res += n & 1：如果n&1=1n&1=1，则统计res加1。n >>= 1：将二进制数 n 无符号右移一位（Java 中无符号右移为“>>>”）。返回统计值 res。

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;  // 遍历
            n >>>= 1;  // 无符号右移
        }
        return res;
    }
}

反转最后一个 1

对于具体情况，比如只有1对我们有用的时候，我们不需要遍历每一位，可以优化之前的算法。

我们不是检查数字的每个数字，而是不断反转数字的最后一个并将答案加一。当数字变为0时，我们知道它没有1位，此时返回答案。

注意：这里我们讨论的是最后一个 1，而不是最后一个 1，它可以是任何位。

这里的关键思想是，对于任何数字 n，将 n 与 n - 1 进行与运算会将最后一位变为 0。为什么？考虑 n 和 n - 1 的二进制表示。

使用 n&(n−1)n&(n−1)

(n−1)(n−1) 解析：二进制数n最右边的1变成0，这个1右边的0变成1。

n&(n−1)n&(n−1) 解析：二进制数n最右边的1变成0，其余不变。

Image 1. ANDing n 和 n-1 会将最低的 1 变成 0

在二进制表示中，数字 n 中的最低有效 1 始终对应于 n - 1 中的 0。因此，将 n 与 n - 1 进行与运算总是将 n 的最低有效 1 变为 0，而其他位保持不变。

例如以下两对数字：

肯定有人又看了，我们以11为例：（注意最后的1变成0的过程）

有了这个小技巧，代码就变得很简单了。

爪哇

public int hammingWeight(int n) {
    int sum = 0;  // 用来存放 1 的个数
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

Java内建函数：1的个数

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

XOR 取消（XOR 操作的特性）

我们先来看看异或的数学性质（数学中异或的符号是⊕⊕）：

XOR 操作具有以下三个属性。

如果任意一个数与0异或，结果还是原来的数，即a⊕0=aa⊕0=a。任意数与自身异或，结果为0，即a⊕a=0a⊕a=0。异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b ⊕(a⊕a)=b⊕0=b。

假设数组中有2m+1个数字，m个数字中的每一个出现两次，每个数字出现一次。设 a1a1 , a2a2 , ... , amam 是出现两次的 m 个数字，而 am+1am+1 是出现一次的数字。根据性质 3，数组中所有元素的异或运算结果总是可以写成以下形式：

(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1(a1⊕a1)⊕(a2⊕a2) ⊕⋯⊕(am⊕am)⊕am+1

根据性质 2 和 1，可将上式简化计算得到如下结果：

0⊕0⊕⋯⊕0⊕am+1=am+10⊕0⊕⋯⊕0⊕am+1=am+1

因此，数组中所有元素的异或运算的结果是数组中只出现一次的数字。

举个例子：

假设我们有三个数字 [21,21,26]，如下所示：

回想一下，我们可以使用“异或”的原因是我们实际上完成了一个在同一个位上清除 2 个 1 的过程。如果是这样的话，上图可能看起来很简单（下图应该是 26^21)：

爪哇

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

实例位数 1

编写一个函数，将无符号整数（以二进制字符串的形式）作为输入，并返回其二进制表达式中“1”位数（也称为汉明权重）。

暗示：

先进的：

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

暗示：

输入必须是长度为 32 的二进制字符串。

答案方法一：循环和位移

算法

这种方法相对简单。我们遍历数字的 32 位。如果某位为 1，则将计数器加一。

我们使用位掩码来检查数字的第 ith 位。一开始，掩码 m=1 因为 1 的二进制表示是

0000 0000 0000 0000 0000 0000 0000 00010000 0000 0000 0000 0000 0000 0000 0001

0000 0000 0000 0000 0000 0000 0000 0001

显然，用掩码 11 对任何数字进行逻辑与运算将得到该数字的最低有效位。检查下一位时，我们将掩码左移一位。

0000 0000 0000 0000 0000 0000 0000 00100000 0000 0000 0000 0000 0000 0000 0010

0000 0000 0000 0000 0000 0000 0000 0010

并重复该过程。

爪哇

public int hammingWeight(int n) {
    int bits = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}

复杂性分析

一点一点的判断

根据AND运算的定义，设置二进制数n，则有：

根据以上特点，考虑如下循环判断：

判断n的最右边是否为1，根据结果计数。将 n 右移一位（此题要求将数 n 视为无符号数，因此使用无符号右移操作）。

算法流程：

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;  // 遍历
            n >>>= 1;  // 无符号右移
        }
        return res;
    }
}

方法二：位操作小技巧

算法

我们可以优化之前的算法。我们不是检查数字的每个数字，而是不断反转数字的最后一个并将答案加一。当数字变为0时，我们知道它没有1位，此时返回答案。

这里的关键思想是，对于任何数字 n，将 n 与 n - 1 进行与运算会将最后一位变为 0。为什么？考虑 n 和 n - 1 的二进制表示。

使用 n&(n−1)n&(n−1)

(n−1)(n−1) 解析：二进制数n最右边的1变成0，这个1右边的0变成1。

n&(n−1)n&(n−1) 解析：二进制数n最右边的1变成0，其余不变。

Image 1. ANDing n 和 n-1 会将最低的 1 变成 0

在二进制表示中，数字 n 中的最低有效 1 始终对应于 n - 1 中的 0。因此，将 n 与 n - 1 进行与运算总是将 n 的最低有效 1 变为 0，而其他位保持不变。

有了这个小技巧，代码就变得很简单了。

爪哇

public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

复杂性分析

只出现一次的数字

给定一个非空整数数组，每个元素出现两次，除了一个只出现一次。找到只出现一次的元素。

操作说明：

您的算法应该具有线性时间复杂度。你可以在不使用额外空间的情况下做到这一点吗？

示例 1：

输入: [2,2,1]
输出: 1

示例 2：

输入: [4,1,2,1,2]
输出: 4

回答

方法一：位运算

如果不考虑时间复杂度和空间复杂度的约束，这个问题的解法很多，可能的解法如下。

上述所有三个解决方案都需要 O(n)O(n) 的额外空间，其中 n 是数组的长度。

我们如何才能实现线性时间复杂度和恒定空间复杂度？

答案是使用按位运算。对于这个问题，使用 XOR 运算符 ⊕⊕ 。XOR 操作具有以下三个属性。

如果任意一个数与0异或四位二进制计数器有几个工作状态，结果还是原来的数，即a⊕0=aa⊕0=a。

任意数与自身异或，结果为0，即a⊕a=0a⊕a=0。

异或运算满足交换律和结合律，即

a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b

(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1(a1⊕a1)⊕(a2⊕a2) ⊕⋯⊕(am⊕am)⊕am+1

根据性质 2 和 1，可将上式简化计算得到如下结果：

0⊕0⊕⋯⊕0⊕am+1=am+10⊕0⊕⋯⊕0⊕am+1=am+1

因此，数组中所有元素的异或运算的结果是数组中只出现一次的数字。

爪哇

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

复杂性分析

剑指的是Offer 56 - II。数组 II 中数字出现的次数

在数组 nums 中，所有数字都出现了 3 次，除了只出现一次的数字。请找出只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

位运算答案

// 虽然位运算很麻烦，但是我也得试试啊
class Solution {
    public int singleNumber(int[] nums) {
        // 位运算有点麻烦
        // 把所有数的二进制位相加，对每一位取余3，那么剩下来的就是我们需要找的数字了
        int[] counts = new int[32]; // 用来存储答案数字的32位二进制
        
        // 遍历数组中的所有数，将他们的二进制位相加，存起来
        for(int num : nums) {
            // 从0到31，从低位到高位
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        // 从高位开始，把每一位二进制 % 3
        int res = 0;    // 结果答案
        for(int i = 31; i >= 0; i--) {
            // 先移位再加个位，就如 sum += sum * 10 + 个位
            res <<= 1;
            res |= counts[i] % 3;
        }
        return res;
    }
}

哈希表答案

class Solution {
    public int singleNumber(int[] nums) {
        // 位运算有点麻烦
        // 哈希表
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            
            int count = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], count);
        }
        for (int i = 0; i < nums.length; i++) {
            
            int count = map.getOrDefault(nums[i], 0);
            if (count == 1) {
                return nums[i];
            }
        }
        return 0;
    }
}

两个数之和

问题 268：不使用运算符 + 和 - 计算两个整数 a 和 b 的和。

回答

大多数位运算题都有一些特殊的技巧。只要你能掌握这些技巧，并将它们组合起来，就可以解决一系列问题。很多人说那些技能是出乎意料的，我想是因为没有认真的学习和记忆。你要相信，起初基本上每个人都做不到，但后来他们通过努力学会了记住，而你没有因为不努力而被卡住。不要认为人们在看到问题时能想到解决方案是多么令人惊奇。“没有他，只有你熟悉！”

应牢记以下两个提示，这也是本主题的目的：

根据以上两种技术，假设有12+7：

根据分析，完成问题解决方案：

//JAVA
class Solution {
    public int getSum(int a, int b){
        while(b != 0){
            int temp = a ^ b;
            b = (a & b) << 1;
            a = temp;
        }
        return a;
    }
}

剑指Offer 65.加法不加减乘除

编写一个函数来计算两个整数的和。要求函数体中不能使用“+”、“-”、“*”和“/”四个运算符。

例子：

输入: a = 1, b = 1
输出: 2

回答

//JAVA
class Solution {
    public int add(int a, int b) {
        // 该位都为1，&，则进位
        // 异或运算，^，非进位加
        // 我们使用temp来记录进位的位数二进制
        // 每次我们都将 非进位和 与 进位二进制 做非进位加法运算，直到没有进位为止（进位为0）
        while(b != 0) { // 当进位为 0 时跳出
            int temp = (a & b) << 1;  // temp = 进位
            a ^= b; // a = 非进位和
            b = temp; // b = 进位
        }
        return a;
    }
}

文章版权声明 1、本站永久网址：https://www.9im.cn
2、本主题所有言论和图片纯属会员个人意见，与本网站立场无关。
3、本网站所有源码和软件均为作者提供和网友推荐收集整理而来，对提供的源码不拥有任何权利，其版权归原著者拥有。仅供学习和研究使用,下载后请24小时内删除。不得使用于非法商业用途，不得经营非法游戏或违反国家法律。一切关于该资源商业行为与老王博客无关。
4、如果您喜欢该程序，请支持正版源码、软件，购买注册，得到更好的正版服务。如有侵犯你版权的，请邮件与我们联系处理，本站将立即改正。
5、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END

喜欢就支持一下吧