edited by
2,168 views
8 votes
8 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 $\text{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 $\text{AND}$ of these binary strings is $00000110$, which is the binary representation of $6$. What does the function $\textsf{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.
edited by

3 Answers

Best answer
9 votes
9 votes

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)

$n-1=14(00001110)$

  $ 00001111$ 
^  $00001110$
---------------------
   $00001110$

edited by
5 votes
5 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

1 votes
1 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.
Answer:

Related questions

49 votes
49 votes
7 answers
4