How to "increment" to the next possible function Let $a$ and $b$ be two integers, where their size is constrained to $2$ bits in binary. There exists a function $f$, which outputs integers of the same size, where $f(a) = f(b) = y$. For example, $a = 01$, $b = 10$, and $y = 11$.
There exist some possible functions, such as $g(x) = x \oplus 10$. Another could be $h(x) = x + 01$ (ignoring overflow). However, in terms of their results, many of these would essentially be the same function, mapping the same inputs to the same outputs.
What is the "common denominator", so to speak, that would allow seeing all functions as the same?
The purpose of this is to be able to "increment" a function. In the first example, suppose I do not know what f is, and I want to write a program to find it. I know that $f(a)=f(b)$, so I could write a loop to try all the possible functions by "incrementing" the function after each iteration, until the function that has $f(A)=f(B)$ is found. Ultimately this will be used on larger sized, and possibly differently sized, inputs and outputs.
 A: There are exactly $\left(2^n\right)^{2^m}=2^{\left(n\cdot 2^m\right)}$ distinct functions that map $m$-bit integers into $n$-bit integers. This is easily seen by considering the vector $<f(0)|f(1)|...|f(2^m)>$ (with a total of $2^m$ subfields of $n$ bits each) for a generic function $f$.
Note that $g\equiv f$ if and only if their vectors coincide, and that every vector of $n\cdot 2^m$ bits can be interpreted as a function from $m-$bit integers to $n-$bit integers - so you can "go through" the entire set of all your functions by "going through" the corresponding set of vectors.
Also note that even for smallish $m,n$ the number $2^{\left(n\cdot 2^m\right)}$ can be pretty large. For $m=n=2$ it equals $256$. For $m=n=4$ it's already $2^{64}> 10^{19}$ and you'd be hard pressed to go through all these functions in a reasonable time on a PC. For $m=n=6$, you are looking at $2^{384}$, which is more than the number of elementary particles in the known universe; going through these many functions appears well beyond the computational power available to the entire human civilization in the foreseeable future.
