Counting Binary Functions
Determine the number of mappings from n-bit binary numbers to m-bit binary numbers
Example of a 4-bit to 1 bit mapping.
The function f1 maps a 4 bit number into its parity (0=even, 1 = odd).
Hence, f1(0010) = f1(0111) = 1 and
f1(1111) = f1(0000) = 0.
Example of an 8-bit to 3 bit mapping.
The function f2 maps an 8-bit binary number into a 3 bit binary number as follows.
f2(x) = y where y is the number of 1s in x's binary representation. So, for example,
f2(14) = f2(00001110) = 3 = 011 and
f2(128) = f2(10000000) = 1 = 001
Let f be a mapping from an n-bit number to an m-bit number.
f has N = 2n different possible inputs.
Each input could be mapped to any one of M = 2m outputs.
Hence,
0 could be mapped to any one of M different outputs and
1 could be mapped to any one of M different outputs,
...
2n - 1 could be mapped to M different outputs.
Therefore the number of possible mappings is M * M * M ... * M for N factors = MN.
So, for example, there are 2256 functions that map an 8 bit number to a 1 bit number.
Remarkably, 2256 approximately equals 1.158*1077
And, almost unbelievably, there are 64,53664,536 functions that map a 16 bit number to another 16 bit number!
Top of this page 
Home page 
