Poison

Manipulating Rightmost Bits

发表于
获取二进制表示中最右侧为 1 的比特位

已知 -x = ~x + 1 ，我们可以使用 x & (-x) 得到二进制表示中最右侧的 1：

1
2
3
4
5
6
7
8
9
若 x 的二进制表示为：
11011100
则 ~x 的二进制表示为：
00100011
则 -x = ~x + 1 的二进制表示为：
00100100

则 x & (-x) 的二进制表示为：
00000100

其中 JDK 中的 Integer.lowestOneBit 就采用了以上的方法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Returns an {@code int} value with at most a single one-bit, in the
 * position of the lowest-order ("rightmost") one-bit in the specified
 * {@code int} value.  Returns zero if the specified value has no
 * one-bits in its two's complement binary representation, that is, if it
 * is equal to zero.
 *
 * @param i the value whose lowest one bit is to be computed
 * @return an {@code int} value with a single one-bit, in the position
 *     of the lowest-order one-bit in the specified value, or zero if
 *     the specified value is itself equal to zero.
 * @since 1.5
 */
public static int lowestOneBit(int i) {
    // HD, Section 2-1
    return i & -i;
}
去除二进制表示中最右侧为 1 的比特位

因为 x - 1 会使最低位 1 右侧的 0 全部变为 1 且最低位 1 同时变为 0，所以我们使用 x & (x - 1) 可以去除最低位的 1：


Reference

面试题15. 二进制中 1 的个数（位运算，清晰图解）
2-1 Manipulating Rightmost Bits