给定一个非负整数num,如何不用循环语句,返回>=num,并且离num最近的,2的某次方
题目描述
给定一个非负整数num,如何不用循环语句,返回>=num,并且离num最近的,2的某次方
题目分析
假设有一个数n,它的二进制位表示如下:
那么n = n ∣ ( n > > 1 ) ,得到如下:
因此,下面代码的意思是:
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
对于数temp,它的二进制表示从最高位的1开始全部变1
为什么只需要算到16,因为整型只有32位。
如果是long类型,那么多一个 n|= n>> 32;即可
举个例子:
如果 n = 13 ,那么它的二进制是:
然后x = n - 1,x的二进制为:
举个例子:
如果 n = 16,那么它的二进制是:
然后对x进行或操作,将最高位开始全部变1,得到y=
代码实现
public class Near2Power {
public static int tableSizeFor(int n) {
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return (n<0)?-1:(n+1);
}
public static void main(String[] args) {
int cap = 120;
System.out.println(tableSizeFor(cap));
}
}