Byte Bit Patterns

Question

Joel mentioned counting the number of bits in a byte as a programming issue in his Guerrilla Guide to Interviewing and talked about a way to use patterns that appear in the lookup table. I wrote an article about this a while ago after I found a template.

Summarizing:

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 

The first row and column exactly match, and each position in the grid can be calculated by adding the first values ​​to this row and column. Because of this, you only need a lookup table with 16 elements for an 8-bit number and can only use the first 16 numbers. Then, if you want, for example, to count the number of bits in the number 243, you simply do:

 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 

The following pattern, which I noticed after that, was that every time you double the size of the NxN grid, each quadrant can be calculated by adding 0, 1, 1 and 2 to each quadrant, respectively:

 # 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 

Repeat this process two more times and you will get a 16x16 grid on top, so I decided there should be some kind of quadtree algorithm that allows you to start with the grid:

 0 1 1 2 

and a given number N, generate a lookup table "on the fly" and calculate the number of bits. So my question / task: can you find an algorithm for this?

Answer 1

Based on Robert's code here , this can be done even without division or module, replacing them with one shift and one AND, for example:

 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 

Or in C:

 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 } 

For any size integer, you can just skip the bytes and do a quick search, for example:

 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 

I am pleased with this answer. I knew something was more complicated and quadtree-esque would not be effective, I just thought it was a worthy thought experiment.

Answer 2

This is a stupid question! In the first example, where you calculated the number of bits set using a table with 16 inputs instead of 256, is not something magical! All you have done is count the number of bits set in the first four bits of a byte (the first nibble), and then in the second nibble by adding them together. x / 16 is the first nibble, x% 16 is the second piece.

If you repeat this process, you now have a lookup table for two bits, and you just do it four times, once for each pair. As a last resort, you can just add all the bits together one by one, and you will get the obvious answer.

The whole point of the lookup table is to avoid adding.

Answer 3

Sorry for the last post, but I just found the call. My $ 0.02 (brute force)

 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