要么改变世界,要么适应世界

算法模板之位操作

2020-08-24 18:55:00
126
目录

在计算机中,对数据进行位操作具有十分高的效率,就拿乘法来说,假如乘数是一个2N形式的数字,那么就可以使用左移的方式,例如: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);
}
历史评论
开始评论