Skip to content

Instantly share code, notes, and snippets.

# mfuerstenau/zigzag-encoding.README Last active Aug 2, 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)
 def zigzag_encode (i): return (i >> 31) ^ (i << 1) def zigzag_decode (i): return (i >> 1) ^ -(i & 1)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.