⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’
Excalidraw Data
Text Elements
Q: Number of set-bits in 10
Brian Kernighan’s Algorithm
10
0 0 0 0 1 0 1 0
While (number not 0)
n = n & (n - 1) count = count + 1
return count
Algorithm:
10
0 0 0 0 1 0 1 0
Example:
Loop 1
While (10 not 0)
n = 00001010 → 10 & 00001001 → 9
count = count + 1
00001000 → 8
Count = 1
Loop 2
While (8 not 0)
n = 00001000 → 8 & 00000111 → 7
count = count + 1
00000000 → 0
Count = 2
Loop 3
While (0 not 0)
return count
Count = 2
0 is 0, so case failed.
Count = 2, This is Brian Kernighan’s Algorithm
CASE FAILED
return count
return count
Complexity:
Time Complexity : O(log n) Spaace Complexity : O(1)
Under the hood
00001010 ⇒ 10 & 00001001 ⇒ 9 = 00001000 ⇒ 8
00001001 ⇒ 9 & 00001000 ⇒ 8 = 00001000 ⇒ 8
00001000 ⇒ 8 & 00000111 ⇒ 7 = 00000000 ⇒ 0
Every n & n - 1 rightmost set-bit flips.