ZigZag encoding/decoding explained

zigzag-encoding.README

  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)

zigzag.py

def zigzag_encode (i):
   return (i >> 31) ^ (i << 1)

def zigzag_decode (i):
    return (i >> 1) ^ -(i & 1)