Naive Solution for Hamming Weight


  • 0
    D

    This is a naive solution, taken from wiki. More on : https://en.wikipedia.org/wiki/Hamming_weight

    class Solution {
    public:
    
        const uint64_t m1  = 0x5555555555555555; //binary: 0101...
        const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
        const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
        const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
        const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
    
        //This is a naive implementation, shown for comparison,
        //and to help in understanding the better functions.
        //It uses 24 arithmetic operations (shift, add, and).
        int hammingWeight(uint32_t x) {
            x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
            x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
            x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
            x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
            x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
            return x;
        }
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.