LooetCode Q191: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

My solution: Time complexity O(1) it counts entire 32 bits.

	class Solution {
	public:
	int hammingWeight(uint32_t n) {
	int res=0;
	for(int i=0; i<32; i++)
	res+= (n>>i)&1;
	return res;
	}
	};

view raw Q191Numberof1Bits.cpp hosted with ❤ by GitHub

Optimal solution: Although the time complexity is also O(1), it takes k steps to finish, where k is the number of 1s in int. The idea is to remove an 1 at a time. The trick is: An elegant way to check is an integer has exactly one bit set to 1. Given integer say int i=k, we could check if (i & (i-1))==0, if true then only one bit is 1 in i. In the same time (i & (i-1))==0 actually check if number i is a power of 2.

	class Solution {
	public:
	int hammingWeight(uint32_t n){
	int res = 0;
	while(n)
	{
	n &= n - 1;
	++ res;
	}
	return res;
	}
	};

view raw Q191-2.cpp hosted with ❤ by GitHub