算法-位运算

位运算相关算法题

给定一个非负整数num，如何不用循环语句，返回>=num，并且离num最近的2的某次方

public int nearest2Power(int n) {
    n --;
    if (n < 1) {
        return 1;
    }
    int highOnePosition = 0;
    // 找到二进制下最高位的1的位置
    while (n != 1) {
        // 右移
        n = n >>> 1;
        highOnePosition ++;
    }
    return (int) Math.pow(2, highOnePosition + 1);
}

图解：

image-20220410031132541

为了保持统计逻辑，令num减一，则都按照第二种情况计算

高级写法：num-=1，再令最高位1的后面都是1，然后+1即是答案

public int nearest2Power(int n) {
    n--;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : n + 1;
}