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