Skip to content

Instantly share code, notes, and snippets.

@mfuerstenau

mfuerstenau/zigzag-encoding.README

Last active January 1, 2025 19:55
Show Gist options
  • Save mfuerstenau/ba870a29e16536fdbaba to your computer and use it in GitHub Desktop.
Save mfuerstenau/ba870a29e16536fdbaba to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. M. Fürstenau revised this gist Aug 26, 2015. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions zigzag.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,5 @@
    def zigzag_encode (i):
    return (i >> 31) ^ (i << 1)

    def zigzag_decode (i):
    return (i >> 1) ^ -(i & 1)
  2. M. Fürstenau created this gist Aug 26, 2015.
    99 changes: 99 additions & 0 deletions zigzag-encoding.README
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,99 @@
    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)