leetcode 231 && ​342 && 371 && 318 && 338

 leetcode 231. 2 的幂  easy   题目描述：

解题思路：

n大于0，且二进制表示只有一个1即可

代码：

//
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n -1)) == 0; // n 大于0， 且只有一个1
    }
};

 leetcode 342. 4的幂  easy             题目描述：

解题思路：

先判断是否2的幂，然后假如是4的幂，唯一的那个1肯定出现在奇数的位置，

所以构造一个整数mask，它的所有偶数二进制位都是 0，所有奇数二进制位都是 1。这样一来，我们将 n 和 mask 进行按位与运算，如果结果为 0，说明 n 二进制表示中的 1 出现在偶数的位置，否则说明其出现在奇数的位置。

代码：

//
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n-1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

 leetcode 371. 两整数之和   medium           题目描述：

解题思路：

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

代码：

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

 leetcode 318. 最大单词长度乘积   medium           题目描述：

• words[i] 仅包含小写字母

解题思路：

本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的整数来存储每个字符是否出现过。

代码：

//
class Solution {
public:
    int maxProduct(vector& words) {
        
        vector masks(words.size());

        for (int i = 0; i < words.size(); i++){
            int one = 0;
            for (char &c: words[i])
                one |= 1 << (c-'a');
            masks[i] = one;
        }

        int res = 0;
        for (int i = 0; i < words.size(); i++){
            for (int j = i+1; j< words.size(); j++){
                if ((masks[i] & masks[j]) == 0)
                    res = max(res, int(words[i].size() * words[j].size()));
            }
        }

        return res;



    }
};

 leetcode 338. 比特位计数  easy     题目描述：

解题思路：

对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;

代码：

//
class Solution {
public:
    vector countBits(int n) {
        vector res(n+1);
        for (int i =1; i< n+1; i++){
            res[i] = res[i&(i-1)] + 1;
        }
        return res;

    }
};