4 ms·

Can you do this with an xor and popcount? I suppose that's what the author is implying when they say the compiler takes care of this.

danbruc 5y ago
You can, the return statement is essentially a popcount. c1 = 0x8080808080808080 c2 = 0x7F7F7F7F7F7F7F7F c3 = 0x0101010101010101 e = ~(x ^ y) return popcount((e & c1) & ((e & c2) + c3)) For those wondering how this works. If two bytes are identical, then the XOR will yield 0x00 and the negation will yield 0xFF. Masking out the seven least significant bits with 0x80 will just yield 0x80 again. Masking out the most significant bit with 0x7F will just yield 0x7F again and adding 0x01 will yield 0x80. Finally combing 0x80 and 0x80 with AND just yields 0x80, i.e. exactly the most significant bit set. On the other hand if two bytes are not identical, then at least one of the two following things happens. The two bytes differ in the most significant bit and therefore the most significant bit of the XNOR is zero. Then masking out the seven least significant bits with 0x80 yields 0x00 and therefore the final AND yields 0x00. Or the two bytes differ in at least one of the seven least significant bits and therefore at least one of the seven least significant bits of the XNOR is zero. Then masking out the most significant bit with 0x7F yields something smaller than 0x7F and adding 0x01 yields something smaller than 0x80, i.e. the most significant bit is zero, and therefore the final AND again yields 0x00 because the first operand is either 0x00 or 0x80. The remaining work is to count the number of set bit, either with popcount or some other construction like the one in the article.
- sfink 5y ago
  Except this is suboptimal, as is the code in the original post: it specifies ASCII, so (e & c1) is guaranteed to be zero. In your code, that means you could just do return popcount((e & c2) + c3); (Thanks for writing this out, as otherwise I wouldn't have spotted it.)
  - danbruc 5y ago
    The author certainly meant extended ASCII and therefore you can not make this change. Sure, it may be technical incorrect but ASCII is so commonly used to refer to extended ASCII that this should probably be the default interpretation unless it is clear from the context, say a discussion of the history of character encodings, that it is meant in its original sense.
  - hairtuq 5y ago
    Actually, e is the inverse of the xor, so (e & c1) is guaranteed to be c1, and you still need popcount(c1 & ((e & c2) + c3)).
- hairtuq 5y ago
  Slightly simpler: c = x ^ y; return popcount(((c >> 1) | 0x8080808080808080) - c) & 0x8080808080808080);

danbruc 5y ago

You can, the return statement is essentially a popcount. c1 = 0x8080808080808080 c2 = 0x7F7F7F7F7F7F7F7F c3 = 0x0101010101010101 e = ~(x ^ y) return popcount((e & c1) & ((e & c2) + c3)) For those wondering how this works. If two bytes are identical, then the XOR will yield 0x00 and the negation will yield 0xFF. Masking out the seven least significant bits with 0x80 will just yield 0x80 again. Masking out the most significant bit with 0x7F will just yield 0x7F again and adding 0x01 will yield 0x80. Finally combing 0x80 and 0x80 with AND just yields 0x80, i.e. exactly the most significant bit set. On the other hand if two bytes are not identical, then at least one of the two following things happens. The two bytes differ in the most significant bit and therefore the most significant bit of the XNOR is zero. Then masking out the seven least significant bits with 0x80 yields 0x00 and therefore the final AND yields 0x00. Or the two bytes differ in at least one of the seven least significant bits and therefore at least one of the seven least significant bits of the XNOR is zero. Then masking out the most significant bit with 0x7F yields something smaller than 0x7F and adding 0x01 yields something smaller than 0x80, i.e. the most significant bit is zero, and therefore the final AND again yields 0x00 because the first operand is either 0x00 or 0x80. The remaining work is to count the number of set bit, either with popcount or some other construction like the one in the article.

sfink 5y ago
Except this is suboptimal, as is the code in the original post: it specifies ASCII, so (e & c1) is guaranteed to be zero. In your code, that means you could just do return popcount((e & c2) + c3); (Thanks for writing this out, as otherwise I wouldn't have spotted it.)
- danbruc 5y ago
  The author certainly meant extended ASCII and therefore you can not make this change. Sure, it may be technical incorrect but ASCII is so commonly used to refer to extended ASCII that this should probably be the default interpretation unless it is clear from the context, say a discussion of the history of character encodings, that it is meant in its original sense.
- hairtuq 5y ago
  Actually, e is the inverse of the xor, so (e & c1) is guaranteed to be c1, and you still need popcount(c1 & ((e & c2) + c3)).
hairtuq 5y ago
Slightly simpler: c = x ^ y; return popcount(((c >> 1) | 0x8080808080808080) - c) & 0x8080808080808080);