關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers

Bit Manipulation(位運(yùn)算)：

• 與 &
• 或 |
• 異或 ^
• 左移 <<
• 右移 >>
  • 正數(shù)右移悯许，高位用 0 補(bǔ)瘫想，負(fù)數(shù)右移昧谊，高位用 1 補(bǔ)
• 無(wú)符號(hào)右移 >>>
  • 當(dāng)負(fù)數(shù)使用無(wú)符號(hào)右移時(shí)玫霎，用 0 進(jìn)行補(bǔ)位
• 取非 ~
  • 一元操作符

一些小技巧

• 將數(shù)字 A 的第 k 位設(shè)置為1：A = A | (1 << (k - 1))
• 將數(shù)字 A 的第 k 位設(shè)置為0：A = A & ~(1 << (k - 1))
• 檢測(cè)數(shù)字 A 的第 k 位：A & (1 << (k - 1)) != 0
• Extract the lowest set bit 獲取數(shù)字 A 的最低位：A & -A 或者 A & ~(A - 1)
  • 例如數(shù)字 6（110）的最低位對(duì)應(yīng) 2（10）
• 得到 111111..111: ~0

異或 ^ 運(yùn)算的小技巧

Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same.
去除出現(xiàn)偶數(shù)次的數(shù)字褥蚯，保留出現(xiàn)奇數(shù)次的數(shù)字挚冤。

LeetCode 題目：371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

// Recursive
public int getSum(int a, int b) {
    return b == 0 ? a : getSum(a^b, (a&b)<<1);
}

// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

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

LeetCode 題目：122. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

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

或 | 運(yùn)算的小技巧

Keep as many 1-bits as possible
盡可能多地保留 1

題目：
Find the largest power of 2 (most significant bit in binary form), which is less than or equal to the given number N.

long largest_power(long N) {
    //changing all right side bits to 1.
    N = N | (N>>1);
    N = N | (N>>2);
    N = N | (N>>4);
    N = N | (N>>8);
    N = N | (N>>16);
    return (N+1)>>1;
}

LeetCode 題目：190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

public int reverseBits(int n) {
    int result = 0;
    
    for(int i = 0; i < 32; i++) {
        result = result + (n & 1);
        
        n >>>= 1;   // CATCH: must do unsigned shift
        if (i < 31) // CATCH: for last digit, don't shift!
            result <<= 1;
        }
    
    return result;
}

與 & 運(yùn)算的小技巧

Just selecting certain bits
選擇特定的位

LeetCode 題目：191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

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

LeetCode 題目：477. Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.

public int hammingDistance(int x, int y) {
    
    int xor = x ^ y;
    
    return hammingWeight(xor);
}

// you need to treat n as an unsigned value
public int hammingWeight(int n) {
    int count = 0;
    int mask = 1;
    
    for (int i = 0; i < 32; i++) {
        
        if((n & mask) != 0) {
            count++;
        }
        
        mask = mask << 1;
    }
    
    return count;
}

其他位運(yùn)算算法題

LeetCode 題目：169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

// Hashtable 
public int majorityElement2(int[] nums) {
    Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
    //Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
    int ret=0;
    for (int num: nums) {
        if (!myMap.containsKey(num))
            myMap.put(num, 1);
        else
            myMap.put(num, myMap.get(num)+1);
        if (myMap.get(num)>nums.length/2) {
            ret = num;
            break;
        }
    }
    return ret;
}

