The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
450 views

What is the following function doing?

unsigned int foo(unsigned int x)
{
    unsigned int c = sizeof x;
    c <<= 3;
    if(x == 0) return c;
    c--;
    while(x = x & x-1) c--;
        return c;   
}
  1. Counting the number of bits in the binary representation of x
  2. Counting the number of set bits in the binary representation of x
  3. Counting the number of unset bits in the binary representation of x
  4. None of the above
asked in Programming by Veteran (408k points) | 450 views

1 Answer

+10 votes
Best answer
1. unsigned int foo(unsigned int x){
2.    unsigned int c = sizeof x;
3.    c <<= 3;
4.    if(x == 0) return c;
5.    c--;
6.    while(x = x & x-1) c--;
7.    return c;   
8. }

line no 2 : c = no of bytes for x.
line no 3 : c<<=3 is c*8 which is converting Byte into bits.
line no 6 : counting no of 1s and decrementing c value by 1.
c will be decremented as many times as no of 1s will be in x.
line no 7 : return c i.e. no of 0s or no of Unset bit in x.
answered by Veteran (59.8k points)
edited by
0
 c<<=3 is c*8 which is converting Byte into bits.

did not understand the above line .. 

According to me it should be,

line 3 = > c= 4     // by default  sizeof(int)= 4
 

line 4 => c = c << 3 = c * 8 = 4* 8 = 32

 

0
size of int depends on machine. By default is 4 ? No.
0
okay sir, but sir please explain line no 4 ??
0
plz explain line no 7.
0

just to clear self doubt-

bool isPowerOfTwo(int x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

In this code will the time complexity be O(1) or O(log X), since there are log X bits to evaluate and its bitwise??

+9

Logic behind no of set bits and decrement of c

+1
line no 4 : c<<=3 is c*8 which is converting Byte into bits.
line no 6 : decrementing c because while will run only k-1 times, where k is no of 1s in x
line no 7 : counting no of 1s and decrementing c value by 1.
c will be decremented k-1 times, where k is no of 1s in x.
so overall after while loop, total no of 1s in x will be subtracted from c
line no 8 : return c i.e. no of 0s or no of Unset bit in x.

Isn't it?

+2
@Sushmita yes, it should be $O(\log n)$ in worst case where all bits are 1. But we can more precisely say it as $O(k)$, where $k$ is the number of 1's in the input.
0
thanx a lot.
0
can u plz explain line no.7 how its counting no. of 1's

what actually while loop is doing
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,588 questions
54,197 answers
187,535 comments
71,152 users