The NSA Instruction (2019)

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 ]