/zigzag-encoding.README
Last active Sep 4, 2019
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