// Moore voting algorithm
public int majorityElement3(int[] nums) {
    int count=0, ret = 0;
    for (int num: nums) {
        if (count==0)
            ret = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return ret;
}

// Bit manipulation 
public int majorityElement(int[] nums) {
    int[] bit = new int[32];
    for (int num: nums)
        for (int i=0; i<32; i++) 
            if ((num>>(31-i) & 1) == 1)
                bit[i]++;
    int ret=0;
    for (int i=0; i<32; i++) {
        bit[i]=bit[i]>nums.length/2?1:0;
        ret += bit[i]*(1<<(31-i));
    }
    return ret;
}

LeetCode 題目：187. Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example, Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return: ["AAAAACCCCC", "CCCCCAAAAA"].

public List<String> findRepeatedDnaSequences(String s) {
    Set<Integer> words = new HashSet<>();
    Set<Integer> doubleWords = new HashSet<>();
    
    List<String> rv = new ArrayList<>();
    
    char[] map = new char[26];
    //map['A' - 'A'] = 0;
    map['C' - 'A'] = 1;
    map['G' - 'A'] = 2;
    map['T' - 'A'] = 3;

    for(int i = 0; i < s.length() - 9; i++) {
        int v = 0;
        
        for(int j = i; j < i + 10; j++) {
            v <<= 2;
            v |= map[s.charAt(j) - 'A'];
        }
        
        if(!words.add(v) && doubleWords.add(v)) {
            rv.add(s.substring(i, i + 10));
        }
    }
    
    return rv;
}

LeetCode 題目：136. Single Number
Given an array of integers, every element appears twice except for one. Find that single one.

public int singleNumber(int[] nums) {
    // null pointer check
    if(nums == null) {
        return 0;
    }
    
    int result = 0;
    for(int i : nums) {
        result = result ^ i;
    }
    
    return result;
}

LeetCode 題目：137. Single Number II
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

public int singleNumber(int[] nums) {
    // null pointer check
    if(nums == null) {
        return 0;
    }

    /*
    每一個(gè)int都是32位（4 bytes），遍歷每一個(gè)int的每一位赞庶。
    如果某一位上是1训挡，則count++，對(duì)于出現(xiàn)了三次的int歧强，則該位上count = 3澜薄。
    因此 count = count % 3可以清除出現(xiàn)了三次的int，保留至出現(xiàn)了一次的int摊册。
    */
    
    int result = 0;
    for(int i = 0; i < 32; i++) {
        int count = 0;
        
        for(int j = 0; j < nums.length; j++) {
            if((nums[j] & 1) == 1) {
                count++;
            }
            nums[j] = nums[j]>>>1;
        }
        
        count = count % 3;
        
        if(count != 0) {
            result = (count << i) + result;
        }
    }

    return result;
}

LeetCode 題目：260. Single Number III
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

public int[] singleNumber(int[] nums) {
    // 假設(shè)只出現(xiàn)一次的數(shù)字為 A肤京，B
    
    /*
    第一步，得到所有數(shù)字的異或結(jié)果丧靡，即 A ^ B蟆沫，因?yàn)槠渌麛?shù)字都出現(xiàn)兩次
    這個(gè)結(jié)果不能為0，因?yàn)?A != B温治，其實(shí)這個(gè)結(jié)果表示的是 A 和 B 之間的差別饭庞。
    假設(shè)這個(gè)結(jié)果的第 i 位為1，則說(shuō)明A和B在第 i 位不同熬荆，可能一個(gè)是 1（假設(shè)是 A）舟山，另外一個(gè)是 0（假設(shè)是 B）。
    */
    int diff = 0;
    for(int num : nums) {
        diff = diff ^ num;
    }
    
    // Extract the lowest set bit 獲取數(shù)字 A 的最低位
    // or diff = diff & ~(diff - 1);
    diff = diff & -diff;
    
    /*
    結(jié)合上面的理論卤恳，所有的數(shù)字可以分為兩組：
        第一組包括A和其他一些數(shù)字累盗，他們的第 i 位為1
            因此在第一組內(nèi)部求異或結(jié)果，即為 A
            
        第二組包括B和其他一些數(shù)字突琳，他們的第 i 位為0
            因此在第二組內(nèi)部求異或結(jié)果若债，即為 B
    */
    int a = 0;
    int b = 0;
    
    for(int num : nums) {
        // 第一組
        if ((num & diff) == 0) {
            a = a ^ num;
        }
        
        // 第二組
        else {
            b = b ^ num;
        }
    }
    
    return new int[]{a, b};
}

LeetCode 題目：239. Power of Two
Given an integer, write a function to determine if it is a power of two.

public boolean isPowerOfTwo(int n) {
    /*
    2的冪都遵循如下格式：
    1
    10
    100
    1000
    ...
    */
    
    if(n < 0) return false;
    
    // 最簡(jiǎn)單的 return !(n&(n-1));

    while(n != 0) {
        if(n == 1) {
            return true;
        }
        
        if((n & 1) == 1) {
            return false;
        }
        
        n = n >>> 1;
    }
    
    return false;
}

LeetCode 題目：342. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

public boolean isPowerOfFour(int num) {
    /*
    4的冪都遵循如下格式：
    1
    4: 100 (2個(gè)0)
    16: 10000 (4個(gè)0)
    64: 1000000 (6個(gè)0)
    256: 100000000 (8個(gè)0)
    ...
    */
    
    if(num < 0) return false;
    
    // 0x55555555 is to get rid of those power of 2 but not power of 4
    // 最簡(jiǎn)單 return (num&(num-1)) == 0 && (num & 0x55555555) != 0;
    
    if(num == 1) return true;
    
    for(int i = 1; i * 2 < 32; i++) {
        int t = (1 << (i * 2));
        if((num ^ t) == 0) {
            return true;
        }
    }
    
    return false;
}

LeetCode 題目：338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

class Solution {
    public int[] countBits(int num) {
        if(num < 0) return null;
        
        int[] result = new int[num + 1];
        
        result[0] = 0; // 00
        
        for(int i = 1; i <= num; i++) {
            // 對(duì)于偶數(shù)，例如6 = 2 * 3; 因此 result[6] = result[3]拆融，乘以二相當(dāng)于左移蠢琳，不增加1的個(gè)數(shù)
            if(i % 2 == 0) {
                result[i] = result[i / 2];
            }
            // 對(duì)于奇數(shù)，例如5 = 2 * 2 + 1; 因此 result[5] = result[2] + 1镜豹，乘以二相當(dāng)于左移傲须，不增加1的個(gè)數(shù)
            else {
                result[i] = result[i / 2] + 1;
            }
        }
        
        return result;
    }
}

更多位運(yùn)算相關(guān)算法題，參見(jiàn) LeetCode Bit Manipulation

引用：
a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently