Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/

Intuition

Top Of The Morning Lads,

Lets begin with Bit Manipulation, finding set bits, it is. Well, firstly, if we want to approach this with sheer brute force, it would make sense to create a mask and check for each bit (it is good approach) however, if we just step back and analyse, we will realise that with AND operation over the previous element, we always get the right-most set bit. This chips off our time by a little bit (by not checking for 0's).

Approach/Pseudocode

Now for the approach:

1. INITIALISE count = 0
2. WHILE number not 0:
        SET number = number AND number - 1
        INCREASE count

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Code

class Solution {
    public int hammingWeight(int a) {
        int count = 0;
        while(a!=0){
            a = a&(a-1);
            count++;
        }
        
        return count;
    }
}

P.S. If you found this useful, please share your support with comments and claps. If you feel this can be useful to someone you know, please feel free to share this publication and story. Join my journey on DSA on my github where I am journaling all the questions I have solved and commented on: StrugglingCOderDSA.

Cheers,
Your Struggling COder;