Ryan Peschel
Ryan Peschel

Reputation: 11828

Is there a faster way to do ZigZag encoding in JavaScript that works with large numbers?

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

Upvotes: 0

Views: 202

Answers (0)

Related Questions