#include <cassert>
#include <climits>
#include <cstdint>
#include <cstdio>
template <uint8_t d, typename int_type>
int_type get_matches_naive(int_type b)
{
int_type ret = 0;
for (size_t i = 0; i < sizeof(int_type); i++)
if (((b >> i * CHAR_BIT) & 0xff) == d)
ret |= (int_type)0x80 << i * CHAR_BIT;
return ret;
}
template <uint8_t d, typename int_type>
int_type get_matches_bitwise(int_type b)
{
// based on
// https://g...content-available-to-author-only...d.edu/~seander/bithacks.html#HasLessInWord
constexpr int_type mask_0x01 = (int_type)~0 / (int_type)0xff;
constexpr int_type mask_0x7f = (int_type)0x7f * mask_0x01;
constexpr int_type mask_0x80 = (int_type)0x80 * mask_0x01;
constexpr int_type mask_d = d * mask_0x01;
int_type matches_as_0x00 = mask_d ^ b;
int_type matches_as_0x80 = (mask_0x80 - (matches_as_0x00 & mask_0x7f)) &
~matches_as_0x00 & mask_0x80;
return matches_as_0x80;
}
template <uint8_t d, typename int_type>
void test()
{
int_type b = 0;
do
{
assert((get_matches_naive<d, int_type>(b) ==
get_matches_bitwise<d, int_type>(b)));
} while(--b != 0);
}
template <uint8_t d, typename int_type>
struct aux
{
static void do_test()
{
test<d, int_type>();
aux<d - 1, int_type>::do_test();
}
};
template <typename int_type>
struct aux<0, int_type>
{
static void do_test()
{
test<0, int_type>();
}
};
int main()
{
aux<0xff, uint16_t>::do_test();
// TAKES TOO LONG FOR IDEONE
//aux<0xff, uint32_t>::do_test();
return 0;
}
I2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPGNzdGRpbz4KCnRlbXBsYXRlIDx1aW50OF90IGQsIHR5cGVuYW1lIGludF90eXBlPgppbnRfdHlwZSBnZXRfbWF0Y2hlc19uYWl2ZShpbnRfdHlwZSBiKQp7CiAgICBpbnRfdHlwZSByZXQgPSAwOwogICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCBzaXplb2YoaW50X3R5cGUpOyBpKyspCiAgICAgICAgaWYgKCgoYiA+PiBpICogQ0hBUl9CSVQpICYgMHhmZikgPT0gZCkKICAgICAgICAgICAgcmV0IHw9IChpbnRfdHlwZSkweDgwIDw8IGkgKiBDSEFSX0JJVDsKICAgIHJldHVybiByZXQ7Cn0KCnRlbXBsYXRlIDx1aW50OF90IGQsIHR5cGVuYW1lIGludF90eXBlPgppbnRfdHlwZSBnZXRfbWF0Y2hlc19iaXR3aXNlKGludF90eXBlIGIpCnsKICAgIC8vIGJhc2VkIG9uCiAgICAvLyBodHRwczovL2cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmQuZWR1L35zZWFuZGVyL2JpdGhhY2tzLmh0bWwjSGFzTGVzc0luV29yZAogICAgY29uc3RleHByIGludF90eXBlIG1hc2tfMHgwMSA9IChpbnRfdHlwZSl+MCAvIChpbnRfdHlwZSkweGZmOwogICAgY29uc3RleHByIGludF90eXBlIG1hc2tfMHg3ZiA9IChpbnRfdHlwZSkweDdmICogbWFza18weDAxOwogICAgY29uc3RleHByIGludF90eXBlIG1hc2tfMHg4MCA9IChpbnRfdHlwZSkweDgwICogbWFza18weDAxOwogICAgY29uc3RleHByIGludF90eXBlIG1hc2tfZCA9IGQgKiBtYXNrXzB4MDE7CiAgICBpbnRfdHlwZSBtYXRjaGVzX2FzXzB4MDAgPSBtYXNrX2QgXiBiOwogICAgaW50X3R5cGUgbWF0Y2hlc19hc18weDgwID0gKG1hc2tfMHg4MCAtIChtYXRjaGVzX2FzXzB4MDAgJiBtYXNrXzB4N2YpKSAmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB+bWF0Y2hlc19hc18weDAwICYgbWFza18weDgwOwogICAgcmV0dXJuIG1hdGNoZXNfYXNfMHg4MDsKfQoKdGVtcGxhdGUgPHVpbnQ4X3QgZCwgdHlwZW5hbWUgaW50X3R5cGU+CnZvaWQgdGVzdCgpCnsKCWludF90eXBlIGIgPSAwOwoJZG8KCXsKCQlhc3NlcnQoKGdldF9tYXRjaGVzX25haXZlPGQsIGludF90eXBlPihiKSA9PQoJCSAgICAgICAgZ2V0X21hdGNoZXNfYml0d2lzZTxkLCBpbnRfdHlwZT4oYikpKTsKCX0gd2hpbGUoLS1iICE9IDApOwp9Cgp0ZW1wbGF0ZSA8dWludDhfdCBkLCB0eXBlbmFtZSBpbnRfdHlwZT4Kc3RydWN0IGF1eAp7CglzdGF0aWMgdm9pZCBkb190ZXN0KCkKCXsKCQl0ZXN0PGQsIGludF90eXBlPigpOwoJCWF1eDxkIC0gMSwgaW50X3R5cGU+Ojpkb190ZXN0KCk7Cgl9Cn07Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgaW50X3R5cGU+CnN0cnVjdCBhdXg8MCwgaW50X3R5cGU+CnsKCXN0YXRpYyB2b2lkIGRvX3Rlc3QoKQoJewoJCXRlc3Q8MCwgaW50X3R5cGU+KCk7Cgl9Cn07CgppbnQgbWFpbigpCnsKCWF1eDwweGZmLCB1aW50MTZfdD46OmRvX3Rlc3QoKTsKCS8vIFRBS0VTIFRPTyBMT05HIEZPUiBJREVPTkUKCS8vYXV4PDB4ZmYsIHVpbnQzMl90Pjo6ZG9fdGVzdCgpOwoJcmV0dXJuIDA7Cn0K