{"id":26615,"date":"2017-12-21T20:41:21","date_gmt":"2017-12-21T15:11:21","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26615"},"modified":"2017-12-21T20:41:21","modified_gmt":"2017-12-21T15:11:21","slug":"c-programming-find-position-set-bit","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-find-position-set-bit\/","title":{"rendered":"C Programming Find position of the only set bit"},"content":{"rendered":"<p>Given a number having only one \u20181\u2019 and all other \u20190\u2019s in its binary representation, find position of the only set bit. Source: Microsoft Interview | 18<br \/>\n<strong>We strongly recommend that you click here and practice it, before moving on to the solution.<\/strong><br \/>\nThe idea is to start from rightmost bit and one by one check value of every bit. Following is detailed algorithm.<\/p>\n<p><strong>1)<\/strong> If number is power of two then and then only its binary representation contains only one \u20181\u2019. That\u2019s why check whether given number is power of 2 or not. If given number is not power of 2, then print error message and exit.<\/p>\n<p><strong>2)<\/strong> Initialize two variables; i = 1 (for looping) and pos = 1 (to find position of set bit)<\/p>\n<p><strong>3)<\/strong> Inside loop, do bitwise AND of i and number \u2018N\u2019. If value of this operation is true, then \u201cpos\u201d bit is set, so break the loop and return position. Otherwise, increment \u201cpos\u201d by 1 and left shift i by 1 and repeat the procedure.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20to%20find%20position%20of%20only%20set%20bit%20in%20a%20given%20number%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20whether%20n%20is%20power%20of%202%20or%20not.%20See%20http%3A%2F%2Fgoo.gl%2F17Arj%0Aint%20isPowerOfTwo(unsigned%20n)%0A%7B%20%20return%20n%20%26%26%20(!%20(n%20%26%20(n-1))%20)%3B%20%7D%0A%20%0A%2F%2F%20Returns%20position%20of%20the%20only%20set%20bit%20in%20\u2019n\u2019%0Aint%20findPosition(unsigned%20n)%0A%7B%0A%20%20%20%20if%20(!isPowerOfTwo(n))%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%0A%20%20%20%20unsigned%20i%20%3D%201%2C%20pos%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20bits%20of%20n%20till%20we%20find%20a%20set%20bit%0A%20%20%20%20%2F%2F%20i%26n%20will%20be%20non-zero%20only%20when%20\u2019i\u2019%20and%20\u2019n\u2019%20have%20a%20set%20bit%0A%20%20%20%20%2F%2F%20at%20same%20position%0A%20%20%20%20while%20(!(i%20%26%20n))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Unset%20current%20bit%20and%20set%20the%20next%20bit%20in%20\u2019i\u2019%0A%20%20%20%20%20%20%20%20i%20%3D%20i%20%3C%3C%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20increment%20position%0A%20%20%20%20%20%20%20%20%2B%2Bpos%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20pos%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20%20int%20n%20%3D%2016%3B%0A%20%20%20%20int%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%2012%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%20128%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>n = 16, Position 5\r\nn = 12, Invalid number\r\nn = 128, Position 8<\/pre>\n[ad type=\u201dbanner\u201d]\n<p>Following is <strong>another method<\/strong> for this problem. The idea is to one by one right shift the set bit of given number \u2018n\u2019 until \u2018n\u2019 becomes 0. Count how many times we shifted to make \u2018n\u2019 zero. The final count is position of the set bit.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20to%20find%20position%20of%20only%20set%20bit%20in%20a%20given%20number%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20whether%20n%20is%20power%20of%202%20or%20not%0Aint%20isPowerOfTwo(unsigned%20n)%0A%7B%20%20return%20n%20%26%26%20(!%20(n%20%26%20(n-1))%20)%3B%20%7D%0A%20%0A%2F%2F%20Returns%20position%20of%20the%20only%20set%20bit%20in%20\u2019n\u2019%0Aint%20findPosition(unsigned%20n)%0A%7B%0A%20%20%20%20if%20(!isPowerOfTwo(n))%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%0A%20%20%20%20unsigned%20count%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20One%20by%20one%20move%20the%20only%20set%20bit%20to%20right%20till%20it%20reaches%20end%0A%20%20%20%20while%20(n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20n%20%3D%20n%20%3E%3E%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20increment%20count%20of%20shifts%0A%20%20%20%20%20%20%20%20%2B%2Bcount%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20%20int%20n%20%3D%200%3B%0A%20%20%20%20int%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%2012%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%20128%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>n = 0, Invalid number\r\nn = 12, Invalid number\r\nn = 128, Position 8<\/pre>\n<p><strong>We can also use log base 2 to find the position<\/strong>.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%20%0Aunsigned%20int%20Log2n(unsigned%20int%20n)%0A%7B%0A%20%20%20return%20(n%20%3E%201)%3F%201%20%2B%20Log2n(n%2F2)%3A%200%3B%0A%7D%0A%20%0Aint%20isPowerOfTwo(unsigned%20n)%0A%7B%0A%20%20%20%20return%20n%20%26%26%20(!%20(n%20%26%20(n-1))%20)%3B%0A%7D%0A%20%0Aint%20findPosition(unsigned%20n)%0A%7B%0A%20%20%20%20if%20(!isPowerOfTwo(n))%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20return%20Log2n(n)%20%2B%201%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20%20int%20n%20%3D%200%3B%0A%20%20%20%20int%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%2012%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20n%20%3D%20128%3B%0A%20%20%20%20pos%20%3D%20findPosition(n)%3B%0A%20%20%20%20(pos%20%3D%3D%20-1)%3F%20printf(%22n%20%3D%20%25d%2C%20Invalid%20number%5Cn%22%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22n%20%3D%20%25d%2C%20Position%20%25d%20%5Cn%22%2C%20n%2C%20pos)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>n = 0, Invalid number\r\nn = 12, Invalid number\r\nn = 128, Position 8<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Programming Find position of the only set bit &#8211; Given a number having only one \u20181\u2019 and all other \u20190\u2019s in its binary representation.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[74852],"tags":[79366,79349,79354,79372,79364,79369,79371,79347,79353,79355,70190,70212,70195,75880,75082,79374,79373,79375,75085,75083,75079,79357,79361,79350,79360,75268,75078,75270,79381,75886,76288,75089,79383,75883,75086],"class_list":["post-26615","post","type-post","status-publish","format-standard","hentry","category-bit-algorithms","tag-assemble","tag-asynchronous-counter","tag-attenuator","tag-attribute","tag-authenticator","tag-autotransformer","tag-babble","tag-bandpass-filter","tag-basel-2","tag-bbs","tag-binary","tag-binary-code","tag-binary-numbers","tag-bit","tag-bit-bit-bit","tag-bit-bit-bit-bit","tag-bit-works","tag-bitmap","tag-bitset","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-black-body","tag-blink","tag-block-cipher","tag-boost-converter","tag-bytes-table","tag-clearbit","tag-first-in-math-hack","tag-hamming-code-example","tag-html-graphics","tag-logical-shift","tag-nextbit","tag-oral-positions","tag-powers-of-2","tag-xor-operator-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26615","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=26615"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26615\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26615"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26615"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26615"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}