LeetCode 专题：位运算

知识点整理

二进制原码、反码、补码最好的解释

https://www.zhihu.com/question/20159860/answer/71256667

1、为什么要有原码。

为了解决“正负相加等于0”的问题，在“原码”的基础上，人们发明了“反码”。

在计算机的世界里，只有 1 和 0。 原码是为了表示负数而引入的一种编码表示方式。

规则：最高位作为符号位：0 表示正数， 1 表示负数。

但是有如下问题：

（1）此时数字 的表示出现了二义性。

例如： 和 都表示 。

（2）数字会产生突然的变化

例如： + =

127 + 1 = 0 并且这个 0 是 -0

例如：1111 1111 + 1 = 0000 0000

-127 变成了 +0

（3）原码参与运算会出错

2、反码：反码是通过原码得到的。

正数的反码是自己，

负数的反码：符号位不变

位运算总结：

n & (n-1)：可以把从右边到左边的第 个 变成 。

n & (~(n-1))：只保留了从右边到左边的第 个 。

例题

LeetCode 第 136 题：只出现一次的数字

传送门：136. 只出现一次的数字。

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

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

LeetCode 第 201 题：数字范围按位与

传送门：201. 数字范围按位与。

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:

输入: [5,7]
输出: 4

示例 2:

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

分析：位运算的问题，干脆就把它记住。

思路：相邻的两个数末尾相与一定等于 。于是就有如下写法：

Java 代码：

public class Solution2 {
    /**
     * 真的是很酷！
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            count++;
        }
        return m << count;
    }
}

于是我们可以一步到位，利用 n &= (n - 1) 运算依次消去“大于” m 的部分的 。

Java 代码：

/**
 * https://blog.csdn.net/DERRANTCM/article/details/47997613
 *
 * @author liwei
 * @date 18/6/29 下午9:37
 */
public class Solution3 {

    /**
     * 利用了 n &= (n - 1) 一下能消死一大片
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n &= (n - 1);
        }
        return n;
    }
}

LeetCode 第 477 题：汉明距离总和

传送门：477. 汉明距离总和。

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

1. 数组中元素的范围为从 0到 10^9。
2. 数组的长度不超过 10^4。

Java 代码：某一位上 的数量乘上 的数量就是这一位对结果的贡献，当某一位上全是 时就没有继续计算下去的必要了。

/**
 * 计算任意汉明距离总和
 */
public class Solution {

