fork download 
  1. #include <cassert>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cstdint>
  5.  
  6. template <int N>
  7. int find_high_bits_in_byte_r(uint8_t x, int base_idx)
  8. {
  9.     uint8_t high = x >> N;
  10.     uint8_t low = ((1 << N) - 1) & x;
  11.     if (high > 0)
  12.     {
  13.         return find_high_bits_in_byte_r<N / 2>(high, base_idx + N);
  14.     }
  15.     else
  16.     {
  17.         return find_high_bits_in_byte_r<N / 2>(low, base_idx);
  18.     }
  19. }
  20.  
  21. template <>
  22. int find_high_bits_in_byte_r<0>(uint8_t x, int base_idx)
  23. {
  24.     return base_idx;
  25. }
  26.  
  27. int find_high_bits_in_byte(uint8_t x)
  28. {
  29.     return find_high_bits_in_byte_r<4>(x, 0);
  30. }
  31.  
  32. template <int N>
  33. bool is_greater_than_zero(uint8_t data[N])
  34. {
  35.     uint8_t zerofill[N] = { 0 };
  36.     auto retval = std::memcmp(data, zerofill, N);
  37.     return (retval != 0);
  38. }
  39.  
  40. template <int N>
  41. int find_high_bit_r(uint8_t data[N], int base_idx)
  42. {
  43.     union container_t {
  44.         uint8_t data[N];
  45.         struct
  46.         {
  47.             uint8_t low[N / 2];
  48.             uint8_t high[N / 2];
  49.         };
  50.     } c;
  51.     std::memcpy(c.data, data, N);
  52.  
  53.     if (is_greater_than_zero<N / 2>(c.high))
  54.     {
  55.         return find_high_bit_r<N / 2>(c.high, base_idx + N / 2);
  56.     }
  57.     else
  58.     {
  59.         return find_high_bit_r<N / 2>(c.low, base_idx);
  60.     }
  61. }
  62.  
  63. template <>
  64. int find_high_bit_r<1>(uint8_t data[1], int base_idx)
  65. {
  66.     auto bit_idx = find_high_bits_in_byte(data[0]);
  67.     return bit_idx + base_idx * 8;
  68. }
  69.  
  70. template <typename T>
  71. int find_high_bit(T x)
  72. {
  73.     if (x == 0)
  74.     {
  75.         return -1;
  76.     }
  77.  
  78.     union container_t {
  79.         T val;
  80.         uint8_t data[sizeof(T)];
  81.     };
  82.     container_t c;
  83.     c.val = x;
  84.     return find_high_bit_r<sizeof(T)>(c.data, 0);
  85. }
  86.  
  87. int main()
  88. {
  89.     for (int i = 0; i < 8; i++)
  90.     {
  91.         assert(i == find_high_bits_in_byte(1 << i));
  92.     }
  93.  
  94.     for (int i = 0; i < 32; i++)
  95.     {
  96.         assert(i == find_high_bit<uint32_t>(1 << i));
  97.     }
  98.  
  99.     assert(3 == find_high_bit<uint32_t>(0b1011));
  100.     assert(27 == find_high_bit<uint32_t>(0b00001000'00000100'00000010'00000001));
  101.  
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/LdQ3qu
language:
C++14 (clang 8.0)
created:
7 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!