Poison

Shift Operators

发表于

最近写了些关于 Bit 操作的代码，才发现使用左移操作符时，当右侧操作数（需要移动的位数）大于左侧操作数比特个数时，实际移动位数等同于右侧操作数对左侧操作数比特个数求余。可能说的不是很明白，可以用一个简单的示例来说明，比如以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class BitShiftTest {

    private static String toBinaryString(int i) {
        return String.format("%32s", Integer.toBinaryString(i)).replace(' ', '0');
    }

    public static void main(String[] args) {
        int i = 0b00000000_00000000_00000000_00000001;
        int j = i << 35;
        System.out.println(j);
        System.out.println(toBinaryString(j));
    }

}

起初我认为以上代码中的 j 对应的值应该为 0，但是并不是这样的，以上代码的输出如下：

1
2
8
00000000000000000000000000001000

我们知道 int 占用 4 个字节，即 32 个比特，那么当我们对变量 i 进行左移 35 位时，此时等于将变量 i 左移 3 位。关于左移操作符，在 15.19. Shift Operators - JLS 中对此有如下说明：

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

即当变量为 int 类型时，实际移动的位数为右操作数的低 5 位比特对应的数值，即在文首的实例代码中移动 35 位时，实际移动的距离为 35 & 0b11111 = 3，即移动 3 位，即移动的距离等同于 35 % 32 = 3。

同理，关于 long 类型数值的左移操作亦是同理：

If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.

关于左移操作符，在 RoaringBitmap 的 BitmapContainer.java 中有如下应用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Simple bitset-like container.
 */
public final class BitmapContainer extends Container implements Cloneable {

    final long[] bitmap;

    @Override
    public Container add(final char i) {
        final long previous = bitmap[i >>> 6];
        long newval = previous | (1L << i);
        bitmap[i >>> 6] = newval;
        if (USE_BRANCHLESS) {
          cardinality += (int)((previous ^ newval) >>> i);
        } else if (previous != newval) {
          ++cardinality;
        }
        return this;
    }

}

在未压缩的 BitmapContainer 中，Bitmap 底层由 long 数组实现，我们知道一个 long 型数字占用 8 个字节，即 64 个比特，那么 add 方法中的第一行即为计算 i 对应 long[] bitmap 中的索引，即应该存储值的 long 数值的索引，此处的 i >>> 6 即等于 i / 64，即使用移位操作相比除法计算效率更优。在 add 方法中的第二行，将数组中之前的值 previous 与 1L << i 进行 或 运算，此处的左移操作符按照 JLS 中的规定，即可将对应的 比特位 置为 1，而不需要我们显式将 i 对 64 取余再进行左移操作。

同理，在 Guava 的 LockFreeBitArray 实现中，也用到了左移操作符，其 set 方法源码位于 BloomFilterStrategies.java at v31.1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static final class LockFreeBitArray {

  private static final int LONG_ADDRESSABLE_BITS = 6;
  final AtomicLongArray data;

  /** Returns true if the bit changed value. */
  boolean set(long bitIndex) {
    if (get(bitIndex)) {
      return false;
    }

    int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
    long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex

    long oldValue;
    long newValue;
    do {
      oldValue = data.get(longIndex);
      newValue = oldValue | mask;
      if (oldValue == newValue) {
        return false;
      }
    } while (!data.compareAndSet(longIndex, oldValue, newValue));

    // We turned the bit on, so increment bitCount.
    bitCount.increment();
    return true;
  }

}

整个方法的实现与 RoaringBitmap 中 BitmapContainer 的 add 方法实现几乎一致，使用左移操作符时还特意加了注释 only cares about low 6 bits of bitIndex，即 JLS 中的规定，该方法与 BitmapContainer 的 add 方法唯一不同的是此方法底层数据结构为 AtomicLongArray，即线程安全的数组，而在 BitmapContainer 中，long[] bitmap 并不是线程安全的。