2

I want to count the number of set bits in a uint in Specman:

var x: uint;
gen x;
var x_set_bits: uint;
x_set_bits = ?;

What's the best way to do this?

Nathan Fellman
  • 122,701
  • 101
  • 260
  • 319

2 Answers2

4

One way I've seen is:

x_set_bits = pack(NULL, x).count(it == 1);

pack(NULL, x) converts x to a list of bits.
count acts on the list and counts all the elements for which the condition holds. In this case the condition is that the element equals 1, which comes out to the number of set bits.

Nathan Fellman
  • 122,701
  • 101
  • 260
  • 319
2

I don't know Specman, but another way I've seen this done looks a bit cheesy, but tends to be efficient: Keep a 256-element array; each element of the array consists of the number of bits corresponding to that value. For example (pseudocode):

bit_count = [0, 1, 1, 2, 1, ...]

Thus, bit_count2 == 1, because the value 2, in binary, has a single "1" bit. Simiarly, bit_count[255] == 8.

Then, break the uint into bytes, use the byte values to index into the bit_count array, and add the results. Pseudocode:

total = 0
for byte in list_of_bytes
    total = total + bit_count[byte]

EDIT

This issue shows up in the book Beautiful Code, in the chapter by Henry S. Warren. Also, Matt Howells shows a C-language implementation that efficiently calculates a bit count. See this answer.

Community
  • 1
  • 1
Brian Clapper
  • 25,705
  • 7
  • 65
  • 65
  • See http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html (from http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer) – jfs Jan 12 '09 at 13:39
  • Nathan, This may be more efficient in compiled code ( because Specman translates into C or C++), but you'd have to test whether this would be more efficient than the answer that you posted. Specman implements some data structures *very* poorly ( at least in 6.1 ). – Ross Rogers Jan 14 '09 at 15:16
  • Their dictionary implementation is extremely slow when you put a million items into it -- 1000 times slower than a similar dictionary in python. Who knows how they're really implementing lists. If you want speed, you should measure the performance of these two algorithms. – Ross Rogers Jan 14 '09 at 15:17
  • Using the built-in methods may be faster. Specman could be doing crazy things like copying their int object upon reference.... If you want to look at the code generated by Specman, search for "sn_compile.sh" on this page: – Ross Rogers Jan 14 '09 at 15:18
  • http://ldiracdelta.blogspot.com/2008/09/how-to-debug-environments-in-unix-or.html – Ross Rogers Jan 14 '09 at 15:18