0

I am attempting to perform ZigZag encoding for numbers in JavaScript that are within the safe bounds of JavaScript integers

These functions seem to work up to 2^30 - 1 only because JavaScript bit-wise operators only work with 32 bit numbers:

function encodeZigzag(value) {
  return ((value << 1) ^ (value >> 31));
}

function decodeZigzag(encoded) {
  return (encoded >> 1) ^ -((encoded & 1));
}

console.log(decodeZigzag(encodeZigzag(0)));
console.log(decodeZigzag(encodeZigzag(-1))); 
console.log(decodeZigzag(encodeZigzag(2))); 
console.log(decodeZigzag(encodeZigzag(-2))); 
console.log(decodeZigzag(encodeZigzag(1073741823))); 
console.log(decodeZigzag(encodeZigzag(1073741824))); // breaks

Anyways, I was looking for a pair of alternate functions that worked up to a larger upper-bound (2^53 or so). I came up with these, which seem to work, but I was wondering if there was a more elegant / performant way:

function bigEncodeZigzag(v) {
  const shift = v * 2;

  return v >= 0 ? shift : -shift - 1;
}

function bigDecodeZigzag(v) {
  const shift = Math.floor(v / 2);

  return v % 2 === 0 ? shift : -shift - 1;
}

console.log(bigDecodeZigzag(bigEncodeZigzag(0)));
console.log(bigDecodeZigzag(bigEncodeZigzag(-1))); 
console.log(bigDecodeZigzag(bigEncodeZigzag(2))); 
console.log(bigDecodeZigzag(bigEncodeZigzag(-2))); 
console.log(bigDecodeZigzag(bigEncodeZigzag(1073741823))); 
console.log(bigDecodeZigzag(bigEncodeZigzag(1073741824))); // works
Heretic Monkey
  • 11,687
  • 7
  • 53
  • 122
Ryan Peschel
  • 11,087
  • 19
  • 74
  • 136
  • "Elegant" is not objectively measurable. "Performant" would be okay if there was a target (e.g., faster than X, less memory than Y). – Heretic Monkey Jan 08 '23 at 00:45
  • 1
    In any case, you could [try using the `Bigint` type](https://stackoverflow.com/a/68488096/215552). – Heretic Monkey Jan 08 '23 at 00:47
  • Yeah just faster then is fine. I saw BigInt but I suspect casting 4 numbers to BigInts and then casting back to a number is much slower than what I'm doing, with less browser support to boot – Ryan Peschel Jan 08 '23 at 00:48
  • Using `encoded >>> 1` extends the useful range somewhat – harold Jan 08 '23 at 02:51

0 Answers0