算法模板之位操作

在计算机中，对数据进行位操作具有十分高的效率，就拿乘法来说，假如乘数是一个2^N形式的数字，那么就可以使用左移的方式，例如：n * 2 == n << 1、n * 8 == n << 3、n / 16 == n >> 4、，实际上位操作还有其他更高级的用法：

判断num是否是2的次幂

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

向上取整为2次幂

public static int upperPowerOf2(int num) {
    if (num <= 0) return 1;
    if ((num & (num - 1)) == 0) return num;
    num |= num >> 1;
    num |= num >> 2;
    num |= num >> 4;
    num |= num >> 8;
    num |= num >> 16;
    return num + 1;
}

返回num的最高有效位的掩码

如i=00..1xx..，则返回00..100..

public static int highestOneBit(int num) {
        num |= (num >>  1);
        num |= (num >>  2);
        num |= (num >>  4);
        num |= (num >>  8);
        num |= (num >> 16);
        // 无符号右移
        return num - (num >>> 1);
}

保留最右边的“1”

public static int rightmostOneBit(int num){
    return num & (~num) + 1;
}

清除最右边的“1”

public static int clearLowestBit(int num) {
    return n & (n - 1);
}