Find the binary input function given the outputs

Question

Here we have three binary variables $x_1$, $x_2$, $x_3$ $\in \{0,1\}$.
I want to find the form of the function $f(x_1, x_2, x_3)$ such that the following are satisfied:

if $\ x_1 = 0,\ x_2 = 0,\ x_3 = 0 \ $ then $\ f(x_1, x_2, x_3) = 0$
if $\ x_1 = 0,\ x_2 = 0,\ x_3 = 1 \ $ then $\ f(x_1, x_2, x_3) = 3$
if $\ x_1 = 0,\ x_2 = 1,\ x_3 = 0 \ $ then $\ f(x_1, x_2, x_3) = 2$
if $\ x_1 = 0,\ x_2 = 1,\ x_3 = 1 \ $ then $\ f(x_1, x_2, x_3) = 3$
if $\ x_1 = 1,\ x_2 = 0,\ x_3 = 0 \ $ then $\ f(x_1, x_2, x_3) = 1$
if $\ x_1 = 1,\ x_2 = 0,\ x_3 = 1 \ $ then $\ f(x_1, x_2, x_3) = 3$
if $\ x_1 = 1,\ x_2 = 1,\ x_3 = 0 \ $ then $\ f(x_1, x_2, x_3) = 2$
if $\ x_1 = 1,\ x_2 = 1,\ x_3 = 1 \ $ then $\ f(x_1, x_2, x_3) = 3$

I imagine it like having a "virtual sum" which is increased by one each step in the sequence. Every time I see a one, this virtual sum "becomes real" and is zeroed. For instance:

• $\ x_1 = 0,\ x_2 = 0,\ x_3 = 1 \ $. After seeing the first zero the virtual sum is 1. After the second zero the virtual sum is 2. Finally there is a one, so the virtual sum becomes 3 and is reset. The final result is 3.
• $\ x_1 = 0,\ x_2 = 0,\ x_3 = 0 \ $ We have three zero, so the virtual sum is 3 at the end of the sequence. However, since there are no ones it does not "become real" and the result is 0.

In the two variables case it is enough to write $f(x_1, x_2) = x_1 + x_2$, but in higher dimensions things start to become more difficult.

Answer 1

What you are looking for is simply the last bit set.

You can reverse this, and instead count the sequence of zeroes at the end instead. This has a simple pattern:

1. At least one zero at the end: $(1 - x_3)$.

2. At least two zeroes at the end: $(1 - x_3)(1 - x_2)$.

3. At least three zeroes at the end: $(1 - x_3)(1 - x_2)(1 - x_1)$.

So we get our total expression as:

$$3 - (1 - x_3) - (1 - x_3)(1 - x_2) - (1 - x_3)(1 - x_2)(1 - x_1)$$

Answer 2

If you sort in ascending order of $f$, you can think $f(x_1, x_2, x_3)$ as the maximum index of the variable on, i.e. $f(x_1, x_2, x_3)=max\{i\, :\, x_i=1\}$