質問

Googleプロトコルバッファー エンコードの概要, 、彼らは「zig zag encoding」と呼ばれるものを紹介します。これには署名された数字があります。

例えば

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ビット整数に戻す方法を理解することはできません

役に立ちましたか？

解決

これを試してみてください：

(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

他のヒント

どうですか 

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

これは、説明のためだけに同じことをするもう1つの方法を示します（明らかに3レフェロロゴのワンライナーを使用する必要があります）。

あなたは、すべての1（ビットワイズではない）またはすべての0（何もしないことに相当）のいずれかの数字でXORに気付く必要があります。それが何なのか (-(n & 1)) 利回り、またはGoogleの「算術シフト」の発言によって説明されるもの。

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を持つために、ZigzagエンコードはLSBをサインビットとして、もう1つのビットを絶対値として使用します（実際には正の整数の場合のみ、2の補体のための負の数値では絶対値-1を使用します表現）。

3レフロロゴによって提案された受け入れられた回答をいじった後、署名されていないロング（C＃ - コンパイラエラー）で始めるときにそれを機能させることができませんでした。代わりに似たようなものを思いついた：

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

これは、2の賛辞（.NETなど）の負の数字を表すあらゆる言語に最適です。

私は解決策を見つけました。残念ながら、それは私が望んでいた1つのラインの美しさではありません。

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

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

これをより速く行う非常に効率的なビットワイズ操作があると確信していますが、機能は簡単です。これが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]
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top