slide 20 of 23

Reductions: Summation

• Conventional C summation:

  t = 0;
  for (i=0; i<MAX; ++i) t += x[i];
  return(t);
  

• 4 8-bit fields in 32-bit register, SWAR summation:

  t = ((x & 0x00ff00ff) +
       ((x >> 8) & 0x00ff00ff));
  return((t + (t >> 16)) & 0x000003ff);
  

• Not really very expensive...
  C-coded SWAR summation of 1-bit fields easily outruns the Intel Pentium population count hardware instruction!