Leetcode 338. Counting Bits

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Counting Bits

2. Solution

• Version 1

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> array;
        for(int i = 0; i <= num; i++) {
            int current = i;
            int count = 0;
            while(current) {
                current &= (current - 1);
                count++;
            }
            array.push_back(count);
        }
        return array;
    }
};

• Version 2

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> array(num + 1, 0);
        for(int i = 0; i <= num; i++) {
            array[i] = array[i >> 1] + (i & 1);
        }
        return array;
    }
};

• Version 3

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

• Version 4

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> array(num + 1, 0);
        for(int i = 1; i <= num; i++) {
            array[i] = array[i / 2] + (i % 2);
        }
        return array;
    }
};

Reference

1. https://leetcode.com/problems/counting-bits/description/