03 二进制特性

​ 利用二进制的一些特性，可以把位运算使用到更多问题上。例如，可以利用二进制和位运算输出一个数组的所有子集。假设有一个长度为 n 的数组，可以生成长度为 n 的所有二进制，1 表示选取该数字，0 表示不选取。这样就获得了 2^n 个子集。

342 4的幂 (opens new window)

给定一个整数，判断它是否是 4 的次方。

输入是一个整数，输出是一个布尔值，表示判断结果。

输入：n = 16
输出：true

解析：

​ 本题可以采用按位与运算简单实现判断数是否为4的幂。如果 n 是 4 的幂，那么 n 的二进制表示中有且仅有一个 1 ，且其位置必须为奇数位，例如16 = (10000)，从右向左且从1开始计数的话，16的二进制表示中 1 位于第5位。根据此规律可以将 n 和二进制01010101010101010101010101010101或者十六进制的0x55555555做按位与，如果得到的结果不为零，那么说明这个数可能是 4 的幂。

​ 为什么说是可能呢？可以看出上述条件是充分条件而非充要条件，1 与0x55555555做按位与的结果也是非0的。

​ 所以需要进一步考虑该数 n 也是 2 的幂，才能保证上述条件判断结果为该数是 4 的幂。如果 n 是 2 的幂，那么 n 的二进制表示中也有且仅有一个 1，假设其位置为 pos ；那么 n - 1 二进制表示由第 1 位到第 pos-1 位全部为 1构成。例如16 = 10000; 15 = 01111 ，所以可以得出：如果 n & (n - 1) == 0，那么 n 是 2 的幂。

​ 最终得到：如果(n&(n-1))==0 && (n & 0x55555555)!=0，那么n 是 4 的幂。

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && !(n&(n-1)) && (n&0x55555555);
    }
};

​ 当然，本题也可以采用类似求 326. 3的幂 (opens new window)的方法直接使用对数函数的换底公式构造log4(n)，然后使用fmod()函数判断该值是否为整数，进而判断 n 是否是 4 的幂。

class Solution {
public:
    bool isPowerOfFour(int n) {
        return fmod(log10(n)/log10(4),1) == 0;
    }
};

318 最大单词长度乘积 (opens new window)

给定多个字母串，求其中任意两个字母串的长度乘积的最大值，且这两个字母串不能含有相同字母。

输入一个包含多个字母串的一维数组，输出一个整数，表示长度乘积的最大值。

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

解析：

​ 怎样快速判断两个字母串是否含有重复数字呢？可以为每个字母串建立一个长度为 26 的二进制数字 mask，用于表示从右到左每个位置表示是否存在a-z对应的字母。例如abc:111, abd:1011，如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0，例如abc,adbe存在相同的字母，将它们按位与的结果是1011!=0。

​ 怎么实现对字符串的编号记录呢？也可以通过位运算实现：首先将 mask 置为 0，然后遍历字符串的所有字符，每一次遍历中计算当前字符串所处的位置，然后使用算术左移，将标识 1 移动到指定位置，移动完成后将其与mask按位与运算，将位置记录在mask中。

​ 为了求长度乘积的最大值，可以建立一个哈希表记录字符串与其自身的长度。在计算长度乘积最大值时，遍历哈希表将不存在相同字母的字符串长度相乘并取最大值。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int,int> hash;
        int ans = 0;
        for(const auto& word: words){
            int mask = 0;
            int wordLen = word.length();
            // 为当前字符串编码
            for(const auto c:word){
                // 考虑字符串中每一个字符时，将 1 左移 (c-'a') 位
                int cPos = 1 << (c-'a');
                // 与mask按位与，将当前字符的位置保存到mask中，如果当前字符已经存在不影响mask
                mask = mask | cPos;
            }
            // 更新mask对应的长度时要考虑到：字符串中元素重复出现的情况，这种情况下字符串长度不一致 
            hash[mask] = max(hash[mask],wordLen);
            // 遍历所有已经记录的字符串，如果有不存在相同字符 （mask & h_mask）== 0 的字符串计算当前长度乘积
            for(const auto& [h_mask,h_len]: hash){
                if(!(mask & h_mask)){
                    ans = max(ans,wordLen*h_len);
                }
            }
        }
        return ans;
    }
};

338 比特位计数 (opens new window)

给定一个非负整数 n，求从 0 到 n 的所有数字的二进制表达中，分别有多少个 1。

输入是一个非负整数 n，输出是长度为 n + 1 的非负整数数组，每个位置 m 表示 m 的二进制里有多少个 1。

输入：n = 5 输出：[0,1,1,2,1,2] 解释：0 --> 0, 1 --> 1, 2 --> 10, 3 --> 11, 4 --> 100, 5 --> 101

解析：

​ 本题如果使用双层循环逐个统计每个数二进制表示中1的个数会出现超时的情况。为了优化可以考虑使用动态规划来解题。

​ 设置状态：使用一个一维数组dp[i]表示第 i 个数的二进制表示中 1 的个数

​ 状态转移方程：对于第 i 个数字，如果该数为奇数即其二进制表示的末位为1，那么该数二进制表示中 1 的个数直接与前一个偶数相关为dp[i]=dp[i-1]+1；如果该数为偶数即其二进制表示的末位为0，那么该数二进制表示中 1 的个数与其算术右移一位结果相同，因为其算术右移一位将末位0移出后与对应数的二进制表示一致，即dp[i]=dp[i>>1]

​ 边界条件：当 n = 0时，dp[0]=0

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1,0);
        for(int i=1;i<=n;++i){
            if(i&1){
                dp[i] = dp[i-1] + 1;
            }else{
                dp[i] = dp[i>>1];
            }
        }
        return dp;
    }
};