318. Maximum Product of Word Lengths

https://leetcode.com/problems/maximum-product-of-word-lengths/description/
    int maxProduct(vector<string>& words) {
        int N = words.size();
        int res = 0;
        vector<int> w(N, 0);
        for(int i=0; i<N; i++) {
            for(char c : words[i]) w[i] |= 1 << (c - 'a');
            for(int j=0; j<i; j++) {
                if((w[j] & w[i]) == 0) {
                    res = max(res, (int) words[i].size() * (int) words[j].size());
                }
            }
        }
        return res;
    }

421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/
Solution 1. Get the max XOR for each num using TRIE searching after the tree is built.
Solution 2. Search the tree after the tree is built.
class Solution {
    struct TreeNode {
        TreeNode* l;
        TreeNode* r;
        TreeNode(): l(nullptr), r(nullptr) {};
    };
public:
    int findMaximumXOR(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int b = 30;
        TreeNode* root = getTree(nums, b), *node = root;
        while(node && !(node->l && node->r)) {
            b--;
            if(node->l) node = node->l;
            else node = node->r;
        }
        if(b==-1) return 0;
        int res = 0;
        dfs(node->l, node->r, b, res, 1<<b);
        return res;
    }
    void dfs(TreeNode* nl, TreeNode* nr, int b, int& res, int s) {
        if(b==-1) {
            if(s>res) res = s;
            return;
        }
        if(!nl || !nr) return;
        b--;
        if(nl->l && nr->r || nl->r && nr->l) {
            dfs(nl->l, nr->r, b, res, s|(1<<b));
            dfs(nl->r, nr->l, b, res, s|(1<<b));
        }
        else {
            dfs(nl->l, nr->l, b, res, s);
            dfs(nl->r, nr->r, b, res, s);
        }
    }
    TreeNode* getTree(vector<int>& nums, int b) {
        TreeNode* root = new TreeNode(), *node;
        for(int n : nums) {
            int k = 1<<b;
            node = root;
            while(k) {
                if(k&n) {
                    if(!node->r) node->r = new TreeNode();
                    node = node->r;
                }
                else {
                    if(!node->l) node->l = new TreeNode();
                    node = node->l;
                }
                k >>= 1;
            }
        }
        return root;
    }
};

477. Total Hamming Distance

https://leetcode.com/problems/total-hamming-distance/description/
    int totalHammingDistance(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int N = nums.size();
        int res = 0, w=1;
        for(int i=0; i<32; i++) {
            int n1 = 0;
            for(int j=0; j<N; j++) {
                n1 += (nums[j]&w)!=0;
            }
            res += n1*(N-n1);
            w <<= 1;
        }
        return res;
    }

693. Binary Number with Alternating Bits

bool hasAlternatingBits(int n) {
        if(n&1) n >>= 1;
        int i=0;
        while(n){
            if((n&3) != 2) return false;
            n >>= 2;
        }
        return true;
    }

260. Single Number III

https://leetcode.com/problems/single-number-iii/description/

    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res;
        int x = 0;
        for(int n: nums) {
            x ^= n;
        }
        int b = 1;
        while((b&x) == 0) b <<= 1;
      // explanation in link
      //  // Get the XOR of the two numbers we need to find
      //  int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
      //  // Get its last set bit,  diff &= ~(diff-1) is slower
      //  diff &= -diff; 

        int y = 0, z = 0;
        for(int n: nums) {
            if(b&n) y ^= n;
            else z ^= n;
        }
        return {y, z};
    }

540. Single Element in a Sorted Array

https://leetcode.com/problems/single-element-in-a-sorted-array/description/
    int singleNonDuplicate(vector<int>& nums) {
        for(int i=1;i<nums.size();i+=2) {
            if(nums[i] != nums[i-1]) return nums[i-1];
        }
        return nums.back();
    }
or use XOR
    int singleNonDuplicate(vector<int>& nums) {
        int res = 0;
        for(int n : nums) {
            res ^= n;
        }
        return res;
    }

338. Counting Bits

https://leetcode.com/problems/counting-bits/description/
    vector<int> countBits(int num) {
        vector<int> res;
        for(int i=0; i<=num; i++) {
            int n = i;
            int b = 0;
            while(n) {
                b += n&1;
                n >>= 1;
            }
            res.push_back(b);
        }
        return res;
    }

69. Sqrt(x)

https://leetcode.com/problems/sqrtx/description/
Solution 1.
    int mySqrt(int x) {
        if(x == 0) return 0;
        int n = 0;
        for(int m = 1<<30; m!=0; m>>=1){
            int r = n|m;
            while(r>x/r) {
                m >>= 1;
                r = n|m;
            }
            n |= m;
        }
        return n;
    }
Solution 2
    int mySqrt(int x) {
        if(x == 0) return 0;
        double y = log10(x)/2.;
        return (int) pow(10.,y);
    }

190. Reverse Bits

https://leetcode.com/problems/reverse-bits/description/
    uint32_t reverseBits(uint32_t n) {
        int res = 0, f = 1;
        for(int i=0; i<32; i++, n >>= 1) {
            res <<= 1;
            res |= (n & 1);
        }
        return res;
    }

367. Valid Perfect Square

https://leetcode.com/problems/valid-perfect-square/description/
Solution 1. For 32 bit integer input num, sqrt(num) < pow(2,16). Let n=0, Start from 15th bit, n = n + pow(2,15). If num < n*n, decreasing n to pow(2,14), pow(2,13), ... until num > n*n, say n = pow(2,i). Then start again from i-1 bit.
     bool isPerfectSquare(int num) {
        vector<int> sq;
        int n = 0;
        for(int i=15; i>=0; i--){
            while(pow(n+(1<<i),2) > num && i>=0) i--;
            n += (1<<i);
            if(pow(n,2) == num) return true;
        }
        return false;
    }
