fork(11) download
copy 
  1. #include <iostream>
  2.  
  3. uint32_t node_id = 0;
  4. uint32_t failed = 0;
  5.  
  6. uint32_t popcnt(const uint32_t x)
  7. { return __builtin_popcount(x); }
  8.  
  9. uint32_t getMSBindex(const uint32_t x)
  10. { return 31 - __builtin_clz(x); }
  11.  
  12. uint32_t getMSBmask(const uint32_t x)
  13. { return 1 << getMSBindex(x); }
  14.  
  15. uint32_t notSimpleCase(const uint32_t x)
  16. { return ((x+1) & x) && ((x+2) & (x+1)); }
  17.  
  18. /*
  19. uint32_t parent(const uint32_t node)
  20. {
  21.     uint32_t x = node;
  22.  
  23.     while (notSimpleCase(x))
  24.     {
  25.         x &= ~getMSBmask(x);
  26.         ++x;
  27.     }
  28.  
  29.     return node + 1 + (((x+1) & x)? 0: x);
  30. }
  31.  
  32. uint32_t parent(const uint32_t node)
  33. {
  34.     uint32_t x = node;
  35.     uint32_t mid = getMSBindex(node) / 2;
  36.  
  37.     while (notSimpleCase(x) && mid >= 3)
  38.     {
  39.         const uint32_t mask = (1 << mid) - 1;
  40.         const uint32_t y = (x & mask) + popcnt(x & ~mask);
  41.  
  42.         if ((y & ~mask) || y == mask) // overflow
  43.             break;
  44.  
  45.         x = y;
  46.         mid /= 2;
  47.     }
  48.  
  49.     while (notSimpleCase(x))
  50.     {
  51.         x &= ~getMSBmask(x);
  52.         ++x;
  53.     }
  54.  
  55.     return node + 1 + (((x+1) & x)? 0: x);
  56. }
  57. */
  58.  
  59. uint32_t parent(const uint32_t node)
  60. {
  61.     uint32_t x = node;
  62.     uint32_t bit = x;
  63.  
  64.     while ((x & bit) && notSimpleCase(x))
  65.     {
  66.         const uint32_t y = x + popcnt(x);
  67.         bit = getMSBmask(y & ~x);
  68.         const uint32_t mask = (bit << 1) - 1;
  69.         const uint32_t z = (x & mask) + popcnt(x & ~mask);
  70.  
  71.         if (z == mask && (x & (bit << 1)))
  72.             return node + 1;
  73.  
  74.         x = z;
  75.     }
  76.  
  77.     if (notSimpleCase(x))
  78.         return node + 1;
  79.     else
  80.         return node + 1 + (((x+1) & x)? 0: x);
  81. }
  82.  
  83. uint32_t test(const int32_t depth)
  84. {
  85.     if (depth)
  86.     {
  87.         const uint32_t left = test(depth - 1);
  88.         const uint32_t right = test(depth - 1);
  89.         ++node_id;
  90.         if (left != node_id) ++failed;
  91.         if (right != node_id) ++failed;
  92.     }
  93.     else
  94.     {
  95.         ++node_id;
  96.     }
  97.  
  98.     return parent(node_id);
  99. }
  100.  
  101. int main()
  102. {
  103.     test(23);
  104.     std::cout << "nodes: " << node_id << '\n';
  105.     std::cout << "failed: " << failed << '\n';
  106. }
  107.  
Success #stdin #stdout 1.37s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
nodes: 16777215
failed: 0
https://ideone.com/77e1tF
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

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!