Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.<\/p>\n
Input : n = 5\r\n Output: 8 \r\n\r\n Input : n = 17\r\n Output : 32 \r\n\r\n Input : n = 32\r\n Output : 32<\/pre>\nThere are plenty of solutions for this. Let us take the example of 17 to explain some of them.
\nMethod 1(Using Log of the number)<\/strong><\/p>\n1. Calculate Position of set bit in p(next power of 2):\r\n pos = ceil(lgn) (ceiling of log n with base 2)\r\n 2. Now calculate p:\r\n p = pow(2, pos) \r\n<\/pre>\nExample<\/strong><\/p>\n
Let us try for 17\r\n pos = 5\r\n p = 32<\/pre>\n[ad type=\u201dbanner\u201d]\nMethod 2 (By getting the position of only set bit in result )<\/strong><\/p>\n
\/* If n is a power of 2 then return n *\/\r\n 1 If (n & !(n&(n-1))) then return n \r\n 2 Else keep right shifting n until it becomes zero \r\n and count no of shifts\r\n a. Initialize: count = 0\r\n b. While n ! = 0\r\n n = n>>1\r\n count = count + 1\r\n\r\n \/* Now count has the position of set bit in result *\/\r\n 3 Return (1 << count) \r\n<\/pre>\nExample:<\/strong><\/p>\n
Let us try for 17\r\n count = 5\r\n p = 32<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201dunsigned%20int%20nextPowerOf2(unsigned%20int%20n)%0A%7B%0A%20%20unsigned%20count%20%3D%200%3B%0A%20%0A%20%20%2F*%20First%20n%20in%20the%20below%20condition%20is%20for%20the%20case%20where%20n%20is%200*%2F%0A%20%20if%20(n%20%26%26%20!(n%26(n-1)))%0A%20%20%20%20return%20n%3B%0A%20%0A%20%20while(%20n%20!%3D%200)%0A%20%20%7B%0A%20%20%20%20n%20%20%3E%3E%3D%201%3B%0A%20%20%20%20count%20%2B%3D%201%3B%0A%20%20%7D%0A%20%0A%20%20return%201%20%3C%3C%20count%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20unsigned%20int%20n%20%3D%200%3B%0A%20%20printf(%22%25d%22%2C%20nextPowerOf2(n))%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\nMethod 3(Shift result one by one)<\/strong>
\nThanks to coderyogi for suggesting this method . This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dunsigned%20int%20nextPowerOf2(unsigned%20int%20n)%0A%7B%0A%20%20%20%20unsigned%20int%20p%20%3D%201%3B%0A%20%20%20%20if%20(n%20%26%26%20!(n%20%26%20(n%20-%201)))%0A%20%20%20%20%20%20%20%20return%20n%3B%0A%20%0A%20%20%20%20while%20(p%20%3C%20n)%20%0A%20%20%20%20%20%20%20%20p%20%3C%3C%3D%201%3B%0A%20%20%20%20%20%0A%20%20%20%20return%20p%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20unsigned%20int%20n%20%3D%205%3B%0A%20%20printf(%22%25d%22%2C%20nextPowerOf2(n))%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nTime Complexity:<\/strong> O(lgn)<\/p>\n
[ad type=\u201dbanner\u201d]\nMethod 4(Customized and Fast)<\/strong><\/p>\n
1. Subtract n by 1\r\n n = n -1\r\n\r\n 2. Set all bits after the leftmost set bit.\r\n\r\n \/* Below solution works only if integer is 32 bits *\/\r\n n = n | (n >> 1);\r\n n = n | (n >> 2);\r\n n = n | (n >> 4);\r\n n = n | (n >> 8);\r\n n = n | (n >> 16);\r\n 3. Return n + 1\r\n<\/pre>\nExample:<\/strong><\/p>\n
Steps 1 & 3 of above algorithm are to handle cases \r\nof power of 2 numbers e.g., 1, 2, 4, 8, 16,\r\n\r\n Let us try for 17(10001)\r\n step 1\r\n n = n - 1 = 16 (10000) \r\n step 2\r\n n = n | n >> 1\r\n n = 10000 | 01000\r\n n = 11000\r\n n = n | n >> 2\r\n n = 11000 | 00110\r\n n = 11110\r\n n = n | n >> 4\r\n n = 11110 | 00001\r\n n = 11111\r\n n = n | n >> 8\r\n n = 11111 | 00000\r\n n = 11111\r\n n = n | n >> 16\r\n n = 11110 | 00000\r\n n = 11111 \r\n\r\n step 3: Return n+1\r\n We get n + 1 as 100000 (32)\r\n<\/pre>\nProgram:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%20%0A%2F*%20Finds%20next%20power%20of%20two%20for%20n.%20If%20n%20itself%0A%20%20%20is%20a%20power%20of%20two%20then%20returns%20n*%2F%0Aunsigned%20int%20nextPowerOf2(unsigned%20int%20n)%0A%7B%0A%20%20%20%20n\u2013%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%201%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%202%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%204%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%208%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%2016%3B%0A%20%20%20%20n%2B%2B%3B%0A%20%20%20%20return%20n%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20unsigned%20int%20n%20%3D%205%3B%0A%20%20%20%20printf(%22%25d%22%2C%20nextPowerOf2(n))%3B%0A%20%20%20%20return%200%3B%0A%7D%20%20%20%20%20%20\u2033 message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Time Complexity:<\/strong> O(lgn)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C Programming-Smallest power of 2 greater than or equal to n – Bit Algorithm – Write a function that, for a given no n, finds a number p which is greater<\/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":[70840,70815,73135,75509,74845,74848,76420,74851,77630,75511,75517,78175,78173,70857,73778,75513,75067,71983,73134,75058,78179,70832,77628,75077,74836,70822,76421,75074,70838,74066,75066,74087,74037,74069,74828,78177,77604,76616,78176,78178,76416,70810,70836,69937,78174,78172,70826,78171,75514,75960],"class_list":["post-26282","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","category-c-programming","category-coding","tag-addition-program-in-c","tag-array-programs-in-c","tag-ascending-order-program-in-c","tag-average-in-c-programming","tag-basic-c-program-examples","tag-basic-c-programming-tutorial","tag-basic-c-programs-for-beginners","tag-basic-programs-in-c","tag-c-program-for-addition","tag-c-program-for-average-of-5-numbers","tag-c-program-for-student-details-using-structure","tag-c-program-for-sum-of-digits","tag-c-program-of-sum-of-two-numbers","tag-c-program-to-add-two-numbers","tag-c-program-to-find-power-of-a-number-using-function","tag-c-program-to-find-sum-of-n-numbers-using-function","tag-c-program-to-print-given-number-in-words","tag-c-program-to-separate-digits-of-a-number","tag-c-program-to-store-student-information-using-array","tag-c-program-using-for-loop","tag-c-programming-addition-of-two-numbers","tag-c-programming-codes","tag-c-programming-error-finding-questions-with-answers","tag-c-programming-examples-for-beginners","tag-c-programming-language-software","tag-c-programs-with-output","tag-cs-language-code","tag-example-c-program","tag-example-of-c-program","tag-for-loop-c-programming","tag-for-loop-programs-in-c","tag-how-to-write-a-program-in-c","tag-how-to-write-ac-program","tag-if-c-programming","tag-if-else-c-programming","tag-introduction-of-c-programming-language","tag-one-two-three-numbers","tag-prime-number-c-program-using-while-loop","tag-program-in-c-for-addition-of-two-numbers","tag-programs-for-c-language","tag-sample-programs-in-c","tag-simple-c-programs","tag-simple-c-programs-with-output","tag-simple-program-in-c-language","tag-some-c-programs","tag-sum-of-digits-in-c-program","tag-wap-in-c","tag-write-a-program-in-c","tag-write-ac-program","tag-write-ac-program-to-print-the-following-pattern"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26282","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=26282"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26282\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}