|
| 1 | +importjava.util.Scanner; |
| 2 | + |
| 3 | +/** |
| 4 | + * |
| 5 | + * @author Nishita Aggarwal |
| 6 | + * |
| 7 | + * Brian Kernighan’s Algorithm |
| 8 | + * algorithm to count the number of set bits in a given number |
| 9 | + * Subtraction of 1 from a number toggles all the bits (from |
| 10 | + * right to left) till the rightmost set bit(including the |
| 11 | + * rightmost set bit). |
| 12 | + * So if we subtract a number by 1 and do bitwise & with |
| 13 | + * itself (n & (n-1)), we unset the rightmost set bit. |
| 14 | + * If we do n & (n-1) in a loop and count the no of times loop |
| 15 | + * executes we get the set bit count. |
| 16 | + * Number of iterations of the loop is equal to the number of |
| 17 | + * set bits in a given integer. |
| 18 | + * |
| 19 | + * Time Complexity: O(logn) |
| 20 | + * |
| 21 | + */ |
| 22 | + |
| 23 | + |
| 24 | +publicclassBrianKernighanAlgorithm { |
| 25 | + |
| 26 | +/** |
| 27 | + * @param num: number in which we count the set bits |
| 28 | + * |
| 29 | + * @return int: Number of set bits |
| 30 | + * */ |
| 31 | +staticintcountSetBits(intnum) |
| 32 | +{ |
| 33 | +intcnt =0; |
| 34 | +while(num !=0) |
| 35 | +{ |
| 36 | +num =num & (num-1); |
| 37 | +cnt++; |
| 38 | +} |
| 39 | +returncnt; |
| 40 | +} |
| 41 | + |
| 42 | + |
| 43 | +/** |
| 44 | + * |
| 45 | + * @param args : command line arguments |
| 46 | + * |
| 47 | + */ |
| 48 | +publicstaticvoidmain(Stringargs[]) |
| 49 | +{ |
| 50 | +Scannersc =newScanner(System.in); |
| 51 | +intnum =sc.nextInt(); |
| 52 | +intsetBitCount =countSetBits(num); |
| 53 | +System.out.println(setBitCount); |
| 54 | +sc.close(); |
| 55 | +} |
| 56 | +} |