CountingBits.cpp

//Given a non negative integer number num.For every numbers i in the range 0 ¡Ü i ¡Ü num calculate the number of 1's in their binary representation and return them as an array.
//
//Example:
//For num = 5 you should return[0, 1, 1, 2, 1, 2].
//
//Follow up :
//
//It is very easy to come up with a solution with run time O(n*sizeof(integer)).But can you do it in linear time O(n) / possibly in a single pass ?
//Space complexity should be O(n).
//Can you do it like a boss ? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

#include<vector>
#include<iostream>

using namespace std;

//Given an integer, write a function to determine if it is a power of two.



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

};


void main_CountingBits()
{
	int x = -16;
	CountingBits nb;

	//cout << nb.countBits(x) << endl;



}