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?

  1. The highest power of $2$ dividing $n$, but zero if $n$ is zero.
  2. The number obtained by complementing the binary representation of $n$.
  3. The number of ones in the binary representation of $n$.
  4. The code might go into an infinite loop for some $n$.
  5. The result depends on the number of bits used to store unsigned integers.
in Algorithms by Boss (30.8k points)
edited by | 450 views

3 Answers

+8 votes
Best answer

Option C. It returns no of 1's in binary representation of $n$.
Here, $n$&$(n-1)$ reset rightmost bit of $n$ in each iteration.

For example,

Suppose $n=15=00001111$(binary)


  $ 00001111$ 
^  $00001110$

by Active (3.1k points)
edited by
option C  .. u have solved for option c ... saying option B . plz check
corrected that.
didnt understand it. please explain. how it is giving no. of 1s?
+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

by Active (3k points)
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.
by Boss (23.9k points)
@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
Yes true.. Count will only increment one time

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
50,737 questions
57,385 answers
105,343 users