Why it can run 4ms in C++?


  • 0
    O
    int hammingWeight(uint32_t n) {
        int count = 0;
        unsigned int temp;
        for(int i=0; i<32; i++)
        {
            temp = n & (1<<i);
            if(temp > 0)
                count++;
        }
    
        return count;
    }
    

    In this code, it must loop 32 times.while in following code, it may be loop less than 32 times.why it just got 8ms? because n>>=1 costs more? Is that right? Hoping you guys help me,thank you.

    	    int hammingWeight(uint32_t n) {
    		int cnt=0;
    		for(;n;n>>=1){
    			if(n&1)cnt++;
    		}
    	return cnt;
    }

  • 0
    B

    Same as your second method in C, got 4ms.
    I think n >> 1 bitwise operation should be faster than others, can't figure it out anyway.


  • 0
    J

    A difference of 4ms does not appear to be significant in C++ on leetcode. I've had a number of problem where I would run the same code twice and runtimes different by 4ms. If you ran your a number of times, you would probably get 4ms at some point.


  • 0
    O

    Get it. Thank you.


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

    the above code takes 4ms.

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

    ;
    While the above code takes 8ms.

    The difference lies in the condition.

    Using for loops the iteration number is fixed. So the compiler simply repeat the loops for 32 times. The CPU does not need to execute the branch instruction.

    Using while(n) as loop condition the compiler does not know how many iterations will be. So CPU need to execute the branch instruction causing more overhead.


  • 0
    O

    I resubmit my second method in c++,I got 4ms. Thank you.


  • 0
    O

    I resubmit my second method in c++,I got 4ms. Thank you .


  • 0
    V

    the code with while(n) condition si faster because it will stop when you don't have any '1' in the number. For small numbers it will do only a few iterations


Log in to reply
 

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