fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zfIvMu
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!