zigzag  

A library for converting between signed and unsigned integers using zigzag encoding and decoding. View the documentation on docs.rs here.

License

This crate is available as open source under the terms of the MIT License.

lib.rs:

A crate which exposes two quasi-extension traits that extend signed integers with the ZigZagEncode trait and unsigned integers with the ZigZagDecode trait.

Zigzag Encoding

Zigzag encoding takes a signed integer and encodes it as an unsigned integer. It does so by counting up, starting at zero, alternating between representing a positive number and a negative number.

To encode any signed integer, x, with a representation length—in bits, n, the formula is as follows:

(x >> n - 1) ^ (x << 1)

Note: The ^ operator is not exponentiation; rather, it is bitwise XOR.

For instance, the simplified formula to encode a signed 32-bit integer of value x would be as follows:

(x >> 31) ^ (x << 1)

Zigzag Decoding

To convert a zigzag-encoded unsigned integer, x, to its decoded signed counterpart, the formula is as follows:

(x >>> 1) ^ -(x & 1)

Note: The >>> operator is to represent a logical right shift as opposed to an arithmetic right shift. In Rust, unsigned integer types implement the right shift operator as logical instead of arithmetic. Therefore, the formula in Rust is simplified as (x >> 1) ^ -(x & 1).

Examples

Encoding a signed integer:

use zigzag::ZigZagEncode;

assert_eq!(0i8.zigzag_encode(), 0u8);
assert_eq!((-1i8).zigzag_encode(), 1u8);
assert_eq!(1i8.zigzag_encode(), 2u8);

assert_eq!(i8::MIN.zigzag_encode(), u8::MAX);
assert_eq!(i16::MIN.zigzag_encode(), u16::MAX);
assert_eq!(i32::MIN.zigzag_encode(), u32::MAX);
assert_eq!(i64::MIN.zigzag_encode(), u64::MAX);
assert_eq!(i128::MIN.zigzag_encode(), u128::MAX);

assert_eq!(isize::MIN.zigzag_encode(), usize::MAX);

Decoding an unsigned integer:

use zigzag::ZigZagDecode;

assert_eq!(0u8.zigzag_decode(), 0i8);
assert_eq!(1u8.zigzag_decode(), -1i8);
assert_eq!(2u8.zigzag_decode(), 1i8);

assert_eq!(u8::MAX.zigzag_decode(), i8::MIN);
assert_eq!(u16::MAX.zigzag_decode(), i16::MIN);
assert_eq!(u32::MAX.zigzag_decode(), i32::MIN);
assert_eq!(u64::MAX.zigzag_decode(), i64::MIN);
assert_eq!(u128::MAX.zigzag_decode(), i128::MIN);

assert_eq!(usize::MAX.zigzag_decode(), isize::MIN);