31

In the google protocol buffers encoding overview, they introduce something called "Zig Zag Encoding", this takes signed numbers, which have a small magnitude, and creates a series of unsigned numbers which have a small magnitude.

For example

Encoded => Plain
0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3

And so on. The encoding function they give for this is rather clever, it's:

(n << 1) ^ (n >> 31) //for a 32 bit integer

I understand how this works, however, I cannot for the life of me figure out how to reverse this and decode it back into signed 32 bit integers

6 Answers 6

34

Try this one:

(n >> 1) ^ (-(n & 1))

Edit:

I'm posting some sample code for verification:

#include <stdio.h>

int main()
{
  unsigned int n;
  int r;

  for(n = 0; n < 10; n++) {
    r = (n >> 1) ^ (-(n & 1));
    printf("%u => %d\n", n, r);
  }

  return 0;
}

I get following results:

0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3
7 => -4
8 => 4
9 => -5
14
  • 1
    I knew there had to be a way around the multiply. Kudos!
    – ergosys
    Feb 5, 2010 at 23:18
  • Well, it works for me and for ergosys, so it should work for you too... Can you tell me what results you get? Feb 5, 2010 at 23:23
  • It may well be that I'm using it incorrectly. I have a UInt32 for n, and I'm casting the returned result into Int32 afterwards. Which sounds like a logical way to do things...
    – Martin
    Feb 5, 2010 at 23:24
  • 1
    I think this may be a language problem, translating that pretty much directly into C# results in an error, negating a UInt32 results in a long, and xor of long and UInt32 is undefined. I'm going to have a go at fixing it for C#
    – Martin
    Feb 5, 2010 at 23:42
  • 1
    return ((int)(u >> 1)) ^ ((int)(-(u & 1))); The power of casting has fixed it. So, the question remains which should I use, from what ergosys said above I would assume this is faster due to a lack of multiplication?
    – Martin
    Feb 5, 2010 at 23:44
5

Here's yet another way of doing the same, just for explanation purposes (you should obviously use 3lectrologos' one-liner).

You just have to notice that you xor with a number that is either all 1's (equivalent to bitwise not) or all 0's (equivalent to doing nothing). That's what (-(n & 1)) yields, or what is explained by google's "arithmetic shift" remark.

int zigzag_to_signed(unsigned int zigzag)
{
    int abs = (int) (zigzag >> 1);

    if (zigzag % 2)
        return ~abs;
    else
        return abs;
}

unsigned int signed_to_zigzag(int signed)
{
    unsigned int abs = (unsigned int) signed << 1;

    if (signed < 0)
        return ~abs;
    else
        return abs;
}

So in order to have lots of 0's on the most significant positions, zigzag encoding uses the LSB as sign bit, and the other bits as the absolute value (only for positive integers actually, and absolute value -1 for negative numbers due to 2's complement representation).

6
  • zigZag_to_signed is not returning the original value.
    – Salar
    Dec 10, 2015 at 22:13
  • @SalarKhalilzadeh Thanks, fixed. Operator precedence was wrong, casting then shifting lost the first bit of "zigzag".
    – Cimbali
    Dec 14, 2015 at 18:55
  • The difference with the answer of 3lectrologos is that you use a test. A test ~disable pipelining of operation and is slower than a computation without a test and branch.
    – chmike
    Jul 2, 2018 at 9:21
  • @chmike Yes this answer is to illustrate what happens, not for performance, as acknowledged in the first line.
    – Cimbali
    Jul 2, 2018 at 10:14
  • 1
    Thanks for this. This version makes it easy to see intuitively why the encoding scheme works.
    – 1110101001
    Jan 19, 2021 at 2:42
4

How about

(n>>1) - (n&1)*n
0
2

After fiddling with the accepted answer proposed by 3lectrologos, I couldn't get it to work when starting with unsigned longs (in C# -- compiler error). I came up with something similar instead:

( value >> 1 ) ^ ( ~( value & 1 ) + 1 )

This works great for any language that represents negative numbers in 2's compliment (e.g. .NET).

1

I have found a solution, unfortunately it's not the one line beauty I was hoping for:

uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);

UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
-1

I'm sure there's some super-efficient bitwise operations that do this faster, but the function is straightforward. Here's a python implementation:

def decode(n):
  if (n < 0):
    return (2 * abs(n)) - 1
  else:
    return 2 * n

>>> [decode(n) for n in [0,-1,1,-2,2,-3,3,-4,4]]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
3
  • Thanks, but unfortunately this is in a network encoding system for a game, and this particular decode function is used many times per packet, many times per second - it's gotta be fast
    – Martin
    Feb 5, 2010 at 23:20
  • You can use a simple bit op to speed this up a bit. Shift by 1 to multiply by 2. Oct 17, 2013 at 14:13
  • -1: This function encodes signed numbers into coded unsigned numbers. The original question already has a function that does that. The original question asked for a function that decodes those unsigned numbers back to the original signed numbers: we want decode(3) to return -2, but this function makes decode(3) return 6.
    – David Cary
    Jun 18, 2015 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.