The NSA Instruction (2019)

Re:The NSA Instruction (2019) by amalcon on Friday June 11, 2021 @10:44AM (#27474062)

A neat one for large, sparse integers is:

  for(i=0; !x; ++i) {
    x = (x-1)&x
  }
  return i;

Which runs only a number of iterations equal to the number of 1 bits. This works because (x-1) actually just flips the rightmost 1 bit and all zeroes to its right, then the & zeroes all of those.

It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.

[ Parent | on HN ]

Re:The NSA Instruction (2019) by pbsd on Friday June 11, 2021 @11:47AM (#27474866)

When the integer is expected to be dense, you have the corresponding trick

    size_t count = sizeof(x) * 8;
    while(x != -1) {
        x |= x+1;
        --count;
    }
    return count;

[ Parent | on HN ]

Re:The NSA Instruction (2019) by throw5away on Friday June 11, 2021 @04:40PM (#27478195)

This is essentially equivalent to feeding the input through bitwise-NOT first. Unfortunately, there are far more integers that are neither sparse nor dense than integers that are sparse or dense.

[ Parent | on HN ]

Re:The NSA Instruction (2019) by jffry on Friday June 11, 2021 @08:15PM (#27480072)

But I can certainly imagine there could be problem domains where most of some collection of integers being manipulated are expected to be sparse or dense.

[ Parent | on HN ]