来源:

     漫画算法 P173

问题:

实现一个方法,判断是个整数是否是2的整数次幂,要求性能尽可能高...

1.将2的整数次幂转成2进制

2.2的整数次幂-1(原始值-1)

3.原始值 & (原始值-1) 结果=0

如下图所示:

十进制

二进制

原始值-1

 原始值&(原始值-1)

是否为2的整数次幂

2

10B

 01B 0

Y

4

100B

 011B 0

Y

8

1000B

 0111B 0

Y

16

10000B

 01111B 0

Y

32

100000B

 011111B 0

Y

64

1000000B

 0111111B 0

Y

100

1100100B

 1100011B 1100000B

N

 

so,算法很 简单了

 public static boolean isPowerOf2(int num){
        return (num&num -1)==0;
    }

 

那么,如何返回一个大于或小于某个数的2的整数次幂的数

借鉴HashMap 的源码,

1.小于n的2的整数次幂的数

public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

2.大于n的2的整数次幂的数

number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1