697 views
3 votes
3 votes
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?

1 Answer

Best answer
3 votes
3 votes
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.
selected by

Related questions

2 votes
2 votes
3 answers
2
Laahithyaa VS asked Sep 9, 2023
895 views
. What will be the value returned by the following function, when it is called with 11?recur (int num){if ((num / 2)! = 0 ) return (recur (num/2) *10+num%2);else return 1...
0 votes
0 votes
1 answer
3
radha gogia asked Jul 26, 2015
2,554 views
#include <stdio.h void e(int); int main() { int a = 3; e(a); putchar('\n'); return 0; } void e(int n) { if (n 0) { e( n); printf("%d ", n); e( n); } }I am not getting he...
1 votes
1 votes
2 answers
4