|
8 | 8 | * |
9 | 9 | * algorithm to count the number of set bits in a given number |
10 | 10 | * |
11 | | - * Subtraction of 1 from a number toggles all the bits (from |
12 | | - * right to left) till the rightmost set bit(including the |
| 11 | + * Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the |
13 | 12 | * rightmost set bit). |
14 | | - * So if we subtract a number by 1 and do bitwise & with |
15 | | - * itself i.e. (n & (n-1)), we unset the rightmost set bit. |
| 13 | + * So if we subtract a number by 1 and do bitwise & with itself i.e. (n & (n-1)), we unset the rightmost set bit. |
16 | 14 | * |
17 | | - * If we do n & (n-1) in a loop and count the no of times loop |
18 | | - * executes we get the set bit count. |
| 15 | + * If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count. |
19 | 16 | * |
20 | 17 | * |
21 | 18 | * Time Complexity: O(logn) |
|