Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment