Number of 1 bits GFG Practice

Problem Link:

https://practice.geeksforgeeks.org/problems/set-bits0143/1

Solution:

int count=0;

        int a=0;

        while(n!=0){

            a=n%2;

            if(a==1){

                ++count;

            }

            n=n/2;

            //n=n>>1 (you can use this statement also in place of n=n/2 as every time n is divided by 2)

        }

        return count;

TIME:O(Total bits in given number)[GFG Time:0.2/1.3]

SPACE:O(1)

AUXILLARY SPACE:O(1)

Total Test Cases:150

Approach :

Here we will convert the number into binary and check for each digit from last. If the digit is 1 then increment the counter variable count else value of the count variable remains the same.

Return count;

--------------------------------------------------------------------------------------------------------------------------

int count=0;

        int a=0;

        while(n!=0){

            

            if((n&1)==1){

                ++count;

            }

            //n=n/2;

            n=n>>1;

        }

        return count;

Time:O(Total digits in number)[GFG Time:0.2]

Space:O(1)

Auxillary Space:O(1)

Approach :

We directly check whether the mask is 1 or not. (We check this by taking and with 1 and if the last bit is 1 then we increment the counter value. )

eg if n=7 then binary representation is 111

7&1= 111&001 all bits except the last will be 0 and hence last bit nature depended on the given number.

If the last bit is 1 count++, else no increment.

-----------------------------------------------------------------------------------------------------------------------------

int count=0;

        int a=0;

        while(n!=0){

            

            count=count+(n&1);

            //n=n/2;

            n=n>>1;

        }

        return count;

Time:O(Total digits in number)[GFG Time:0.2]

Space:O(1)

Auxillary Space:O(1)

Approach:

Directly calculate the mask value and add in the count. If 0 then no increment in count else increase by 1.

(Modification of 2 Approach discussed above)

-----------------------------------------------------------------------------------------------------------------------------

Effecient Solution:

 Brian Kerningams algo

        int count=0;

        while(n!=0){//n>0

            n=n&(n-1);

            count++;

        }

        return count;

Time:O(Total 1's in number)[GFG Time:0.2]

Space:O(1)

Auxillary Space:O(1)

Approach:

1. Take mask between n and n-1.

2. Do this till n!=0 or n>0

3. Increment the counter every time because this loop will run the same number of times equal to  1's present in the given number.

example 

if n=7 then binary 111

n-1= 6 ie 110

first iteration--------------(n>0)

111 & 110 ie 110 

new value of n=110

count=1

Second iteration----------(n>0)

110 & 101(decimal 5)= 100

new value of n=100

count=2

Third iteration---------------(n>0)

100 & 011(decimal 3)=000

new value of n=000

count=3

Hence n=0 loop break;

return count ie 3

Second Example 

n=32 ie 10000

n-1=31 ie 01111

n&(n-1)= 10000&00001=00000

count=1;

Since n=0 loop break;

So total number of times loop run is the number of 1 present in the binary representation of the given number.

for 32 it is 1 and for 7 it is 3.

-----------------------------------------------------------------------------------------------------------------------------

Efficient Solution Using Loop Table Method:

int count=0;

        int table[]=new int[256];

        for(int i=1;i<256;i++){

            table[i]=(i&1)+table[i/2];

        }

        count=table[n&0xff];

       n= n>>8;

        count=count+table[n&0xff];

       n= n>>8;

        count=count+table[n&0xff];

       n= n>>8;

        count=count+table[n&0xff];

        return count;*/

        

        

 Time:O(1)[GFG Time:0.2]

Space:O(1)

Auxillary Space:O(An Array for 256 bits ie O(256 integers). Moreover there will be recursive calls so the stack will be maintained. Maximum height of stack at any time will be O(Log n) n is number).

Approach:

Here we use the concept of storing and then using.

First of all, we will divide 32-bit numbers into 4 chunks of 8 bits each. 

And we know for each chunk the value ranges from 1 (when the last bit is 1) to 255(when except MSB all are 1).

So we store all the occurrences of 1 from 1(inclusive) to 255(inclusive). 

ex for 1 it is 1(00000001)

for 2 it is 1(00000010)

for 3 it is 2(00000011)

Similarly, for 255, it is 7(01111111)

No, we store all this information in an array named table.

HOW STORE AND USE APPROACH IS USED?

We calculate the value of new results from the previous results. ie

for 2 we use (2&1)+table[2/2]  ----------------------------->     0+table[1]---------------------------> 0+1 ie 1

for 3 we use (3&1)+table[3/2]--------------------------------------> 1+table[1]------------------------>1+1 ie 2

for 7 we use (7&1)+table[7/2]-----------------------------> 1+table[3]--------------------->1+2 ---------> 3

In same way we calucluate the value of all i from 1 to 256(exclusive)

 

Now traversing, 

We will traverse 32-bit numbers in a chunks manner.

The last chunk will be traversed first then the second last chunk and in the same way till the last chunk. (LSB TO MSB)

Then we will mask the number with the maximum value ie when all are 1 except MSB ie 255 and store that value in res.

Now we will shift n to right by 8 bits using n>>8.

Then calculate the value(n&0xff) and append it in the earlier value of res.

We will do this shift 3 times after that number will become 00000000 or 11111111. It actually depends on the nature of a given number. If it is positive then after every shift 0's will be added else 1 will be added.

In last we return res.

For 64 bit numbers, Chunks will be 8 or 8 bits each 

The array will be the same.

Traversal will be in the same manner but the shifting will occur 3+4 times ie 7 times.

Number of Shifts=[(32/8)or(64/8)]-1 === either 3 or 7.

-----------------------------------------------------------------------------------------------------------------------------

       // Direct Function In Java

        int count=0;

        String s=Integer.toBinaryString(n);

        for(int i=0;i<s.length();i++){

            if(s.charAt(i)=='1'){

                ++count;

            }

        }

        return count;

Time:O(Total digits in number)[GFG Time:0.2]

Space:O(1)

Auxillary Space:O(1)

Approach:

Here we will convert number to string using an inbuilt operation by java.

Later traverse the string and calculate the number of 1's present.

return count.

-----------------------------------------------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"