A 3ms solution in C


  • 1
    G

    My first solution (6ms):

    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n > 0) {
            uint32_t m = n - 1;
            n = m & n;
            ++count;
        }
        return count;
    }
    

    Using register variable to improve the first solution (4ms):

    register int count = 0;
        register uint32_t a = n;
        while (a > 0) {
            a &= (a - 1);
            ++count;
        }
        return count;
    }
    

    finally, get a good balance between time complexity and space complexity (3ms):

    int hammingWeight(uint32_t n) {
        int map[] = {0, 1,  1, 2,   1, 2, 2, 3,   1, 2, 2, 3, 2, 3, 3, 4};
        register int count = 0;
        register uint32_t a = n;
        while (a > 0) {
            count += map[0xf & a];
            a >>= 4;
        }
        return count;
    }

  • 0
    H

    Better than mine. I also use table lookup but I got a "4ms"


Log in to reply
 

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