fork download
  1. #include <cassert>
  2. #include <climits>
  3. #include <cstdint>
  4. #include <cstdio>
  5.  
  6. template <uint8_t d, typename int_type>
  7. int_type get_matches_naive(int_type b)
  8. {
  9. int_type ret = 0;
  10. for (size_t i = 0; i < sizeof(int_type); i++)
  11. if (((b >> i * CHAR_BIT) & 0xff) == d)
  12. ret |= (int_type)0x80 << i * CHAR_BIT;
  13. return ret;
  14. }
  15.  
  16. template <uint8_t d, typename int_type>
  17. int_type get_matches_bitwise(int_type b)
  18. {
  19. // based on
  20. // https://g...content-available-to-author-only...d.edu/~seander/bithacks.html#HasLessInWord
  21. constexpr int_type mask_0x01 = (int_type)~0 / (int_type)0xff;
  22. constexpr int_type mask_0x7f = (int_type)0x7f * mask_0x01;
  23. constexpr int_type mask_0x80 = (int_type)0x80 * mask_0x01;
  24. constexpr int_type mask_d = d * mask_0x01;
  25. int_type matches_as_0x00 = mask_d ^ b;
  26. int_type matches_as_0x80 = (mask_0x80 - (matches_as_0x00 & mask_0x7f)) &
  27. ~matches_as_0x00 & mask_0x80;
  28. return matches_as_0x80;
  29. }
  30.  
  31. template <uint8_t d, typename int_type>
  32. void test()
  33. {
  34. int_type b = 0;
  35. do
  36. {
  37. assert((get_matches_naive<d, int_type>(b) ==
  38. get_matches_bitwise<d, int_type>(b)));
  39. } while(--b != 0);
  40. }
  41.  
  42. template <uint8_t d, typename int_type>
  43. struct aux
  44. {
  45. static void do_test()
  46. {
  47. test<d, int_type>();
  48. aux<d - 1, int_type>::do_test();
  49. }
  50. };
  51.  
  52. template <typename int_type>
  53. struct aux<0, int_type>
  54. {
  55. static void do_test()
  56. {
  57. test<0, int_type>();
  58. }
  59. };
  60.  
  61. int main()
  62. {
  63. aux<0xff, uint16_t>::do_test();
  64. // TAKES TOO LONG FOR IDEONE
  65. //aux<0xff, uint32_t>::do_test();
  66. return 0;
  67. }
  68.  
Success #stdin #stdout 0.07s 3488KB
stdin
Standard input is empty
stdout

Standard output is empty