Hi!
Could anyone give me a good method to round an int up to the nearest power of two. I'm working on a buddy system memory allocation program.
Thanks!!

 

 

public int round(int i)
{
    if(i%2 != 0) i++;
 
    return i;
 
}

This will take in an int and test if it's evenly divisible by two. If not, it's gonna increment it by one. If it already is, well then it's already rounded to the closest power of two.

 

 

Ack... sorry.. I completely misread that. I was thinking multiple of two. That would be easier ;)

 

 

public int round(int i)
{
 
int power = 2;
while(i > power)
{
     power *= 2;
}
 
return power;
 
}

Try that... seems like it should work to me.

 

 

what does *= do?? I have never seen that construct before.

 

 

use java.lang.Integer

Sting bits = Integer.toBinaryString();
int power = bits.length() - bits.indexOf("1");
int answer = 2 * power;

 

 

= works just like += ... a = b is just a shorthand notation for a = a*b

 

 

a = 2

It is read something like

a times by two and assigned new value.

= times/multipilcation

= = assign.


So if you ever se a combination like that again, you'll know what it means.

-=      = minus and assign resulting value

=     = add and assign resulting value

/=      = divide and assign resulting value

=      = multiply and assign resulting value



--       =  decrease int by one and assign resulting value.

+     =  increase by one and assign resulting value



<<     = shift binary value x position to the right



        EXAMPLE:



        8 = 1000

        2 = 10



        8 << 2 =  2



        BECAUSE:



        1000 binary shifted to difits left (means all digits left are deleted) is 10

= works the opposite way as <<. (8 >> 1 = 64)

That is a brief overview of all operators. I was just going to explain the = but I got to carried away! ;^)

Virum

 

 

Neither of the suggested solutions will work for negative numbers or for integers greater than 2^30. If you can constrain the problem in that way, then either will work fine, however in znerladivad, the final line should be
int answer = Math.pow(2,power)
rather than using multiplication. The String solution is nifty, but should have a bit of documentation to explain why it is that you're changing the int to a string.
We know that if you left shift the int by 1 bit, then the answer is between the input and the result.
int upperBound = intVal << 1;
but I can't see how to determine the exact value.

 

 

Does it look better?

long answer;
int i=Integer.parseInt(args[0]);
if(i<-1) {
 answer=(long)(Math.pow(2,Double.NEGATIVE_INFINITY));
} else {
 String bits=Long.toBinaryString((long)i);
 int exp=bits.length()-bits.indexOf("1");
 long upper=(long)Math.pow(2,exp);
 long lower=(long)Math.pow(2,exp-1);
 answer=(upper-i)>(i-lower)?lower:upper;
}

 

 

a version that doesn't use String(or even long :~/ ) would be nice... I'll have a go 2night.

rob,

 

 

ooops....

long answer;
int i=Integer.parseInt(args[0]);
if(i<0) { // error, was -1
  answer=0;
  // of course, it's the same of the (formally more correct)
  // answer=(long)(Math.pow(2,Double.NEGATIVE_INFINITY));
} else {
  String bits=Long.toBinaryString((long)i);
 int exp=bits.length()-bits.indexOf("1");
 long upper=(long)Math.pow(2,exp);
 long lower=(long)Math.pow(2,exp-1);
 answer=(upper-i)>(i-lower)?lower:upper;
}
 

 

 

Not using strings... and if you are not afraid of overflows, neither longs :-)

int answer;
if(i<0) answer=0;
else {
 int exp=0;
 for(int iTmp=i; (iTmp>>=1) >0; exp++);
 int upper=1<<exp+1;
 int lower=1<<exp;
 answer=(upper-i)>(i-lower)?lower:upper;
}

 

 

I was trying to be clever and I was close.

I was thinking there was a quick answer with a mask in there some how, but haven't figured it out. And-ing a simple mask should make everything all ones and add 1 to that value and you've got it.

 

 

Disregard that last entry....