Solutions for both O(log(32)) and O(32), your choice


  • 3
    W
    //worst time O(log(32)), space O(1)
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
        	n = ((n>>(1<<0)) & 0x55555555) + (n & 0x55555555); //count 1bit of adjacent 2 bits
        	n = ((n>>(1<<1)) & 0x33333333) + (n & 0x33333333); //count 1bit of adjacent 4 bits
        	n = ((n>>(1<<2)) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); //count 1bit of adjacent 8 bits
        	n = ((n>>(1<<3)) & 0x00FF00FF) + (n & 0x00FF00FF); //count 1bit of adjacent 16 bits
        	return ((n>>(1<<4)) & 0x0000FFFF) + (n & 0x0000FFFF); //count 1bit of adjacent 32 bits
        }
    };
    
    
    
    //worst time O(32), space O(1)
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int ret=0;
            while(n)
            {
            	++ret;
            	n&=(n-1);
            }
            return ret;
        }
    };

  • 0
    C

    could you please give a brief explain on how does the first solution work?


  • 2
    Y

    It's a divide and conquer method.
    First we compute “number of 1bits” in adjacent 2 bits, then 4bits, 8bits, 16bits, finally 32 bits.

    Let's take an 8 bit unsigned number as example:
    The original 8 bit number n is 90, which is '01011010' in binary format. There are 3 steps:

    0  | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
    1  |     01|     01|     01|     01|
    2  |           0010|           0010|
    3  |                       00000100|
    

    Line 0 is the original number.
    Line 1: we add up every two adjacent bits, so the result is "number of 1s in every 2 bits".
    Line 2: Every four adjacent bits, 01 + 01 = 10, 01 + 01 = 10.
    Line 3: 8bits, 0010 + 0010 = 0100, so the final answer is 4.

    The computation of Line 1:
    Compute adjacent 2 bits, we use a mask number '01010101' (0x55)

       01 01 10 10
    &  01 01 01 01 
    =  01 01 00 00   ---- (1)
    

    right shift n by 1 bit, so we can deal with the adjacent bit

       00 10 11 01  
    &  01 01 01 01  
    =  00 00 01 01   ---- (2)  
    

    then we add up (1) and (2):

    n = 01 01 01 01  
    

    Line 2 and 3 are similar, but they have different mask numbers and shift values.
    for 8 bit number, the mask numbers are:

    01010101 (0x55)
    00110011 (0x33)
    00001111 (0x0f)

Log in to reply
 

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