LCR003.比特位计数

剑指offer（专项突破版）1.2 二进制

题目链接：LCR003-比特位计数

方法1：借鉴两数相除题目的思想

分析：一种直接的想法是先将0-n之间的每个数的二进制表示求出来，再数其中1的个数，但这样循环次数过多，应该会超时。于是想到可以借鉴LCR001-两数相除这道题的思想。

//自己第一次写的代码
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vec(n+1,0);
        //对于每个数字i
        for(int i = 0;i <= n;i++){
            int num = i;
            while(num > 0){
                int j;
                for(j=1;j <= num;){
                    j += j;
                }
                num -= j/2;
                vec[i]++;
            }
        }
        return vec;
    }
    
};

时间复杂度分析：

外层循环for(int i = 0;i <= n;i++)遍历了从0到n的所有数字，因此时间复杂度为O(n)。
内层循环使用了一个while循环和一个for循环：
- while循环中，每次将num除以2，直到num变为0。最坏情况下，这个过程需要O(logn)次操作。
- for循环中，每次将j乘以2，直到j超过num。因此，这个循环的时间复杂度也是O(logn)。
  
  因此，内层循环的时间复杂度可以视为O(logn)。

整体来看，外层循环的时间复杂度是O(n)，内层循环的时间复杂度是O(logn)。由于内层循环是在外层循环内部执行的，所以内层循环的总时间复杂度是O(nlogn)。

结果：

方法2：简单计算每个整数的二进制形式中1的个数

计算整数i的二进制形式中1的个数有多种不同的方法，其中一种比较高效的方法是每次用“i&（i-1）”将整数i的最右边的1变成0。整数i减去1，那么它最右边的1变成0。如果它的右边还有0，则右边所有的0都变成1，而其左边所有位都保持不变。下面对i和i-1进行位与运算，相当于将其最右边的1变成0。

时间复杂度分析： 每次将最右边的1变成0，直到这个数变为0。如果一个整数共有k位，那么它的二进制形式中可能有O（k）个1。在上述代码中，while循环中的代码对每个整数将执行O（k）次，因此，上述代码的时间复杂度是O（nk）。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vec(n+1,0);
        //对于每个数字i
        for(int i = 0;i <= n;i++){
            int j = i;
            while(j != 0){
                vec[i]++;
                j = j & (j-1);
            }
        }
        return vec;
    }
};

结果：

方法3：根据“i&（i-1）”计算i的二进制形式中1的个数

根据前面的分析可知，“i&（i-1）”将i的二进制形式中最右边的1变成0，也就是说，整数i的二进制形式中1的个数比“i&（i-1）”的二进制形式中1的个数多1。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vec(n+1,0);
        //对于每个数字i
        for(int i = 1;i <= n;i++){
            vec[i] = vec[i & (i-1)] + 1;
        }
        return vec;
    }
};

时间复杂度分析： 不管整数i的二进制形式中有多少个1，上述代码只根据O（1）的时间就能得出整数i的二进制形式中1的数目，因此时间复杂度是O（n）。

结果：

方法4：根据“i/2”计算i的二进制形式中1的个数

如果正整数i是一个偶数，那么i相当于将“i/2”左移一位的结果，因此偶数i和“i/2”的二进制形式中1的个数是相同的。如果i是奇数，那么i相当于将“i/2”左移一位之后再将最右边一位设为1的结果，因此奇数i的二进制形式中1的个数比“i/2”的1的个数多1。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vec(n+1,0);
        //对于每个数字i
        for(int i = 1;i <= n;i++){
            if(i % 2 == 0){
                vec[i] = vec[i/2];
            }   //i是偶数  
            else{
                vec[i] = vec[i/2] + 1;
            }   //i是奇数
        }
        return vec;
    }
};

时间复杂度分析： O（n）。

结果：

书上的代码使用“i>>1”计算“i/2”，用“i&1”计算“i%2”，因为位运算比除法运算和求余运算更高效。这个题目是关于位运算的，因此应该尽量运用位运算优化代码。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vec(n+1,0);
        //对于每个数字i
        for(int i = 1;i <= n;i++){
            vec[i] = vec[i >> 1] + (i & 1);
        }
        return vec;
    }
};