31–40 of 98 posts
>You might be wondering, like I was, if there’s more to this instruction, but that’s all it does! This doesn’t seem very useful, right? I have a hard time understanding how anybody who has done most any non-trivial amount of bit maniplation couldn't think of plenty of uses.
Why did you write this comment?
https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC...
It is also incredibly useful for doing string scanning - look at strlen/strchr in various libc imp lementations
Obviously using a dedicated instruction is fastest in normal cases. But if you need to implement popcount or many other bit manipulation algorithms in software, a good book to look at is "Hacker's Delight" by Henry S. Warren, Jr, 2003. "Hacker's Delight' page 65+ discuss "Counting 1-bits" (population counts). There are a lot of software algorithms to do this. One approach is to set each 2-bit field to the count of 2…
for(i=0; !x; ++i) {
x = (x-1)&x
}
return i;
It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.
Earlier quoted context omitted.
Yep, I've used __builtin_popcountll for ORB from OpenCV (256 bit binary descriptors).
Looks like we've done similar things :) Horror story: I was once developing a TRN system for a spacecraft instrument which uses an ancient x86 processor that does not have popcnt, ended up using a look-up table instead...
Earlier quoted context omitted.
But taken in the context of the whole article, it adds nothing of any value. The author literally spends the rest of the post describing how it is useful. Saying 'doesn't seem useful, does it?' at the beginning is a rhetorical device. The author is assuming that the reader probably doesn't have experience using bit manipulations for complex problems. I am so tired of HN pedantry.
How else are we supposed to feel intellectually superior to literally everyone if we're not pedantic assholes to each other?
There's an adversarial air that exists around dissecting, criticizing, nit-picking etc ideas presented, both here and in the tech world at large. As if one's most valuable contribution to a conversation is assuming the role of smug contrarian.
It's frankly tiring and obnoxious. I used to think non-geeks were just bad at communicating with us; that the fault was on their side somehow. But now I think we're just dicks.
Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The ma…
Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The ma…
If I recall the Knuth lecture correctly, given a "sheep and goats" instruction where one of the sets is packed in reverse order, you can implement any n-bit permutation in something like log2(n) instructions. I don't remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT.
PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount.
What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.
Obviously using a dedicated instruction is fastest in normal cases. But if you need to implement popcount or many other bit manipulation algorithms in software, a good book to look at is "Hacker's Delight" by Henry S. Warren, Jr, 2003. "Hacker's Delight' page 65+ discuss "Counting 1-bits" (population counts). There are a lot of software algorithms to do this. One approach is to set each 2-bit field to the count of 2…
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.
size_t count = sizeof(x) * 8;
while(x != -1) {
x |= x+1;
--count;
}
return count;