Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted? Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:

$m = (n(n+1)/2)\ \bmod 2^{64}$

It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\rfloor$ . For all other numbers the inversion is not that trivial but I have the feeling it could be done without brute force.
As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.