code: private int allocateNode(int d) {
          int id = 1;
          int initial = - (1 << d); // has last d bits = 0 and rest all = 1
          byte val = value(id);
          if (val > d) { // unusable
              return -1;
          }
          while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
              id <<= 1;
              val = value(id);
              if (val > d) {
                  id ^= 1;
                  val = value(id);
              }
          }
          byte value = value(id);
          assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d",
                  value, id & initial, d);
          setValue(id, unusable); // mark as unusable
          updateParentsAlloc(id);
          return id;
      }
docs: Algorithm to allocate an index in memoryMap when we query for a free node
  at depth d
  
  @param d depth
  @return index in memoryMap