{"id":25990,"date":"2017-10-26T09:22:27","date_gmt":"2017-10-26T03:52:27","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25990"},"modified":"2017-10-26T09:22:27","modified_gmt":"2017-10-26T03:52:27","slug":"find-whether-given-number-power-4-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-whether-given-number-power-4-not\/","title":{"rendered":"Find whether a given number is a power of 4 or not"},"content":{"rendered":"<p><strong>We strongly recommend that you click here and practice it, before moving on to the solution.<\/strong><\/p>\n<p>1. A simple method is to take log of the given number on base 4, and if we get an integer then number is power of 4.<\/p>\n<p>2. Another solution is to keep dividing the number by 4, i.e, do n = n\/4 iteratively. In any iteration, if n%4 becomes non-zero and n is not 1 then n is not a power of 4, otherwise n is a power of 4.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23define%20bool%20int%0A%20%0A%2F*%20Function%20to%20check%20if%20x%20is%20power%20of%204*%2F%0Abool%20isPowerOfFour(int%20n)%0A%7B%0A%20%20if(n%20%3D%3D%200)%0A%20%20%20%20return%200%3B%0A%20%20while(n%20!%3D%201)%0A%20%20%7B%20%20%20%20%0A%20%20%20if(n%254%20!%3D%200)%0A%20%20%20%20%20%20return%200%3B%0A%20%20%20%20n%20%3D%20n%2F4%3B%20%20%20%20%20%20%0A%20%20%7D%0A%20%20return%201%3B%0A%7D%20%0A%20%0A%2F*Driver%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20int%20test_no%20%3D%2064%3B%0A%20%20if(isPowerOfFour(test_no))%0A%20%20%20%20printf(%22%25d%20is%20a%20power%20of%204%22%2C%20test_no)%3B%0A%20%20else%0A%20%20%20%20printf(%22%25d%20is%20not%20a%20power%20of%204%22%2C%20test_no)%3B%0A%20%20getchar()%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>3. A number n is a power of 4 if following conditions are met.<br \/>\na) There is only one bit set in the binary representation of n (or n is a power of 2)<br \/>\nb) The count of zero bits before the (only) set bit is even.<\/p>\n<p>For example: 16 (10000) is power of 4 because there is only one bit set and count of 0s before the set bit is 4 which is even.<\/p>\n<p>Thanks to Geek4u for suggesting the approach and providing the code.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23define%20bool%20int%0A%20%0Abool%20isPowerOfFour(unsigned%20int%20n)%0A%7B%0A%20%20int%20count%20%3D%200%3B%0A%20%0A%20%20%2F*Check%20if%20there%20is%20only%20one%20bit%20set%20in%20n*%2F%0A%20%20if%20(%20n%20%26%26%20!(n%26(n-1))%20)%0A%20%20%7B%0A%20%20%20%20%20%2F*%20count%200%20bits%20before%20set%20bit%20*%2F%0A%20%20%20%20%20while(n%20%3E%201)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20n%20%20%3E%3E%3D%201%3B%0A%20%20%20%20%20%20%20count%20%2B%3D%201%3B%0A%20%20%20%20%20%7D%20%20%20%20%20%20%0A%20%0A%20%20%20%20%2F*If%20count%20is%20even%20then%20return%20true%20else%20false*%2F%0A%20%20%20%20return%20(count%252%20%3D%3D%200)%3F%201%20%3A0%3B%0A%20%20%7D%0A%20%0A%20%20%2F*%20If%20there%20are%20more%20than%201%20bit%20set%0A%20%20%20%20then%20n%20is%20not%20a%20power%20of%204*%2F%0A%20%20return%200%3B%0A%7D%20%20%20%20%0A%20%0A%2F*Driver%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20int%20test_no%20%3D%2064%3B%0A%20%20%20if(isPowerOfFour(test_no))%0A%20%20%20%20%20printf(%22%25d%20is%20a%20power%20of%204%22%2C%20test_no)%3B%0A%20%20%20else%0A%20%20%20%20%20printf(%22%25d%20is%20not%20a%20power%20of%204%22%2C%20test_no)%3B%0A%20%20%20getchar()%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Find whether a given number is a power of 4 or not &#8211; Bit Algorithm &#8211; A simple method is to take log of the given number on base 4, and if we get an integer.<\/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],"tags":[76458,76440,76449,76445,76465,76438,76475,76473,76466,76479,76454,76441,76472,76455,76476,76480,76456,76469,76467,76481,76446,76436,76451,76461,76457,76459,76464,76448,74025,76443,76453,76444,76471,76437,76478,76442,76470,76463,76450,76439,76460,75883,76468,76474,76477,76482,76462,76435,76452,76447],"class_list":["post-25990","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","tag-0-power","tag-0-power-0","tag-10-2-math","tag-10-power-0","tag-16-power-of-2","tag-2-power","tag-2-power-1-2","tag-2-power-14","tag-2-power-2","tag-2-power-31","tag-2-power-4","tag-2-power-6","tag-2-power-64","tag-2-power-7","tag-2-power-8-value","tag-2-power-of-2","tag-2-power-of-4","tag-2-to-power","tag-2-to-power-10","tag-2-to-the-negative-3rd-power","tag-2-to-the-power-of","tag-2-to-the-power-of-6","tag-3-power-6","tag-3-to-the-0-power","tag-4-power-2","tag-8-to-the-3rd-power","tag-all-powers-of-2","tag-definition-of-power-in-math","tag-how-to-calculate-the-power-of-a-number","tag-math-power","tag-power-0","tag-power-2","tag-power-calculator-math","tag-power-math","tag-power-math-example","tag-power-numbers","tag-power-of-2-in-c-programming","tag-power-of-2s","tag-power-of-one","tag-power-raised-to-a-power","tag-power-to-2","tag-powers-of-2","tag-to-the-0-power","tag-to-the-2-power","tag-two-power","tag-what-is-2-to-the-power-of-6","tag-what-is-5-to-the-3rd-power","tag-x-power-2","tag-x-power-3","tag-x-to-the-power-of-4"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25990","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=25990"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25990\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25990"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25990"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25990"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}