Whoa. Some links (with sometimes not-very-well-thought-out allegations):

https://groups.google.com/forum/#!topic/comp.arch/UXEi7G6WHu...

https://www.schneier.com/blog/archives/2014/05/the_nsa_is_no...

Even boring old Java has had Integer.bitCount for many years.

I think the point is that Rust makes it much easier to use that opcode instruction. It's possible but hard with GCC using __builtin_popcount(), but, I'd guess totally impossible in Java due to lack of a JVM instruction for the same.

If you look at the openjdk9 sources you will notice that it is annotated as intrinsic candidate[0]. But earlier versions also have intrinsics for that[1], it's just not annotated as such.

[0] http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/23721aa1d87f/s... [1] https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc#file-ho...

I don't understand why you would guess at what Java can do when you can find out for certain?

    public class Test {
      
      private static int bitCount(int a) {
        return Integer.bitCount(a);
      }
      
      public static void main(String[] args) {
        while (true) {
          bitCount(14);
        }
      }
      
    }

    0x000000011e637980: sub    rsp,0x18
    0x000000011e637987: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                  ; - Test::bitCount@-1 (line 4)

    0x000000011e63798c: popcnt eax,esi            ;*invokestatic bitCount
                                                  ; - Test::bitCount@1 (line 4)

    0x000000011e637990: add    rsp,0x10
    0x000000011e637994: pop    rbp
    0x000000011e637995: test   DWORD PTR [rip+0xfffffffff10ed665],eax        # 0x000000010f725000
                                                  ;   {poll_return}
    0x000000011e63799b: ret 

https://github.com/bobbyi/Fast-Bit-Counting

Doing it by table lookup results in questions such as "am I wasting too much cache space on this?" and "is a 64K table causing cache misses".

Here are a few of the scalar intrinsics for bit counting.

  popcnt() - population count
  leadz() - leading zero
  trailz() - trailing zero
  poppar() - parity

Edited to fix formatting.

TFTFY :-)

        push    rbp
        mov     rbp, rsp
        popcnt  eax, edi
        pop     rbp
        ret

[1]: https://gcc.gnu.org/onlinedocs/gcc-3.4.4/gcc/Optimize-Option...

  example::count:
        popcnt  eax, edi
        ret

rbp points to the base of the current stack frame (register base pointer) and rsp points to the top of the current stack frame (register stack pointer).

What the function actually does is just the single popcnt instruction.

But this is a leaf-function and one that has no register trashing or temporary variables. Could this be inlined later on via link-time optimizations? Will the linker then remove that function prologue and epilogue?

The example with slightly different options (as mentioned in another comment) gives what you're looking for: https://godbolt.org/g/GlkEQK

In case you're wondering what this could be useful for besides super secret NSA stuff, and Bitcoin mining, here are a few suggestions:

1) hyperloglog. (Similar to Bitcoin). Keep an estimated count of items streaming by by hashing them and store the highest lzcount of the hashes for each category you're tracking. This will be ~ log2(category count)

2) converting from fixed point to floating point. The number of zeros in front of your value represents the exponent of your value (or ones in the case of a 2's complement negative fixed point), which is critical to deducting the float representation.

Along those lines, one of the things I've done is implemented floating point-like datatypes, which extensively uses lzcount and locount for tracking values and also will use tzcount to measure if the values are exact or not.

https://github.com/Etaphase/FastSigmoids.jl/blob/master/READ...

It's unclear how well the benchmarks in this linked article generalize to other applications. If you are just popcounting in a tight loop, probably pretty well, but who does that? In reality you have other things going on, so if this method is occupying too many execution units or polluting your cache, you would see the effect of that on the rest of the program. But it's program-dependent, thus unclear.

https://doc.rust-lang.org/std/primitive.u64.html#method.coun...

https://doc.rust-lang.org/std/primitive.u128.html#method.cou...

Of course to benefit from the SSE optimizations you would still have to call it in a loop and the optimizer would have to recognize that and replace it with a vectorized approach.

C's weak typing should handle signed

Oh, Hacker News.

If someone can't solve a problem like this off the top of their head, does it not act as a strong signal that they are a beginner and you should probably look elsewhere for quality information?

The intent of my comment is not to be mean, it's just ... there is a lot of noise on places like Hacker News and this article is part of that noise because, look, just about all compilers have had intrinsics for decades now at least, popcount is a very common one, so it's not surprising to see it turn up. It's not impressive as the title suggests, it's extremely common. And it's nothing specific about Rust because most production-quality languages do it. So both major elements of the article title are pretty much incorrect.

And it's fine not to know that when you're a beginner, I am not knocking that at all. But there's something about writing articles that then get broadcast, that give the wrong impression to other new people who are trying to learn. It's useful information that there is a popcount intrinsic in the Rust compiler, but this would be much more educational coming from someone who understands the context of all this stuff and can explain the real situation. Which may be the author of this article someday, maybe even someday very soon -- I don't wish to be inappropriately negative -- but it's not today.

I never liked going to school, and I think higher education is going to go through an existential crisis pretty soon, if it's not happening already. But one good thing about the old system is that at least there was this idea that you should work hard, and really learn the material, before you go presuming to teach people. And I think that's a very good idea. If you're inexperienced and there's a shortage of teachers and teaching needs to happen, then go for it -- but otherwise I think it is very important to keep in mind what one does and does not understand, and who understands it better, and to not presume to teach until one is in a good position to do so.

I know this goes a little bit against the current philosophy of "programming is great! Anyone can do it! Rah rah," but actually I think on closer inspection it doesn't. There's nothing wrong with participation, and community, and everyone contributing, etc. But it's important to keep an understanding of the difference between beginner contributions and advanced contributions, otherwise it seems possible to suffer a severe degradation of skill in the field over time, because how do people know what to shoot for if people of all expertise levels are teaching them and they can't tell the difference because they themselves are beginners?