{"id":26282,"date":"2017-10-26T20:50:23","date_gmt":"2017-10-26T15:20:23","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26282"},"modified":"2017-10-26T20:50:23","modified_gmt":"2017-10-26T15:20:23","slug":"c-programming-smallest-power-2-greater-equal-n","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-smallest-power-2-greater-equal-n\/","title":{"rendered":"C Programming-Smallest power of 2 greater than or equal to n"},"content":{"rendered":"

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>\n
There 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>\n
 1.  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>\n
Example<\/strong><\/p>\n
    Let us try for 17\r\n            pos = 5\r\n            p   = 32<\/pre>\n[ad type=”banner”]\n
Method 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>\n
Example:<\/strong><\/p>\n
    Let us try for 17\r\n                 count = 5\r\n                 p     = 32<\/pre>\n
 
 C Programming<\/span> <\/div> 
unsigned int nextPowerOf2(unsigned int n){  unsigned count = 0;   \/* First n in the below condition is for the case where n is 0*\/  if (n && !(n&(n-1)))    return n;   while( n != 0)  {    n  >>= 1;    count += 1;  }   return 1 << count;} \/* Driver program to test above function *\/int main(){  unsigned int n = 0;  printf("%d", nextPowerOf2(n));  return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Method 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
 
 C Programming<\/span> <\/div> 
unsigned int nextPowerOf2(unsigned int n){    unsigned int p = 1;    if (n && !(n & (n - 1)))        return n;     while (p < n)         p <<= 1;         return p;} \/* Driver program to test above function *\/int main(){  unsigned int n = 5;  printf("%d", nextPowerOf2(n));  return 0;}<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(lgn)<\/p>\n
[ad type=”banner”]\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>\n
Example:<\/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>\n
Program:<\/strong><\/p>\n
 
 C Programming<\/span> <\/div> 
#include <stdio.h> \/* Finds next power of two for n. If n itself   is a power of two then returns n*\/unsigned int nextPowerOf2(unsigned int n){    n--;    n |= n >> 1;    n |= n >> 2;    n |= n >> 4;    n |= n >> 8;    n |= n >> 16;    n++;    return n;} \/* Driver program to test above function *\/int main(){    unsigned int n = 5;    printf("%d", nextPowerOf2(n));    return 0;}      <\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(lgn)<\/p>\n[ad type=”banner”]\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}]}}