أنماط مجموعة البتات في البايت

Question

ذكر جويل حساب عدد البتات المحددة في البايت كسؤال برمجي في كتابه دليل حرب العصابات لإجراء المقابلات, وتحدث عن طريقة للاستفادة من الأنماط التي تظهر في جدول البحث.لقد كتبت مقالاً عنه منذ فترة بعد أن وجدت النمط.

كي تختصر:

Number of bits set in a byte in 16x16
0   1   1   2   1   2   2   3   1   2   2   3   2   3   3   4  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
4   5   5   6   5   6   6   7   5   6   6   7   6   7   7   8  

الصف والعمود الأولان متماثلان تمامًا، ويمكن حساب كل موضع في الشبكة عن طريق إضافة القيم الأولى في الصف والعمود الخاصين بهذا الموضع.ولهذا السبب، فإنك تحتاج فقط إلى جدول بحث يحتوي على 16 إدخالاً لرقم مكون من 8 بتات، ويمكنك فقط استخدام أول 16 رقمًا.بعد ذلك، إذا أردت حساب مجموعة البتات في الرقم 243، على سبيل المثال، فما عليك سوى القيام بما يلي:

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 / 16 => 15 # (int)
y = 243 % 16 => 3

a[x] + a[y] => 6

# Are there six bits set in the number 243?
243 = 11110011 # yep

النمط التالي الذي لاحظته بعد ذلك هو أنه في كل مرة تقوم فيها بمضاعفة حجم شبكة NxN، يمكن حساب كل ربع بإضافة 0 و1 و1 و2 إلى كل ربع، على التوالي، كما يلي:

# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.  
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.  

# Upper left quad add 0 to each number from 2x2  
0   1   *   *  
1   2   *   *  
*   *   *   *  
*   *   *   *  

# Upper right quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
*   *   *   *  
*   *   *   *  

# Lower left quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   *   *  
2   3   *   *  

# Lower right quad add 2 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   2   3  
2   3   3   4  

كرر هذه العملية مرتين أخريين، وستحصل على شبكة 16 × 16 من الأعلى، لذلك اعتقدت أنه يجب أن يكون هناك نوع من خوارزمية الشجرة الرباعية التي تسمح لك بالبدء من الشبكة:

0 1
1 2

وأعطيت الرقم N، أنشئ جدول البحث سريعًا واكتشف عدد البتات.لذلك سؤالي/التحدي هو، هل يمكنك اكتشاف خوارزمية للقيام بذلك؟

Answer 1

بناءً على كود روبرت هنا, ، يمكن القيام بذلك بدون القسمة أو المعامل، واستبدالهما بإزاحة واحدة وواحد، كما يلي:

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 >> 4 # 15 (same as dividing by 16)
y = 243 & 0x0f # 3 ( same as modding by 16)

result = a[x] + a[y] # 6 bits set 

أو في ج:

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

بالنسبة لأي عدد صحيح بأي حجم، يمكنك فقط المرور عبر البايتات وإجراء بحث سريع، كما يلي:

def bits(n)
    a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
    a[n >> 4] + a[n & 0x0f]
end

def setBits(n)
   total = 0
   while(n > 0)
       total += bits(n&0xff)
       n >>= 8
   end
   total
end

setBits(6432132132165432132132165436265465465653213213265465) # 78 bits set

أنا راضٍ عن هذه الإجابة.كنت أعلم أن شيئًا أكثر تعقيدًا وشبه رباعي لن يكون فعالاً، اعتقدت أنها كانت تجربة فكرية جيدة.

Answer 2

هذا هو سؤال سخيف!في المثال الأول الذي قمت فيه بحساب عدد البتات المحددة باستخدام جدول مكون من 16 إدخالًا بدلاً من 256، لا يعد هذا أمرًا سحريًا!كل ما فعلته هو حساب عدد البتات المحددة في البتات الأربع الأولى من البايت (القضم الأول) ثم في القضم الثاني، وإضافة الاثنين معًا.x/16 هي القضمة الأولى، وx%16 هي القضمة الثانية.

إذا كررت العملية، أصبح لديك الآن جدول بحث لبتين، وقم بذلك أربع مرات فقط، مرة واحدة لكل زوج.وفي الحالات القصوى، يمكنك فقط جمع كل البتات معًا واحدة تلو الأخرى وستحصل على الإجابة الواضحة.

بيت القصيد من جدول البحث هو تجنب الإضافة.

Answer 3

عذرا على هذا المنصب في وقت متأخر، ولكنني وجدت التحدي للتو.بلدي $.02 (القوة الغاشمة)

Private Sub Button1_Click(ByVal sender As System.Object, _
                          ByVal e As System.EventArgs) Handles Button1.Click

    For x As Integer = 0 To 255
        Debug.WriteLine(bitsOn2(CByte(x)) & " " & Convert.ToString(x, 2).PadLeft(8, "0"c))
    Next

End Sub

Private Function bitsOn(ByVal aByte As Byte) As Integer
    Dim aBit As Byte = 1
    For z As Integer = 0 To 7
        If (aByte >> z And aBit) = aBit Then bitsOn += 1
    Next
End Function

Dim aDict As New Dictionary(Of Integer, Integer)
Private Function bitsOn2(ByVal aByte As Byte) As Integer
    If aDict.Count = 0 Then 'init dictionary
        For x As Integer = 0 To 255
            aDict.Add(x, bitsOn(CByte(x)))
        Next
    End If
    Return aDict(aByte)
End Function