    public int totalHammingDistance(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int mask = 1;
        int total = 0;
        for (int i = 0; i < 32; i++) {
            // 在这个数位上有多少个 1
            int oneCount = 0;
            for (int num : nums) {
                if ((num & mask) > 0) {
                    oneCount++;
                }
            }
            total += ((len - oneCount) * oneCount);
            mask <<= 1;
        }
        return total;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4, 14, 2};
        Solution solution = new Solution();
        int totalHammingDistance = solution.totalHammingDistance(nums);
        System.out.println(totalHammingDistance);
    }
}

《剑指 Offer 》（第 2 版）第 56 题：数组中只出现一次的两个数字

传送门：数组中只出现一次的两个数字。

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

思路：==按位分组==。

Python 代码：

class Solution(object):
    def findNumsAppearOnce(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l = len(nums)
        if l < 2:
            raise Exception('程序出错')
        if l == 2:
            return nums

        # 全部相与一遍
        xor = 0
        for num in nums:
            xor ^= num
            
        # 最末尾的 1 从右向左边数在第几位
        counter = 0
        while xor & 1 == 0:
            xor >>= 1
            counter += 1

        res = [0, 0]
        for num in nums:
            if (num >> counter) & 1 == 1:
                res[1] ^= num
            else:
                res[0] ^= num
        return res

Java 代码：

import java.util.Arrays;

// 第 56 题：数组中数字出现的次数 P275
// 参考资料：
// 1、https://blog.csdn.net/derrantcm/article/details/46771717
public class Solution {

    // 考察位运算：或、与、异或、非，以及无符号左移 >>>
    public int[] findNumbersAppearanceOnce(int[] nums) {
        int len = nums.length;
        int[] res = new int[2];
        assert len >= 2;
        if (len == 2) {
            return nums;
        }
        // 那两个只出现一次的数的异或运算的结果
        int xor = xor(nums);
        
        // 关键在这里
        // 找到这个 xor 的二进制表示第 1 个是 1 的数位是第几位
        int binaryFirstNotZero = binaryFirstNotZero(xor);
        
        // 接下来分别对两组进行异或
        for (int i = 0; i < len; i++) {
            // 如果这个数右移这么多位是 1 的分在一组，是 0 的分在另外一组，遍历的时候，就进行异或运算
            if ((nums[i] >>> binaryFirstNotZero & 1) == 1) {
                res[0] ^= nums[i];
            } else {
                res[1] ^= nums[i];
            }
        }
        return res;
    }

    // 得到一个数组经过异或运算的结果 xor
    // 异或 的英文翻译就是 xor
    private int xor(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
        }
        return xor;
    }

    // 得到一个整数的二进制表示从右到左第 1 个非零的位数是第几位
    private int binaryFirstNotZero(int num) {
        int index = 0;
        // 这里的 1 把它看成二进制的 1，即 00000001
        while ((num & 1) == 0 && index < 32) {
            num >>>= 1;
            index++;
        }
        // 走到这里满足 (num & 1) == 1
        return index;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 3, 6, 3, 2, 5, 5};
        Solution solution = new Solution();
        int[] res = solution.findNumbersAppearanceOnce(nums);
        System.out.println(Arrays.toString(res));

        int[] nums2 = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] res2 = solution.findNumbersAppearanceOnce(nums2);
        System.out.println(Arrays.toString(res2));

        int[] nums3 = {4, 6};
        int[] res3 = solution.findNumbersAppearanceOnce(nums3);
        System.out.println(Arrays.toString(res3));

        int[] nums4 = {4, 6, 1, 1, 1, 1};
        int[] res4 = solution.findNumbersAppearanceOnce(nums4);
        System.out.println(Arrays.toString(res4));
    }
}

LeetCode 第 421 题：数组中两个数的最大异或值

要求：给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

你能在O(n)的时间解决这个问题吗？

参考资料：https://www.cnblogs.com/njufl/p/6403043.html

1、这里Trie树建立的思路是，整数在存储时是一个占据 32bit 的数，因此可以看成一个含32个字符的字符串，这个字符串中的每个字符只可能是0或1。

因此，将一个整数插入 Trie 树就是从它的最高位开始，根据每一位上的值进入不同的分支，直到最低位。

3、那么如何找到最大的异或值呢？

（1）两个数异或得到一个数，这个数的值要尽量大，那么这个数的二进制表示法中，第一个1出现的位数越高这个数就越大，即置1位越高数越大。

所以，对于数组中的每一个数，要找到它和数组中其他数异或后得到的最大异或值，可以采用类似贪心的策略，从最高位开始，找和它在这一位相反的数。如果有，那么和这个数异或就得到最大异或值，如果没有就依次往下一位找，直到找到相异的位。

4、一开始，先将数组中所有的数，建成一棵 Trie 树后再对每一个数求各自的最大异或值，然后再取最大值，建立 Trie 树的时间复杂度是 O(32n) ，这里的 32 即 Trie 树的键值最大长度；

5、Trie树的高度为 32 ，因此查找每个数的最大异或值得时间复杂度是 O(32n) ，合起来是 O(64n) ，提交时出现了TLE，显然时间复杂度太高了。代码大致如下：

342： 4 的幂

LeetCode 第 868 题：二进制间距

要求：给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。

如果没有两个连续的 1，返回 0 。

注意：这里设置 pre 初值为 -1 的小技巧，即 pre 一定要被赋值以后，才能参与计算。

image-20190111002912609

（本节完）