450 views

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.

edited | 450 views

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$

by Active (3.1k points)
edited
0
option C  .. u have solved for option c ... saying option B . plz check
0
corrected that.
0
didnt understand it. please explain. how it is giving no. of 1s?

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

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