문제

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

설명 목적으로 만 똑같이 수행하는 또 다른 방법이 있습니다 (분명히 3Lectrologos의 One-Liner를 사용해야합니다).

당신은 당신이 모두 1 (비트와 동일하지 않음) 또는 모든 0 (아무것도하지 않는 것과 동일) 인 숫자를 가진 것을 알아야합니다. 그게 뭐야 (-(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를 부호 비트로 사용하고 다른 비트는 절대 값으로 사용합니다 (실제로 양수 정수의 경우에만, 2의 보완으로 인해 음수의 경우 절대 값 -1 대표).

3Lectrologos가 제안한 허용 된 답변을 피한 후 서명되지 않은 Long (C# - 컴파일러 오류)으로 시작할 때 작동 할 수 없었습니다. 나는 대신 비슷한 것을 생각해 냈습니다.

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

이것은 2의 칭찬 (예 : .NET)에서 음수를 나타내는 모든 언어에 적합합니다.

나는 해결책을 찾았다. 불행히도 그것은 내가 기대했던 한 줄의 아름다움이 아니다 :

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

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

나는 이것을 더 빠르게 수행하는 초효 비트 연산이 있다고 확신하지만 기능은 간단합니다. 파이썬 구현은 다음과 같습니다.

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