Шаблоны установки битов в байте

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  

Повторите этот процесс еще два раза, и сверху вы получите сетку 16x16, поэтому я решил, что должен быть какой-то алгоритм квадродерева, который позволит вам начать с сетки:

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

Извините за поздний пост, но я только что нашел вызов.Мой 0,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