ZigZag decode/encode in Java

Question

I'm looking for some library which can provide with the functions that can help deconding zig-zag encoded byte array into 2's complement long/int and back.

Since ZigZag is used in protobuf I expected that guava has something for it, but googling did not give any result. By ZigZag encoding I mean this:

Signed Original Encoded As
0               0
-1              1
1               2
-2              3
2147483647      4294967294
-2147483648     4294967295

Do I have to "reinvent the wheel"?

@NiVeR Not quite 2 lines. Looking at its implementation I found it pretty much scary. — Some Name, Jun 09 '18 at 10:48
https://gist.github.com/mfuerstenau/ba870a29e16536fdbaba and scroll down. OK, it's python, but nothing there doesn't have a 1:1 Java equivalent. — fvu, Jun 09 '18 at 10:52
The page you linked has your answer: `(n << 1) ^ (n >> 63)` for 64-bit — Arijoon, Jun 09 '18 at 11:06
9 or 10 bytes aren't long or ints. these are 4B(32bits) and 8B (64bit) values. https://cs.fit.edu/~ryan/java/language/java-data.html — Arijoon, Jun 09 '18 at 11:35
You can also look at how protobuf does it: https://github.com/google/protobuf/blob/master/java/core/src/main/java/com/google/protobuf/CodedInputStream.java check `long readRawVarint64()` — Arijoon, Jun 09 '18 at 11:37
@Arijoon I meant ZigZag encoding is a bit eccessive in the sense that the 8-bytes long may be incoded into 9 or 10 bytes. — Some Name, Jun 09 '18 at 12:41

score 1 · Accepted Answer · answered Jun 09 '18 at 10:55

1

Here you go:

    Long aD = 2147483647L;
    //encode
    Long aE = (aD >> 31) ^ (aD << 1);
    //decode
    Long bD = (aE >> 1) ^ -(aE & 1);

    System.out.println(aD + "," + aE + "," + bD);

answered Jun 09 '18 at 10:55

NiVeR

9,644
4
30
35

The problem is it does not work for longs which are encoded to 9 or 10 bytes. – Some Name Jun 09 '18 at 11:00
You can go on and adapt the `BigInteger` type if you want to treat arbitrary lenght numbers. – NiVeR Jun 09 '18 at 11:03
@SomeName I went with just the simple logic of if(value%2==0){ return value/2; }else { return (long) -Math.floor(value/2d); } – Sagan Sep 18 '22 at 20:38

ZigZag decode/encode in Java

1 Answers1