Thread: Help with checking, raising to the power of 2

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    5

    Help with checking, raising to the power of 2

    Hi all, I am trying to raise an integer to the closest power of 2 (if already not one). Now in order to do this I first check for whether the number (say n) is power of 2. If it is , then I return. Now for doing this check I loop over integers :

    example

    Code:
    int raise(int n)
    { 
     for(int i=0;i<=n;i++) 
     { 
      temp=2**i; 
    
       if(n == temp) 
       return n; 
        
        if(temp > n) 
       { 
        n=temp; 
        return n; 
        } 
    
      } 
    }
    I was wondering whether this is the most efficient method(which I am sure isn't especially when one considers the for loop). I know that probaly bitwise operations (XOR, AND etc.) could be used for the same and would be more efficient in a way. Could someone help me improve the effieciency of this

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    to begin with:
    Code:
    temp=2**i;
    ** isn't a valid operator

    Now when you said
    raise an integer to the closest power of 2 (if already not one).
    I assume you mean round the integer up to the closest power of 2 (i.e 3 because 4, 5 becomes 8, 9 because 16, etc). Unless you build an array of integers that represent all powers of 2 there is no way to avoid some type of looping.

    An easy way would be to start from 1 ( 2 raised to 0 = 1) and keep multiplying by 2 until you reach your number or have exceeded your number.

    If you reach your number then you know its a power of 2 and if you exceed your number then you know it wasn't but you've got the next power of 2

    Quasi psuedo:
    Code:
    int raise(int n)
      temp = 1
      while ( temp < n )
        temp <- temp * 2
      return temp

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    5
    sorry I used Fortran syntax. I guess in C++/C ,can one use the pow() function instead?

    Code:
    int raise(int n)
    { 
     for(int i=0;i<=n;i++) 
     { 
      temp=pow(2,i)
      if(n == temp) 
       return n; 
        
        if(temp > n) 
       { 
        n=temp; 
        return n; 
        } 
    
      } 
    }
    but I am sure some bitwise operations could be used too...

  4. #4
    Cat Lover
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    109
    Well, you could use <<

    I'm not sure how the speed of that compares to using the pow function though.

    *edit*Fixed link*

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    5
    exactly ... how do i use say '<<' to do the same?

  6. #6
    ^ Read Backwards^
    Join Date
    Sep 2005
    Location
    Earth
    Posts
    282
    If the log of base2 to any number is a whole number...than it is a power of 2, and your result is that power of two it is. But in c++ you can not specify log base so you must use natural log to convert.
    *edit*

    Code:
    	int input;
    	cin >> input;
    
    	double math;
    
    	math = ( (log(input))/(log(2)) );
    
    	cout << math;
    That is probably the most efficent way to check if it is a power of 2.
    If it is 2, it will be a whole number (and whatever that number is, it is that power of two). You just have to check if it is a whole number.

    And if it is not a whole number, the next whole number is the next closest power of 2.

    And you can change that hardcoded 2 to any number, and it will check for that power. Or the user can input it in, ect.

    When ever you are trying to do something with powers and exponets , make sure to look into logs.
    +,-
    *,/
    exponets,logs
    Last edited by Enahs; 11-14-2005 at 08:18 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  2. Replies: 6
    Last Post: 11-08-2005, 03:05 PM
  3. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM
  4. raising to a power
    By next_to_nothing in forum C++ Programming
    Replies: 5
    Last Post: 10-22-2002, 04:00 AM
  5. Raising to a power
    By Nate2430 in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2001, 04:44 PM