Solution 2. 1 + 3 + 5 + ... + (2n-1) = n*n
     bool isPerfectSquare(int num) {
        int i = 1;
        while (num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;
    }

342. Power of Four

https://leetcode.com/problems/power-of-four/description/
Solution 1. Shift and compare the last 2 bits on the left.
    bool isPowerOfFour(int num) {
        if(num<=0) return false;    
        while(num){
            if(num&3) {
                if(num == 1) return true;
                return false;
            }
            num >>= 2;
        }
        return true;
    }
Solution 2. It can be fit in one line. A number is power of 4 only if num>4 and only 1 nonzero bit and the nonzero bit is at 1, or 3, or 5 ...
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
    }

191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/
Solution 1. One operation of n&(n-1) eliminates the rightmost 1 of the integer. (3 ms)
int hammingWeight(uint32_t n)
{
    int res = 0;
    while(n)
    {
        n &= n - 1;
        ++ res;
    }
    return res;
}
Solution 2. shift and count 6 ms
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n) {
            res += (n&1);
            n >>= 1;
        }
        return res;
    }

231. Power of Two

https://leetcode.com/problems/power-of-two/description/
Solution 1.
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        int p = 0;
        while(n){
            p += (n & 1);
            n >>= 1;
        }
        if(p == 1) return true;
        return false;
    }
Solution 2.
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        return !(n&(n-1));
    }

405. Convert a Number to Hexadecimal

https://leetcode.com/problems/convert-a-number-to-hexadecimal/description/

Solution 2.
    string toHex(int num) {
        if(num==0) return "0";
        vector<char> dict {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        string res;
        for(int i=0;i<8 && num;i++){
            res = dict[num & 15] + res;
            num >>= 4;
        }
        return res;
    }

268. Missing Number

https://leetcode.com/problems/missing-number/description/
Solution 1. 
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++) {
            res ^= (i ^ nums[i]);
        }
        return res^nums.size();
    }
Solution 2.
    int missingNumber(vector<int>& nums) {
        vector<int> s(nums.size()+1, -1);
        for(int i=0; i<nums.size(); i++) {
            s[nums[i]] = 1;
        }
        for(int i=0; i<s.size(); i++) {
            if(s[i] == -1) return i;
        }
        return -1;
    }

401. Binary Watch

https://leetcode.com/problems/binary-watch/description/
Solution 1. Loop through hour and minute, check the total bits
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        for(int h=0; h<12; h++) {
            for(int m=0; m<60; m++) {
                if(bitset<10> (h<<6 | m).count() == num)
                   res.push_back(to_string(h) + ":" + (m<10 ? "0":"") + to_string(m));
            }
        }
        return res;
    }
Solution 2. Get all possible numbers with num bits
    void combination(int n, int N, int s, vector<int>& c) {
        if(n>N || n==0) return;
        if(n==1) {
            for(int i=0;i<N;i++) {
                c.push_back(s + (1<<i));
            }
            return;
        }
        combination(n, N-1, s, c);
        combination(n-1, N-1, s + (1<<(N-1)), c);
    }
    vector<string> readBinaryWatch(int num) {
        if(num == 0) return vector<string> {"0:00"};
        vector<string> res;
        vector<int> c;
        combination(num, 10, 0, c);
        for(auto x : c) {
            int m = x & 15;
            int s = x >> 4;
            if(m<12 && s<60) res.push_back(to_string(m) + ":" + (s<10? "0":"") + to_string(s));
        }
        return res;
    }

409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/
Solution 1.
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
                res += (cnt[i]& ~1);
        }
        return res + (res < s.size()); // there is odd when (res < s.size())
    }

Solution 2. slower
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        int odd = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
            if(cnt[i]%2==0)
                res += cnt[i];
            else {
                res += cnt[i] - 1;
                odd = 1;
            }
        }
        return res + odd;
    }

661. Image Smoother

https://leetcode.com/problems/image-smoother/description/
Solution 0. Use the bits at the same address to store the sum and counts
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int L = M.size();
        int W = M[0].size();

        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                for(int m=i-1;m<=i+1;m++) {
                    for(int n=j-1;n<=j+1;n++) {
                        if(m>=0 && m<L && n>=0 && n<W) {
                            // bits 0~7: 255 = 11111111b
                            // original value = M[m][n] & 255
                            // bits 8~11: counts 
                            // 256 = 100000000b
                            // bits 12~ : sum
                            M[i][j] += 256 + ((M[m][n]&255) << 12);
                        }
                    }
                }
            }
        }
        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                // 15 = 1111b, use & to get the counts
                M[i][j] = (M[i][j]>>12)/((M[i][j]>>8) & 15);
            }
        }
        return M;
    }
Solution 1. A boring solution.

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
https://leetcode.com/problems/sum-of-two-integers/description/
    int getSum(int a, int b) {
        int s = a;
        while(b != 0) {
            s = a ^ b;
            b = (a & b) << 1;
            a = s;
        }
        return s;
    }

389. Find the Difference

Description https://leetcode.com/problems/find-the-difference/description/
Solution 1, use XOR
    char findTheDifference(string s, string t) {
        char c = 0;
        for(int i=0;i<s.size();i++)
            c ^= s[i];
        for(int i=0;i<t.size();i++)
            c ^= t[i];
        return c;
    }
Solution 2, sort the strings and compare.
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        for(int i=0; i<s.size();i++) {
            if(s[i]!=t[i]) return t[i];
        }
        return t.back();
    }