30

googleプロトコルバッファエンコーディングの概要では、「ジグザグエンコーディング」と呼ばれるものが導入されています。これは、大きさが小さい符号付き数値を取得し、大きさが小さい一連の符号なし数値を作成します。

例えば

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

等々。彼らがこれのために与えるエンコーディング関数はかなり賢いです、それは次のとおりです：

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

これがどのように機能するかは理解していますが、これを逆にして符号付き32ビット整数にデコードする方法を一生理解することはできません。

4

6 に答える 6

32

これを試してください：

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

編集：

検証用のサンプルコードを投稿しています。

#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;
}

次の結果が得られます。

0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3
7 => -4
8 => 4
9 => -5
于 2010-02-05T23:03:39.750 に答える
4

どうですか

(n>>1) - (n&1)*n
于 2010-02-05T22:49:23.910 に答える
4

説明のためだけに、同じことを行うさらに別の方法があります（明らかに、3lectrologosのワンライナーを使用する必要があります）。

すべて1（ビット単位ではないのと同等）またはすべて0（何もしないのと同等）のいずれかの数値でxorすることに注意する必要があります。それが(-(n & 1))得られるもの、またはグーグルの「算術シフト」の発言によって説明されるものです。

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;
}

したがって、最上位に多くの0を含めるために、ジグザグエンコーディングでは、LSBを符号ビットとして使用し、他のビットを絶対値として使用します（実際には正の整数の場合のみ、2の補数による負の数の場合は絶対値-1）。表現）。

于 2012-09-21T22:31:07.143 に答える
2

3lectrologosによって提案された受け入れられた答えをいじった後、unsigned longsで開始したときにそれを機能させることができませんでした（C＃-コンパイラエラー）。私は代わりに似たようなものを思いついた：

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

これは、2の補数で負の数を表す言語（.NETなど）に最適です。

于 2013-10-30T15:43:43.767 に答える
1

私は解決策を見つけましたが、残念ながらそれは私が望んでいた一線の美しさではありません：

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

UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
于 2010-02-05T22:45:02.183 に答える
-1

これをより高速に実行する非常に効率的なビット演算があると確信していますが、関数は単純です。Pythonの実装は次のとおりです。

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]
于 2010-02-05T22:45:43.627 に答える