Commitdcfde17

authored

Merge pull requestTheAlgorithms#367 from NISHITA97/Branch2

Brian Kernighan’s Algorithm added

2 parents05efd17 +1567b58 commitdcfde17Copy full SHA for dcfde17

File tree

+55

-0

lines changed

+55

-0

lines changed

Lines changed: 55 additions & 0 deletions

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

Comments

(0)