The Gateway to Computer Science Excellence

+6 votes

Consider the following code.

def brian(n): count = 0 while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1 return count

Here $n$ is meant to be an unsigned integer. The operator & considers its arguments in binary and computes their bit wise $AND$. For example, $22$ & $15$ gives $6$, because the binary (say 8-bit) representation of $22$ is $00010110$ and the binary representation of $15$ is $00001111$, and the bit-wise $AND$ of these binary strings is $00000110$, which is the binary representation of $6$. What does the function $\text{brian}$ return?

- The highest power of $2$ dividing $n$, but zero if $n$ is zero.
- The number obtained by complementing the binary representation of $n$.
- The number of ones in the binary representation of $n$.
- The code might go into an infinite loop for some $n$.
- The result depends on the number of bits used to store unsigned integers.

+8 votes

Best answer

+3 votes

Let us first understand difference between the bit patterns of N and N-1 , when N>0

Case(1): N is Even

If N is even then, we can get N-1 by complimenting all the bits from rightmost "1" to least significant bit of N's bit pattern.

Hence, N&(N-1) will have all the bits same as N except the position of N's rightmost "1"

Example- N= 1010111000 , N-1=1010110111

Now, N&(N-1) = 1010110000

Case(2): N is Odd

If N is odd then, we can get N-1 just by complementing least significant bit. Hence, N&(N-1) will have all the bits same as N except the least significant bit(which will be 0)

Example- N= 1010111001 , N-1=1010111000

Now N&(N-1)=1010111000

So, conclusion is , If C(N) denotes the number of 1s in N's bit pattern , then C(N)= C(N&(N-1)) +1

Answer C

0 votes

We can go like this

take n=1,2,3,4

we get return values as 1,1,2,1 which is equivalent to no. of 1's in its binary representation. Remaining options can simply eliminated by common sense.

U can cross check by taking n=8 which will return 1 and take n=7 which will return 3.

take n=1,2,3,4

we get return values as 1,1,2,1 which is equivalent to no. of 1's in its binary representation. Remaining options can simply eliminated by common sense.

U can cross check by taking n=8 which will return 1 and take n=7 which will return 3.

+1

@Rajesh Pradhan but here count will increment only once bcoz there is no { } present after while loop. plz verify am i correct..... while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,385 answers

198,542 comments

105,343 users