Write an efficient program to count number of 1s in binary representation of an integer.<\/p>\n
Examples<\/strong><\/p>\n Recommended: Please solve it on \u201cPRACTICE\u201d first, before moving on to the solution.<\/strong><\/p>\n 1. Simple Method Loop through all bits in an integer, check if a bit is set and if it is then increment the set bit count. See below program.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Function%20to%20get%20no%20of%20set%20bits%20in%20binary%0A%20%20%20representation%20of%20passed%20binary%20no.%20*%2F%0Aunsigned%20int%20countSetBits(unsigned%20int%20n)%0A%7B%0A%20%20unsigned%20int%20count%20%3D%200%3B%0A%20%20while(n)%0A%20%20%7B%0A%20%20%20%20count%20%2B%3D%20n%20%26%201%3B%0A%20%20%20%20n%20%3E%3E%3D%201%3B%0A%20%20%7D%0A%20%20return%20count%3B%0A%7D%0A%20%0A%2F*%20Program%20to%20test%20function%20countSetBits%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20i%20%3D%209%3B%0A%20%20%20%20printf(%22%25d%22%2C%20countSetBits(i))%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Time Complexity:<\/strong> (-)(logn) (Theta of logn)<\/p>\n[ad type=\u201dbanner\u201d]\n 2. Brian Kernighan\u2019s Algorithm:<\/strong> Implementation of Brian Kernighan\u2019s Algorithm:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Function%20to%20get%20no%20of%20set%20bits%20in%20binary%0A%20%20%20representation%20of%20passed%20binary%20no.%20*%2F%0Aunsigned%20int%20countSetBits(int%20n)%0A%7B%0A%20%20%20%20unsigned%20int%20count%20%3D%200%3B%0A%20%20%20%20while%20(n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20n%20%26%3D%20(n-1)%20%3B%0A%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F*%20Program%20to%20test%20function%20countSetBits%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20i%20%3D%209%3B%0A%20%20%20%20printf(%22%25d%22%2C%20countSetBits(i))%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Example for Brian Kernighan\u2019s Algorithm:<\/strong><\/p>\n Time Complexity:<\/strong> O(logn)<\/p>\n[ad type=\u201dbanner\u201d]\n 3. Using Lookup table:<\/strong> We can count bits in O(1) time using lookup table. Please see http:\/\/graphics.stanford.edu\/~seander\/bithacks.html#CountBitsSetTable for details.<\/p>\n We can find one use of counting set bits at http:\/\/www.geeksforgeeks.org\/?p=1465<\/p>\n Note:<\/strong> In GCC, we can directly count set bits using __builtin_popcount(). So we can avoid a separate function for counting set bits.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20demonstrate%20__builtin_popcount()%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20main()%0A%7B%0A%20%20%20cout%20%3C%3C%20__builtin_popcount%20(4)%20%3C%3C%20endl%3B%0A%20%20%20cout%20%3C%3C%20__builtin_popcount%20(15)%3B%0A%20%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Output :<\/strong><\/p>\n Count set bits in an integer in C Programming – Bit Algorithm – Simple Method Loop through all bits in an integer, check if bit is set and if then increment <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74852,69866,1],"tags":[77969,75890,75277,77968,75107,75898,75266,75880,75888,75082,75094,75102,75095,75099,77970,75110,75885,75889,75085,75083,75079,75088,75263,75879,75111,75109,75884,75078,75091,75878,75084,75887,75093,75270,75892,75098,75090,75886,74432,76387,75281,75089,75897,75882,75893,75096,75104,75894,75896,75100],"class_list":["post-26226","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","category-c-programming","category-coding","tag-16-bit-binary-counter","tag-16-bit-counter","tag-2-power-32-value","tag-32-bit-counter-ic","tag-32-bit-word","tag-5-bit-counter","tag-binary-operation","tag-bit","tag-bit-bit","tag-bit-bit-bit","tag-bit-counter-online","tag-bit-number","tag-bit-packing","tag-bit-table","tag-bit-test","tag-bitcount","tag-bits-bit","tag-bits-power","tag-bitset","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-bitwise-operator-in-c-example-programs","tag-bitwise-operators-in-c","tag-bs-it","tag-c-byte","tag-c-xor","tag-chacker","tag-clearbit","tag-counter-bit-set","tag-counter-set","tag-counting-bits","tag-counting-numbers","tag-cs-counter","tag-first-in-math-hack","tag-first-set-bit","tag-for-bit","tag-how-many-bits-in-a-byte","tag-html-graphics","tag-integer-numbers","tag-low-bit","tag-magic-bit","tag-nextbit","tag-number-sets","tag-population-counter","tag-python-bit","tag-python-integer-to-binary","tag-set-bit","tag-set-count","tag-set-number","tag-word-bit"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26226","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26226"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26226\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Input : n = 6\r\nOutput : 2\r\nBinary representation of 6 is 110 and has 2 set bits\r\n\r\nInput : n = 13\r\nOutput : 3\r\nBinary representation of 11 is 1101 and has 3 set bits<\/pre>\n
\nSubtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
\nBeauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.<\/p>\n 1 Initialize count: = 0\r\n 2 If<\/strong> integer n is not zero\r\n (a) Do bitwise & with (n-1) and assign the value back to n\r\n n: = n&(n-1)\r\n (b) Increment count by 1\r\n (c) go to step 2\r\n 3 Else<\/strong> return count\r\n<\/pre>\n
n = 9 (1001)\r\n count = 0\r\n\r\n Since 9 > 0, subtract by 1 and do bitwise & with (9-1)\r\n n = 9&8 (1001 & 1000)\r\n n = 8\r\n count = 1\r\n\r\n Since 8 > 0, subtract by 1 and do bitwise & with (8-1)\r\n n = 8&7 (1000 & 0111)\r\n n = 0\r\n count = 2\r\n\r\n Since n = 0, return count which is 2 now.<\/pre>\n
1\r\n4<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"