fork(4) 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 parent(const uint32_t node)
  16. {
  17.     uint32_t x = node;
  18.  
  19.     while (x > 2)
  20.     {
  21.         const uint32_t y = x + popcnt(x);
  22.         const uint32_t bit = getMSBmask(y & ~x);
  23.         const uint32_t mask = (bit << 1) - 1;
  24.         x = (x & mask) + popcnt(x & ~mask);
  25.     }
  26.  
  27.     return node + 1 + (x == 1);
  28. }
  29.  
  30. uint32_t test(const int32_t depth)
  31. {
  32.     if (depth)
  33.     {
  34.         const uint32_t left = test(depth - 1);
  35.         const uint32_t right = test(depth - 1);
  36.         ++node_id;
  37.         if (depth == 1 && left != node_id) ++failed;
  38.         if (depth == 1 && right != node_id) ++failed;
  39.     }
  40.     else
  41.     {
  42.         ++node_id;
  43.     }
  44.  
  45.     return (depth == 0)? parent(node_id): 0;
  46. }
  47.  
  48. int main()
  49. {
  50.     test(23);
  51.     std::cout << "nodes: " << node_id << '\n';
  52.     std::cout << "failed: " << failed << '\n';
  53. }
  54.  
Success #stdin #stdout 0.7s 3340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
nodes: 16777215
failed: 0
https://ideone.com/0sVNgL
language:
C++14 (gcc 8.3)
created:
10 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!