Python, 29 bytes

lambda x,n:pow(x,2**n-1,2**n) 

This returns 0 for even x. It uses Euler’s theorem, with the observation that 2^n − 1 is divisible by 2^(n − 1) − 1, via Python’s builtin fast modular exponentiation. This is plenty fast enough for n up to 7000 or so, where it starts taking more than about a second.

Python 3.8 (pre-release), 25 bytes

lambda a,b:pow(a,-1,2**b) 

Try it online!

Haskell, 42 bytes

_!1=1 x!n|r<-x!div(n+1)2=(2-r*x)*r`mod`2^n 

Using an algorithm based on Hensel’s lemma that doubles the number of digits in every iteration, this runs in under a second for n up to about 30 million!

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f; 

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. \$x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\$, so \$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\$

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is \$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\$ and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f; 

or k=2 with

{:^((1${\.**2^?%}+*}:f; 

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if \$xy \equiv 1 \pmod{2^{k-1}}\$ then \$xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}\$, and if \$x\$ is odd we have \$x(y + xy-1) \equiv 1 \pmod{2^k}\$. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation \$y' = (x+1)y - 1\$ a suitable number of times.

Since \$0x \equiv 1 \pmod {2^0}\$ we get, by induction

\$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\$

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if \$x+1\$ is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f; 

which gives correct answers for inputs which have an inverse. However, it's not so simple when \$x\$ is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f; 

This seems to give sentinel values of either \$0\$ or \$2^{n-1}\$, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of \$0\$ for even numbers by changing the expression \$1 - (x+1)^n\$ into \$1 - 1^n\$:

{1$.1&*)1$?@/~)2@?%}:f; 

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large \$n\$. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f; 

Mathematica - 22

f=PowerMod[#,-1,2^#2]& 

f[x,n] returns y with x*y=1 mod 2^n, otherwise x is not invertible modulo 2^n

Python 3, 77 57 bytes

f=lambda x,n,b=1,i=1:n and f(x,n-1,b-(b&i)*~-x,i+i)or b%i 

Outgolfed all you snek users (except for the pow(x, -1, 2**n) cheapshots) with nothing but pure algorithm.

Try it online! (Only uses Python 3.8 for comparison against pow(a,-1,2**n))

Ungolfed version:

def func(value, shift, acc = 1, mask = 1): if value != 0: return func(value, shift - 1, acc - (acc & mask) * (value - 1), mask << 1) else: return acc & (mask - 1) 

Or, as a loop with size hacks removed:

def func(value, exponent): value -= 1 acc = 1 for i in range(exponent): if acc & (1 << i): acc -= value << i return acc & ((1 << i) - 1) 

Explanation

The function is a lambda called f. It takes two positive integers, and returns either the multiplicative modular inverse or zero.

You may be wondering what the heck is going on. This uses a different, faster, and smaller algorithm for modular inverse for powers of 2 instead of the Euclidian approach.

I'm not going to go too far into the details of why it works, as it is really complex and explained better by others. _{Translation: even I don't fully understand it.}

This set of algorithms is explained here on algassert with a related algorithm explained here on Crypto SE with some interesting papers linked.

This algorithm actually uses no true multiplication (just shifts), the multiplication is just a shortcut for size.

This naturally returns 0 for even numbers, as the odd subtraction (we start with x - 1) causes a chain reaction of trailing with 0b0, which, when masked off, turns the result to zero. No need for a manual sentinel.

0000 0001 - 0000 1101 -> 1111 0010 1111 0010 - 0001 1010 -> 1110 0000 

Ruby - 88 characters

Use the function f.

def e a,b;a%b==0?[0,1]:(x,y=e(b,a%b);[y,x-(y*(a/b))])end def f x,n;e(x,2**n)[0]*(x%2)end 

Simply the recursive function from the linked wiki page, returns 0 on error.

Pyth, 9 bytes

.^Et^2Q^2 

Try it here!

Takes input in reverse order. Or, 9 bytes too: .^EtK^2QK.

Explanation

 .^Et^2Q^2 - Full program. .^ - Pow function. The same in Python (pow). E - The second input. ^2Q - And 2 ^ first input. t - Decremented. ^2 - And 2 ^ first input again. 

GAP, 39 bytes

f:=function(x,n)return 1/x mod 2^n;end; 

f(x,n) returns the inverse of x modulo 2^n and gives an error message

Error, ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime 

if no inverse exists.

Jelly, 5 bytes

2*æi@ 

Try it online!

Takes input with \$n\$ first and \$x\$ second, returns \$0\$ if no such inverse exists. The Footer in the TIO link reverses the input for you and formats the test cases.

How it works

2*æi@ - Main link. Takes n on the left and x on the right 2* - Yield 2*n æi@ - Modular inverse of x, modulo 2*n, or if none exists, 0. 

C++ (gcc), 73 bytes

using l=unsigned;p(l a,l n){l r=1,t=1<<n;for(;n--;a*=a)r=r*a;return r%t;} 

for larger n, there's a 85-byte solution:

using l=unsigned __int128;p(l a,l n){l r=1,t=l(1)<<n;for(;n--;a*=a)r=r*a;return r%t;} 

GolfScript, 10 9 bytes

2\?:q(?q% 

Try it online!

A port of Mr. XCoder's solution, to GS. Stack manipulation is a little messy, could probably be done with a little tomfoolery. Takes in input as X N.

V 1.1 : Improved stack manip, it sucks a lot less now.

2\?:q(?q% #Multiplicative Inverse 2\ #Move "2" to the second pos on the stack. X 2 N ? #Exponentiate. X 2^N :q #Remember, q is 2^N. ( #Decrement. X 2^N-1 ? #Exponentiate. X^(2^N-1) q? #Mod by 2^N. # X^([2^N] -1) % 2^N is the multiplicative inverse, since # X^([2^N] -1)*X = X^(2^N) # which is 1 mod 2^N if X and 2^N are coprime. 

If there is no M.I., it will return 0.

JavaScript (Node.js), 34 bytes

n=>g=x=>x<2?x:x*g(x*x%(a=2n**n))%a 

Try it online!

Modified Power

JavaScript (Node.js), 50 bytes

f=(x,n,d=2n,c=1n)=>d>>n?c:x%2n&&f(x,n,d+d,c*x&d|c) 

Try it online!

Test each bit

APL(NARS), 89 chars

r←l w;b;e;n (b e n)←w⋄r←1 →3×⍳0=2∣e⋄r←n∣r×b b←n∣b×b⋄→2×⍳0<e←⌊e÷2 f←{l ⍺,(¯1+2x*⍵-1),2x*⍵} 

//12+14+18+21+24=89

I follow what some other have said that x^-1=x^((2^(n-1))-1)%n. For calculate that it, in my way of see there is need the ltor or powmod function, that here would be the function l.

f has need 2 arguments, in alpha the number for find the inverse, in omega the n. Return 0 if not exist inverse, otherwise return a integer positive. Not existe one inverse of all even numbers.

 5 f 100 1014120480182583521197362564301 (2x*100)∣5×5 f 100 1 4 f 100 0 (2x*100)∣99×99 f 100 1 99 f 100 409745648558619604524186894667