How to compute a curious inverse
This problem can be cast into a familiar form: it's an example of what is known as a 0-1 linear programming problem. You have a set of variables $v_1, v_2, \dots v_n$ subject to constraints of the form $m\le a_1v_1+a_2v_2+\cdots +a_nv_n\le M$. In your particular problem, we also have $a_i \in \{0, 1\}$. You are looking for any feasible solutions, namely tuples $(v_1, \dots, v_n)$ which satisfy all the constraints.

For example, suppose we have
$$
M = \left( \begin{array}{cccc}
         0 &amp; 0 &amp; 1 &amp; 0\\
         1 &amp; 1 &amp; 0 &amp; 1\\
         1 &amp; 1 &amp; 1 &amp; 0\\
         0 &amp; 1 &amp; 1 &amp; 1
       \end{array} \right), \quad{\text{and}}\quad
z= \left( \begin{array}{c}
     0\\1\\0\\1
   \end{array}\right)
$$
then you want 
$$
v= \left( \begin{array}{c}
     a\\b\\c\\d
   \end{array}\right)
$$
such that $Mv$ will be, in binary (with the lower-order bit unspecified)
$$
Mv=\left(\begin{array}{c}
c \\ a+b+d \\ a + b + c \\ b + c + d 
\end{array}\right)
=\left(\begin{array}{c}
\mathtt{0\_}\\ \mathtt{1\_}\\ \mathtt{0\_}\\ \mathtt{1\_}
\end{array}\right)
$$
From this we have the constraints
$$
\begin{array}{c}
0\le a, b, c, d\le 1\\
2\le a + b + d\le 3\\
0\le a + b + c\le 1\\
2\le b + c + d\le 3
\end{array}
$$
and you want to find $a, b, c, d$ such that all the constraints are simultaneously satisfied.
We've moved into 0-1 LP land because there are established procedures for solving problems like this, though sadly there's nowhere near enough room in this post to introduce them, so you'll have to do the legwork yourself. Be aware that problems like this are very compute-intensive (by which I mean NP-hard) and as far as I know you're not going to get anything like an elegant formulation of the form "This can be solved if and only if $z$ is of the form ..."

By the way, the example I used does indeed have a solution, $v$, and in this particular case is unique, though in general you'll have several solutions (if there are any at all).