[数据结构与算法]Highbit && Lowbit

我们知道计算机底层使用二进制表示数，而 highbit && lowbit 顾名思义就是求某数二进制最高位$1$和最低位$1$所表示十进制数。不管是 OI 还是计算机工程领域这两种算法运用都比较频繁。

lowbit

lowbit 算法在 OI 中应用比较广泛，比如树状数组等。
在了解 lowbit 算法前先看一个问题 —— 求某数清零最低位 $1$ 后变为多少？
比如对于 $40$，二进制表示为 $101000$，这里忽略所有高位 $0$，清零最低位 $1$ 后变为 $100000$，
解决类似问题，能确定解决思路是用为运算，由于二进制非 $0$ 即 $1$，我们用该数减 $1$ ，则借位到最低位 $1$，最低位 $1$ 变为 $0$ ，最低位 $1$ 之后 $0$ 全变为 $1$，例如
$$101000?1=100111$$
发现没，最低位 $1$ 以及之后的 $0$ 都取反了，再和原来数做按位与即可清零最低位 $1$ ，即 x & (x-1)，我们可以使用循环清零最低位 $1$ 直到该数变为 $0$ 这种方式统计一个数二进制表示中含有多少个 $1$ ，

public int hammingWeight(int n) {
	int ret = 0;
	while (n != 0) {
	    n &= n - 1;
	    ret++;
	}
	return ret;
}

lowbit 算法我们可以先将该数按位取反，例如 $101000$ 按位取反后变为 $010111$ ，最低位 $1$ 变为 $0$ ，最低位 $1$ 之后 $0$ 全变为 $1$，此时如果再加 $1$，就会进位到原来最低位 $1$ 位置， $010111+1=011000$，此时再和原来数按位与就可只保留最低位 $1$ ，这里需要注意，计算机使用补码表示一个数，负数补码为这个数正数按位取反加 $1$，所以刚才按位取反加 $1$不就是这个数的负数吗，Java java.lang.Integer#lowestOneBit 对该算法提供实现，

public static int lowestOneBit(int i) {
    // HD, Section 2-1
    return i & -i;
}

highbit

同样，Java java.lang.Integer#highestOneBit 对该 highbit 算法提供实现，

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);
 }

可以看出该算法使用了五次右移和与自己按位或运算，第一次可以将最高位 $1$ 和其下一位变成 $1$ ，第二次可以将最高位 $1$ 连续四位变为$1$ 。。。，依次类推，五次过后最高位 $1$ 及其后所有位都变为 $1$ ，最后减去不带符号的右移一位，即可得到一个 highbit 值。
这里需要注意 >>> 和 >> 都表示右移，但 >>> 运算符会用 $0$ 填充高位，>> 会用符号位填充高位，所以负数经过五次右移和与自己按位或运算后必定所有位全为 $1$ ，即十进制 $?1$，最后减去不带符号的右移一位只剩符号位为 $1$，其余位为 $0$，表示十进制 -2147483648。

public static void main(String[] args) throws Exception {

    System.err.println(Integer.highestOneBit(7)); // 4
    System.err.println(Integer.highestOneBit(11)); // 8
    System.err.println(Integer.highestOneBit(-1)); // -2147483648
    System.err.println(Integer.highestOneBit(-97)); // -2147483648
}

Java java.util.HashMap#tableSizeFor 求一个大于输入 Map 容量且最小的为 $2$ 的 $n$ 次幂的数，使用到的算法和该算法类似，

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	
	static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
}

该算法和 highbit 类似，首先这里容量 cap 非负，通过五次 n |= n >>> i 后，最高位 $1$ 及其后所有位都变为 $1$ ，再经过 n + 1 运算进位到最高位前一位，原最高位 $1$ 及其后所有位都变为 $0$。
但这里有个问题为什么要执行 int n = cap - 1？
执行该命令后，如果 cap 刚好为 $2$ 的 $n$ 次幂，则所有计算完成后 cap 不变。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