أسرع طريقة لحساب عدد من التحولات قليلا في صحيح غير الموقعة

Question

وأنا أبحث عن أسرع طريقة لحساب عدد من التحولات قليلا في unsigned int.

إذا يحتوي على الباحث: 0b00000000000000000000000000001010

وعدد من التحولات هم: 4

إذا يحتوي على الباحث: 0b00000000000000000000000000001001

وعدد من التحولات هم: 3

واللغة هي C.

Answer 1

int numTransitions(int a)
{
  int b = a >> 1; // sign-extending shift properly counts bits at the ends
  int c = a ^ b;  // xor marks bits that are not the same as their neighbors on the left
  return CountBits(c); // count number of set bits in c
}

لتطبيق فعال لCountBits انظر> وأ href = "HTTP : //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel "يختلط =" noreferrer "> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

وأسرع يعتمد على السيناريو الخاص بك: كما يمكنك تحديد نوع البيانات الخاص بك كما المستمر الحجم (صحيح غير الموقعة)، فمن الممكن مع طاولة البحث. ولكن عندما تحتاج هذه العملية مرة واحدة فقط من النفقات العامة مستمرة إلى الحرف الأول من الجدول كبير جدا، والمسح الضوئي + عد من خلال كثافة العمليات هو أسرع بكثير على الرغم من.

وأعتقد أن أفضل عموما سيكون مزيجا: جدول البحث عن بايت أو كلمة (256 أو 64K إدخالات ليست أكثر من ذلك)، ثم تجمع بايت / كلمات من الماضي بواجبهم / أول

Answer 3

في C / C ++ أود أن تفعل ما يلي:

unsigned int Transitions(unsigned int value)
{
    unsigned int result = 0;

    for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
    {
        if (markers & 0x01) result++;
    }

    return result;
}

Answer 4

إليك الشفرة باستخدام التحول الحسابي + اكس اور وطريقة كيرنيغان لفرز بت:

int count_transitions(int x)
{
    assert((-1 >> 1) < 0); // check for arithmetic shift
    int count = 0;
    for(x ^= (x >> 1); x; x &= x - 1)
        ++count;
    return count;
}

Answer 5

ما هي اللغة؟

وأود أن حلقة 64 مرات ثم قليلا تحويل رقمك لتفقد البتات، ثم تخزين بت السابق وذلك لمقارنة الحالي. اذا كان مختلف، incremember العد الخاص بك.

Answer 6

وطيب، مع التحولات تقصد إذا كنت تمشي من خلال سلسلة من 0-ق و 1 والصورة، وكنت تعول كل التكرار بأن 0 يتبع 1 أو 1 يتبع 0.

وهذا سهل عن طريق تحويل بت من والفرز التغييرات:

transitions(n)
  result = 0
  prev = n mod 2
  n = n div 2
  while n<>0 
    if n mod 2 <> prev then
      result++
      prev = n mod 2
    fi
    n = n div 2
  elihw
  return result

ويمكنك استبدال وزارة الدفاع و div مع التحولات.