fork(11) download
  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
stdin
Standard input is empty
stdout
nodes: 16777215
failed: 0