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