منعرج ZAG فك التشفير

Question

في مخازن بروتوكول Google ترميز نظرة عامة, ، يقدمون شيئا يسمى "ترميز ZIG ZAG"، وهذا يأخذ أرقاما موقعة، والتي لها حجم صغير، وإنشاء سلسلة من الأرقام غير الموقعة التي لها حجم صغير.

علي سبيل المثال

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 بت

Answer 1

جرب هذه:

(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

Answer 2

ماذا عن

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

Answer 3

فيما يلي طريقة أخرى للقيام بذلك، فقط لأغراض التفسير (يجب أن تستخدم بوضوح 3LETRologos "بطانة واحدة واحدة).

عليك فقط أن تلاحظ أنك XOR مع رقم إما كليا (ما يعادله لا يحتوي على bitwise) أو كل 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 التمثيل).

Answer 4

بعد الاضطراب مع الإجابة المقبولة التي اقترحتها 3Lectrologos، لم أستطع الحصول عليها للعمل عند البدء في فترة طويلة غير موقعة (في خطأ C # - مترجم). لقد توصلت إلى شيء مماثل بدلا من ذلك:

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

يعمل هذا رائعا لأي لغة تمثل أرقاما سلبية في مجاملة 2 (مثل .NET).

Answer 5

لقد وجدت حلا، لسوء الحظ، إنه ليس الجمال السطر الذي كنت آمل في:

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

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

Answer 6

أنا متأكد من أن هناك بعض عمليات bitwise الفائقة التي تفعل هذا أسرع، ولكن الوظيفة واضحة. إليك تنفيذ ثعبان:

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]