Sonia Notes
92 subscribers
99 photos
1 video
10 files
142 links
Download Telegram
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)
1
Sonia Notes
Photo