The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
129 views
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 brian return?

asked in Programming by (145 points) | 129 views
Increment of count must be inside the loop rt?
yes,,the line upto "count=count+1" is in the loop...
okay. You may use <> in the toolbar to output code properly :)

1 Answer

+1 vote
Best answer
Each time we & a number $n$ with $(n-1)$ the 1 at the least significant bit position of the binary representation of the number changes to 0.

This is because when we subtract a 1, the least significant bit always changes. If it was 1, it changes to 0 and if it was 0, it changes to 1. If the change is 1 -> 0, no other bits are affected. So, the result of (n & (n-1)) will be $n$ with its last bit as 0. Now, if the change is 0 -> 1, this would mean all the bits to the left till the next 1 are complemented for $n-1$ (consider 8 and 7 whose binary representations are 1000  and 0111). So, when we do (n & (n-1)), all the bits towards right from the least significant 1 in the number become 0. So, in both the cases when we do (n & (n-1)), the least significant 1 changes to 0.

Thus, the above code is doing nothing other than counting the number of 1's in the binary representation of the given number. This is an efficient way as the loop runs only for $O(k)$ where $k$ is the number of 1's in the given number as compared to $O(d)$ where $d$ is the number of bits in the given number for a normal code doing the same purpose.
answered by Veteran (332k points)
selected by

Related questions

0 votes
1 answer
1
asked in Programming by radha gogia Boss (7.9k points) | 152 views
+3 votes
2 answers
2
asked in Programming by Akash Kanase Veteran (48.6k points) | 128 views
0 votes
2 answers
3
asked in Programming by radha gogia Boss (7.9k points) | 1k views


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

32,545 questions
39,231 answers
109,315 comments
36,613 users