[Google] isPowerof4 O(1)找4的倍数.

Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数.

既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111.  但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了.

  public static boolean isPowerof4(int n) {
        return (n&n-1)+n%3==1;
    }

下边是power of 8

public static boolean isPowerof8(int n) {
        return (n&n-1)+n%7==1;
    }