Skip to content

Instantly share code, notes, and snippets.

@mfuerstenau
Last active September 15, 2024 11:18
Show Gist options
  • Save mfuerstenau/ba870a29e16536fdbaba to your computer and use it in GitHub Desktop.
Save mfuerstenau/ba870a29e16536fdbaba to your computer and use it in GitHub Desktop.
ZigZag encoding/decoding explained
ZigZag-Encoding
---------------
Maps negative values to positive values while going back and
forth (0 = 0, -1 = 1, 1 = 2, -2 = 3, 2 = 4, -3 = 5, 3 = 6 ...)
(i >> bitlength-1) ^ (i << 1)
with "i" being the number to be encoded, "^" being
XOR-operation and ">>" would be arithemtic shifting-operation
(highest-order bit is replicated). For 32-bit Java integer
this would be
(i >> 31) ^ (i << 1)
ZigZag-Decoding
---------------
(i >>> 1) ^ -(i & 1)
with "i" being the number to be encoded, "^" being
XOR-operation, ">>>" would be non-arithemtic
shifting-operation (0-padding) and "-" is the unary
negative-operation (not bit-inverting operation).
Example for ZigZag-encoded value -1 (8-bit, two's complement)
-------------------------------------------------------------
1111 1111 = -1
1111 1111 = -1 >> 7
1111 1111 = -1
1111 1110 = -1 << 1
1111 1111 = -1 >> 7
^ 1111 1110 = -1 << 1
---------
0000 0001 = (-1 >> 7) ^ (-1 << 1) = 1
Example for ZigZag-encoded value 1 (8-bit, two's complement)
------------------------------------------------------------
0000 0001 = 1
0000 0000 = 1 >> 7
0000 0001 = 1
0000 0010 = 1 << 1
0000 0000 = 1 >> 7
^ 0000 0010 = 1 << 1
---------
0000 0010 = (1 >> 7) ^ (1 << 1) = 2
Example for ZigZag-decoded value 3 (8-bit, two's complement)
-------------------------------------------------------------
0000 0011 = 3
0000 0001 = 3 >>> 1
0000 0011 = 3
1111 1111 = -(3 & 1) (which is equal to ~(3 & 1) + 1)
0000 0001 = 3 >>> 1
^ 1111 1111 = -(3 & 1)
---------
1111 1110 = (3 >>> 1) ^ -(3 & 1) = -2
Example for ZigZag-decoded value 4 (8-bit, two's complement)
-------------------------------------------------------------
0000 0100 = 4
0000 0010 = 4 >>> 1
0000 0100 = 4
0000 0000 = -(4 & 1) (which is equal to ~(4 & 1) + 1)
0000 0010 = 4 >>> 1
^ 0000 0000 = -(4 & 1)
---------
0000 0010 = (4 >>> 1) ^ -(4 & 1) = 2 (two's complement!)
Reminder "two's complement"
---------------------------
0. (convert absolute value to binary)
if negative:
1. invert bits
2. add (+ not &) 1
Example "two's complement" (8-bit) for value -5
------------------------------------------------
0. -5 -> 0000 0101
1. 1111 1010
2. 1111 1010 + 0000 0001 = 1111 1011
Example "two's complement" (8-bit) for value 5
----------------------------------------------
0. 5 -> 0000 0101 (done)
def zigzag_encode (i):
return (i >> 31) ^ (i << 1)
def zigzag_decode (i):
return (i >> 1) ^ -(i & 1)
@gabe-lee
Copy link

THANK YOU for this reference, was looking for the decoding portion for hours today.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment