Editing Lookup table (section)

====Counting bits in a series of bytes====
One discrete problem that is expensive to solve on many computers is that of counting the number of bits that are set to 1 in a (binary) number, sometimes called the ''[[Hamming weight|population function]]''. For example, the decimal number "37" is "00100101" in binary, so it contains three bits that are set to binary "1".<ref name="apress11">{{cite book|doi=10.1007/978-1-4302-4159-1_26|publisher=Apress|url=https://link.springer.com/chapter/10.1007/978-1-4302-4159-1_26|title= Developing for Performance. In: packetC Programming |author1=Jungck P.|author2=Dencan R.|author3=Mulcahy D.|year=2011|isbn=978-1-4302-4159-1}}</ref>{{rp|p=282}}

A simple example of [[C (programming language)|C]] code, designed to count the 1 bits in a ''int'', might look like this:{{r|apress11|p=283}}

<syntaxhighlight lang="c">
int count_ones(unsigned int x) {
  int result = 0;
  while (x != 0) {
    x = x & (x - 1);
    result++;
  }
  return result;
}</syntaxhighlight>

The above implementation requires 32 operations for an evaluation of a 32-bit value, which can potentially take several [[Cycles per instruction|clock cycles]] due to [[Control flow|branching]]. It can be "[[loop unrolling|unrolled]]" into a lookup table which in turn uses [[trivial hash function]] for better performance.{{r|apress11|p=282-283}}

The bits array, ''bits_set'' with 256 entries is constructed by giving the number of one bits set in each possible byte value (e.g. 0x00 = 0, 0x01 = 1, 0x02 = 1, and so on). Although a [[Runtime (program lifecycle phase)|runtime]] algorithm can be used to generate the ''bits_set'' array, it's an inefficient usage of clock cycles when the size is taken into consideration, hence a precomputed table is used—although a [[compile time]] script could be used to dynamically generate and append the table to the [[source file]]. Sum of ones in each byte of the [[Integer (computer science)|integer]] can be calculated through [[trivial hash function]] lookup on each byte; thus, effectively avoiding branches resulting in considerable improvement in performance.{{r|apress11|p=284}}

<syntaxhighlight lang="c">
int count_ones(int input_value) {
  union four_bytes {
    int big_int;
    char each_byte[4];
  } operand = input_value;
  const int bits_set[256] = {
      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};
  return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
          bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}}
</syntaxhighlight>