$g$
can be defined from set $A = \{0,1, \cdots, 2^n  1, 2^n\}$
to set $B = \{0, \cdots, n\}$
such that $g(2^x) = x$
for all $x$
in $B?$

Without any restriction, for each input
$x,$
how many possible output values$g(x)$
are there? 
How do we count the number of possible functions between two sets when we know the sets’ cardinality?

How many output values could an input of the form
$2^x$
take if$x$
is in$B?$

How many output values could an input of a different form take?

To calculate the number of functions we count how many possible outputs there are for each input. In this case we also have a restriction. For each input of the form
$2^x,$
where$x$
is in$B,$
the output value is fixed to$x;$
that is, every function we define must include these relationships, so the number of possible functions we can define is given only by the other inputs. This leaves only$2^nn$
“free” inputs, and for each of these the output could be any of the$n+1$
elements in$B.$
Therefore, the number of functions that can be defined is$(n+1)^{2^{n}  n}.$