LeedCode: Number of 1 bits

Question:

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.

Analysis:

This is a simple problem. Two ways: Either shifting the number to the right one bit per time and then AND with 0x1 and count the number of 1 for each AND operation. Or shifting the 0x1 left one bit per time and AND with the number. Then count the number of non-zero of the AND operation.

C++:

int hammingWeight(uint32_t n) {

        int res=0;

        int x=0x1;

        for(int i=0; i<sizeof(uint32_t)*8; i++){

            if((n&x)!=0)

                res++;

            x<<=1;

        }

        return res;

}

    

int hammingWeight2(uint32_t n) {

        int res=0;

        for(int i=0; i<sizeof(uint32_t)*8; i++){

            if((n&0x1)==1)

                res++;

            n>>=1;

        }

        return res;

}


Cost:
O(1)