Last active
September 15, 2024 11:18
-
-
Save mfuerstenau/ba870a29e16536fdbaba to your computer and use it in GitHub Desktop.
ZigZag encoding/decoding explained
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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
THANK YOU for this reference, was looking for the decoding portion for hours today.