知識點(diǎn)整理

二進(jìn)制原碼矮嫉、反碼、補(bǔ)碼最好的解釋

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

1喳篇、為什么要有原碼敞临。

為了解決“正負(fù)相加等于0”的問題，在“原碼”的基礎(chǔ)上麸澜，人們發(fā)明了“反碼”挺尿。

在計(jì)算機(jī)的世界里，只有 1 和 0炊邦。 原碼是為了表示負(fù)數(shù)而引入的一種編碼表示方式编矾。

規(guī)則：最高位作為符號位：0 表示正數(shù)， 1 表示負(fù)數(shù)馁害。

但是有如下問題：

（1）此時(shí)數(shù)字 的表示出現(xiàn)了二義性窄俏。

例如： 和 都表示 。

（2）數(shù)字會產(chǎn)生突然的變化

例如： + =

127 + 1 = 0 并且這個(gè) 0 是 -0

例如：1111 1111 + 1 = 0000 0000

-127 變成了 +0

（3）原碼參與運(yùn)算會出錯(cuò)

2碘菜、反碼：反碼是通過原碼得到的凹蜈。

正數(shù)的反碼是自己，

負(fù)數(shù)的反碼：符號位不變

位運(yùn)算總結(jié)：

n & (n-1)：可以把從右邊到左邊的第 個(gè) 變成 忍啸。

n & (~(n-1))：只保留了從右邊到左邊的第 個(gè) 仰坦。

例題

LeetCode 第 136 題：只出現(xiàn)一次的數(shù)字

傳送門：136. 只出現(xiàn)一次的數(shù)字。

給定一個(gè)非空整數(shù)數(shù)組计雌，除了某個(gè)元素只出現(xiàn)一次以外悄晃，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素凿滤。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度妈橄。 你可以不使用額外空間來實(shí)現(xiàn)嗎庶近？

示例 1:

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

示例 2:

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

LeetCode 第 201 題：數(shù)字范圍按位與

傳送門：201. 數(shù)字范圍按位與。

給定范圍 [m, n]眷蚓，其中 0 <= m <= n <= 2147483647鼻种，返回此范圍內(nèi)所有數(shù)字的按位與（包含 m, n 兩端點(diǎn)）。

示例 1:

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

示例 2:

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

分析：位運(yùn)算的問題溪椎，干脆就把它記住普舆。

思路：相鄰的兩個(gè)數(shù)末尾相與一定等于 。于是就有如下寫法：

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) 運(yùn)算依次消去“大于” 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. 漢明距離總和歉秫。

兩個(gè)整數(shù)的 漢明距離 指的是這兩個(gè)數(shù)字的二進(jìn)制數(shù)對應(yīng)位不同的數(shù)量蛾洛。

計(jì)算一個(gè)數(shù)組中，任意兩個(gè)數(shù)之間漢明距離的總和雁芙。

示例:

輸入: 4, 14, 2

輸出: 6

解釋: 在二進(jìn)制表示中轧膘，4表示為0100，14表示為1110兔甘，2表示為0010谎碍。（這樣表示是為了體現(xiàn)后四位之間關(guān)系）
所以答案為：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

1. 數(shù)組中元素的范圍為從 0到 10^9。
2. 數(shù)組的長度不超過 10^4洞焙。

Java 代碼：某一位上 的數(shù)量乘上 的數(shù)量就是這一位對結(jié)果的貢獻(xiàn)蟆淀，當(dāng)某一位上全是 時(shí)就沒有繼續(xù)計(jì)算下去的必要了。

/**
 * 計(jì)算任意漢明距離總和
 */
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++) {
            // 在這個(gè)數(shù)位上有多少個(gè) 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 題：數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字

傳送門：數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字澡匪。

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外熔任，其他的數(shù)字都出現(xiàn)了兩次。

請寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字唁情。

你可以假設(shè)這兩個(gè)數(shù)字一定存在疑苔。

樣例

輸入：[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('程序出錯(cuò)')
        if l == 2:
            return nums

        # 全部相與一遍
        xor = 0
        for num in nums:
            xor ^= num
            
        # 最末尾的 1 從右向左邊數(shù)在第幾位
        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 題：數(shù)組中數(shù)字出現(xiàn)的次數(shù) P275
// 參考資料：
// 1甸鸟、https://blog.csdn.net/derrantcm/article/details/46771717
public class Solution {

    // 考察位運(yùn)算：或惦费、與、異或抢韭、非薪贫，以及無符號左移 >>>
    public int[] findNumbersAppearanceOnce(int[] nums) {
        int len = nums.length;
        int[] res = new int[2];
        assert len >= 2;
        if (len == 2) {
            return nums;
        }
        // 那兩個(gè)只出現(xiàn)一次的數(shù)的異或運(yùn)算的結(jié)果
        int xor = xor(nums);
        
        // 關(guān)鍵在這里
        // 找到這個(gè) xor 的二進(jìn)制表示第 1 個(gè)是 1 的數(shù)位是第幾位
        int binaryFirstNotZero = binaryFirstNotZero(xor);
        
        // 接下來分別對兩組進(jìn)行異或
        for (int i = 0; i < len; i++) {
            // 如果這個(gè)數(shù)右移這么多位是 1 的分在一組，是 0 的分在另外一組篮绰，遍歷的時(shí)候后雷，就進(jìn)行異或運(yùn)算
            if ((nums[i] >>> binaryFirstNotZero & 1) == 1) {
                res[0] ^= nums[i];
            } else {
                res[1] ^= nums[i];
            }
        }
        return res;
    }

    // 得到一個(gè)數(shù)組經(jīng)過異或運(yùn)算的結(jié)果 xor
    // 異或 的英文翻譯就是 xor
    private int xor(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
        }
        return xor;
    }

    // 得到一個(gè)整數(shù)的二進(jìn)制表示從右到左第 1 個(gè)非零的位數(shù)是第幾位
    private int binaryFirstNotZero(int num) {
        int index = 0;
        // 這里的 1 把它看成二進(jìn)制的 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 題：數(shù)組中兩個(gè)數(shù)的最大異或值

要求：給定一個(gè)非空數(shù)組吠各，數(shù)組中元素為 a0, a1, a2, … , an-1臀突，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的異或 (XOR) 運(yùn)算結(jié)果贾漏，其中0 ≤ i, j < n 候学。

你能在O(n)的時(shí)間解決這個(gè)問題嗎？

參考資料：https://www.cnblogs.com/njufl/p/6403043.html

1纵散、這里Trie樹建立的思路是梳码，整數(shù)在存儲時(shí)是一個(gè)占據(jù) 32bit 的數(shù)，因此可以看成一個(gè)含32個(gè)字符的字符串伍掀，這個(gè)字符串中的每個(gè)字符只可能是0或1掰茶。

因此，將一個(gè)整數(shù)插入 Trie 樹就是從它的最高位開始蜜笤，根據(jù)每一位上的值進(jìn)入不同的分支濒蒋，直到最低位。

3把兔、那么如何找到最大的異或值呢沪伙？

（1）兩個(gè)數(shù)異或得到一個(gè)數(shù)，這個(gè)數(shù)的值要盡量大县好，那么這個(gè)數(shù)的二進(jìn)制表示法中围橡，第一個(gè)1出現(xiàn)的位數(shù)越高這個(gè)數(shù)就越大，即置1位越高數(shù)越大缕贡。

所以翁授，對于數(shù)組中的每一個(gè)數(shù)，要找到它和數(shù)組中其他數(shù)異或后得到的最大異或值善绎，可以采用類似貪心的策略黔漂，從最高位開始，找和它在這一位相反的數(shù)禀酱。如果有炬守，那么和這個(gè)數(shù)異或就得到最大異或值，如果沒有就依次往下一位找剂跟，直到找到相異的位减途。

4、一開始曹洽，先將數(shù)組中所有的數(shù)鳍置，建成一棵 Trie 樹后再對每一個(gè)數(shù)求各自的最大異或值，然后再取最大值送淆，建立 Trie 樹的時(shí)間復(fù)雜度是 O(32n) 税产，這里的 32 即 Trie 樹的鍵值最大長度；

5、Trie樹的高度為 32 辟拷，因此查找每個(gè)數(shù)的最大異或值得時(shí)間復(fù)雜度是 O(32n) 撞羽，合起來是 O(64n) ，提交時(shí)出現(xiàn)了TLE衫冻，顯然時(shí)間復(fù)雜度太高了诀紊。代碼大致如下：

342： 4 的冪

LeetCode 第 868 題：二進(jìn)制間距

要求：給定一個(gè)正整數(shù) N，找到并返回 N 的二進(jìn)制表示中兩個(gè)連續(xù)的 1 之間的最長距離隅俘。

如果沒有兩個(gè)連續(xù)的 1邻奠，返回 0 。

注意：這里設(shè)置 pre 初值為 -1 的小技巧为居，即 pre 一定要被賦值以后碌宴，才能參與計(jì)算。

image-20190111002912609

（本節(jié)完）