My accepted 1ms c solution


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

  • 3
    Z

    I've run it. my result is 20ms.

    I think it should not be better than this:

            int ret = 0;
        while(n>0) {
            ret += n&1;
            n >>= 1;
        }
        return ret;
    

    >> is faster than a minus operation


  • 0
    R

    My solution is faster than yours in the average case. You can test both solutions with following codes:

    #include <stdint.h>
    #include <stdio.h>
    #include <time.h>

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

    return count;
    

    }

    int hammingWeightAlt(uint32_t n){
    int ret = 0;
    while(n>0) {
    ret += n&1;
    n >>= 1;
    }
    return ret;
    }

    void main(){
    clock_t t1, t2;

    t1 = clock();
    for (int i = 1; i < (1 << 24); i++) {
    	hammingWeightAlt((1 << 30) - (1 << 10));
    }
    t1 = clock() - t1;
    printf("hammingWeightAlt took %d ticks\n", t1);
    
    t1 = clock();
    for (int i = 1; i < (1 << 24); i++) {
    	hammingWeight((1 << 30) - (1 << 10));
    }
    t1 = clock() - t1;
    printf("hammingWeight took %d ticks\n", t1);
    
    return;
    

    }

    You can see that there are more 1 than 0 in each case(20 versus 12), while, the result shows that my solution is faster:
    hammingWeightAlt took 1320000 ticks
    hammingWeight took 1100000 ticks

    I tested the code under Solaris. You can try that under other platforms.


Log in to reply
 

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