21

エンコーディングの「署名されたタイプ」から-プロトコルバッファ-Googleコード：

ZigZagエンコーディングは、符号付き整数を符号なし整数にマップするため、絶対値が小さい（たとえば、-1）数値もvarintエンコード値が小さくなります。これは、正と負の整数を前後に「ジグザグ」する方法で行われるため、-1は1としてエンコードされ、1は2としてエンコードされ、-2は3としてエンコードされ、以下同様に続きます。次の表で確認できます。

Signed Original  Encoded As
0                0
-1               1
1                2
-2               3
2147483647       4294967294
-2147483648      4294967295

言い換えると、各値nは次を使用してエンコードされます。

(n << 1) ^ (n >> 31)

sint32sの場合、または

(n << 1) ^ (n >> 63)

64ビットバージョンの場合。

テーブルの内容はどのように(n << 1) ^ (n >> 31)等しくなりますか？私はそれがポジティブに機能することを理解していますが、それはたとえば-1にどのように機能しますか？-1は1111 1111、ではないでしょ(n << 1)う1111 1110か？（ネガのビットシフトはどの言語でもうまく形成されていますか？）

それでも、数式を使用して実行すると(-1 << 1) ^ (-1 >> 31)、32ビット整数を想定する1111 1111と40億になりますが、表では1が必要であると考えています。

4

3 に答える 3

31

負の符号付き整数を右にシフトすると、符号ビットがコピーされ、次のようになります。

(-1 >> 31) == -1

それで、

(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
                       = 1

これは、バイナリ（ここでは8ビット）で視覚化する方が簡単な場合があります。

(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
                      = 00000001
于 2010-12-26T07:36:52.597 に答える
2

ジグザグマッピングについて考える別の方法は、それが符号と大きさの表現にわずかなひねりを加えたものであるということです。

ジグザグマッピングでは、マッピングの最下位ビット（lsb）が値の符号を示します。0の場合、元の値は負ではなく、1の場合、元の値は負です。

負でない値は、lsbの符号ビット用のスペースを確保するために、単純に1ビット左にシフトされます。

負の値の場合、数値の絶対値（大きさ）に対して同じ1ビット左シフトを実行し、lsbに符号を示すだけで済みます。たとえば、-1は0x03または0b00000011にマップできます。ここで、lsbは負であり、1の大きさが1ビットだけ左にシフトされていることを示します。

この符号と大きさの表現の醜い点は、0x01または0b00000001としてマップされた「負のゼロ」です。このゼロの変形は、値の1つを「使い果たし」、表現できる整数の範囲を1つシフトします。おそらく、負のゼロを-2 ^ 63に特殊なケースでマップして、64b2の補数範囲[-2^ 63、2 ^ 63）全体を表すことができるようにします。つまり、貴重なシングルバイトエンコーディングの1つを使用して、小さな大きさの数値用に最適化されたエンコーディングで使用されることはほとんどない値を表し、特殊なケースを導入しました。これは悪いことです。

これは、この符号と大きさの表現でジグザグのねじれが発生する場所です。符号ビットはまだlsbにありますが、負の数の場合、特別なケーシングの負のゼロではなく、大きさから1を減算します。ここで、-1は0x01にマップされ、-2 ^ 63も特殊なケースでは表現されません（つまり、-マグニチュード2 ^ 63 -1、左に1ビットシフト、lsb /符号ビットが設定され、すべてのビットが1に設定されます） 。

したがって、ジグザグエンコーディングについて考える別の方法は、よりスマートな符号と大きさの表現であるということです。符号ビットはlsbに格納され、負の数の大きさから1が減算され、大きさは1ビット左にシフトされます。

符号を明示的にテストするよりも、投稿した無条件のビット単位の演算子を使用してこれらの変換を実装する方が高速です。特殊なケースでは、負の値を操作し（たとえば、1を否定して減算するか、ビット単位ではない）、大きさをシフトしてから、明示的に設定します。 lsb符号ビット。ただし、これらは実質的に同等であり、このより明確な符号と大きさの一連のステップは、これらのことを何を、なぜ行っているのかを理解するのが簡単な場合があります。

C / C ++のビットシフトの負の値は移植性がないため、避ける必要がありますが、警告します。負の値を左にシフトすると未定義の動作が発生し、負の値を右にシフトすると実装で定義された動作が発生します。正の整数を左シフトしても、未定義の動作が発生する可能性があります（たとえば、符号ビットにシフトすると、トラップなどが発生する可能性があります）。したがって、一般に、C /C++では符号付き型をビットシフトしないでください。"いやだっていうだけだよ。"

最初に型の署名されていないバージョンにキャストして、標準に従って安全で明確な結果を取得します。これは、負の値の算術シフトがなく、論理シフトのみが発生することを意味します。したがって、それを考慮してロジックを調整する必要があります。

Cの64b整数のジグザグマッピングの安全でポータブルなバージョンは次のとおりです（算術否定に注意してください）。

#include <stdint.h>

uint64_t zz_map( int64_t x )
{
  return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}

int64_t zz_unmap( uint64_t y )
{
  return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}
于 2018-02-22T09:47:12.227 に答える
1

私の2セントを議論に加えさせてください。他の回答が指摘しているように、ジグザグエンコーディングは符号の大きさのねじれと考えることができます。この事実は、任意のサイズの整数に対して機能する変換関数を実装するために使用できます。たとえば、Pythonプロジェクトの1つで次のコードを使用しています。

def zigzag(x: int) -> int:
    return x << 1 if x >= 0 else (-x - 1) << 1 | 1

def zagzig(x: int) -> int:
    assert x >= 0
    sign = x & 1
    return -(x >> 1) - 1 if sign else x >> 1

intこれらの関数は、Pythonには固定ビット幅がないにもかかわらず機能します。代わりに、動的に拡張します。ただし、このアプローチは条件付き分岐を必要とするため、コンパイル型言語では非効率的である可能性があります。

于 2018-04-04T20:30:55.910 に答える