Golang左移操作与java的不同

背景

最近在将一个查询解析pb数据工具迁移到Golang的http服务上，由于pb结构中使用了bitArray，一开始写入pb数据使用的是java服务，protobuf生成的Java代码会将bitArray抽象成java的BitSet类型，protobuf生成Golang代码时会将BitArray转化为golang 的 []int64的切片。

下面是pb的大致结构：

1
2
3
4
5
6
7
8
syntax = "proto3";

option go_package = "/message";

message Message {
  repeated int64 bitArray = 1;
  .....
}

在java服务序列化数据为pb时，会调用BitSet对象的set方法，将对应下标置成true或者false，调用该方法实际是用BitSet内部实现的编码方式维护了BitSet对象内部的long数组，在解析pb数据的时候，则需要调用BitSet的valueOf方法。

set方法

1
2
3
4
5
6
7
8
9
10
11
public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();
    }

valueof方法

1
2
3
4
5
6
7

public static BitSet valueOf(long[] longs) {
    int n;
    for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
        ;
    return new BitSet(Arrays.copyOf(longs, n));
}

这里就会存在一个冲突，因为protobuf生成Golang代码时会将BitArray转化为golang 的 []int64的切片。并不是java的BitSet，所以在使用Go来反序列化之前用java服务序列化的pb数据时，就需要使用go语言实现java中BitSet类的valueOf方法，并且需要实现get方法，用来判断bitset的某一位是否是1

get方法

1
2
3
4
5
6
7
8
9
10
public boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

在用go复刻java bitSet的时候就出现了问题

第一版

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const ADDRESS_BITS_PER_WORD = 6
const BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD

type BitSet struct {
	words      []int64
	wordsInUse int
}

func NewBitSet(words []int64) BitSet {
	return BitSet{words: words, wordsInUse: len(words)}
}

func ValueOf(longs []int64) BitSet {
	var n int
	for n = len(longs); n > 0 && longs[n-1] == 0; n-- {
	}
	copyArray := []int64{}

	finalLen := min(len(longs), n)
	for i := 0; i < finalLen; i++ {
		copyArray = append(copyArray, longs[i])
	}
	return NewBitSet(copyArray)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func (bs BitSet) get(bitIdx int) bool {
	if bitIdx < 0 {
		panic(fmt.Sprintf("index out of bounds exception: bitIntex < 0, %v", bitIdx))
	}
	wordIndex := bitIdx >> ADDRESS_BITS_PER_WORD

	var x int64 = 1
	return (wordIndex < bs.wordsInUse) && ((bs.words[wordIndex] & (x << bitIdx)) != 0)
}

func (bs BitSet) size() int {
	return len(bs.words) * BITS_PER_WORD
}

但是发现解析相同的pb数据时，go 实现的bitSet的get方法不正确

例如java BitSet 的 words数组是

1
longs := []int64{-1073741826, 8283751, 54166340830756864, 279262352707, -288054454291267584, 576320014816931847}

调用javabitset的get(230)返回值是true，而go是false

java：

1
2
3
4
5
public static void main(String[] args) {
        long[] longs = {-1073741826, 8283751, 54166340830756864L, 279262352707L, -288054454291267584L, 576320014816931847L};
        BitSet bitSet = BitSet.valueOf(longs);
        System.out.println(bitSet.get(230));
}

输出 true

go:

1
2
3
4
5
6
7
func TestValueOf_1(t *testing.T) {
	longs := []int64{-1073741826, 8283751, 54166340830756864, 279262352707, -288054454291267584, 576320014816931847}

	bitSet := ValueOf(longs)

	fmt.Println(bitSet.get(230))
}

输出: false

这样go与java的输出就不一致了，经过排查发现是,bitSet get方法的返回结果不一致

1
(wordIndex < bs.wordsInUse) && ((bs.words[wordIndex] & (x << bitIdx)) != 0)}
1
return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);

上面代码看着 是相同的逻辑，但是输出不同，问题就在在golang和java中都有<<操作，当左移操作导致溢出时，底层java和golang的处理方式是不同的，因为bitIndex上面例子中取得是230，所以 1 << 230就溢出了。

在java中 1 << 230 = 274877906944 = 2的38次方

在go中 1 << 230 = 0

可以发现java中如果左移操作溢出，实际会将 左移操作符右侧的数模上long的位数64，也就是 1 << 230 = 1 << (230 % 64) = 1 << 38

而在go中的左移操作并没有帮我们取模

所以go实现的bitSet的get方法要进行取模操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 这里 bitIdx左移会overflow go 的处理方式与java不同，java越界自动 mod 64，go 越界直接填0了
func (bs BitSet) get(bitIdx int) bool {
	if bitIdx < 0 {
		panic(fmt.Sprintf("index out of bounds exception: bitIntex < 0, %v", bitIdx))
	}
	wordIndex := bitIdx >> ADDRESS_BITS_PER_WORD

	var x int64 = 1
	return (wordIndex < bs.wordsInUse) && ((bs.words[wordIndex] & (x << (bitIdx % 64))) != 0)
}

func (bs BitSet) size() int {
	return len(bs.words) * BITS_PER_WORD
}

至此问题解

重新调用bitSet.get(230) go的返回也为true