Binary calculation from mod 3 I have an $n$-bit binary number with following property:
$(a2^{n-1}+b2^{n-2}+k)\mod 3 = p$
If two most significant bits $a,b$ of the number cannot be both $1$ concurrently, is it possible to uniquely calculate $a,b$ given $k,n,p$?
 A: Since you specify $n$-digit binary numbers, I take your conditions to be $n>3$, $\,\,\,a,b,a',b'\in\{0,1\},\,\,\,0\le k<2^{n-2}$, $\,\,\,k,n\in\Bbb{N}$.
If both $$(a2^{n-1}+b2^{n-2}+k)\mod 3 = p$$ and $$(a'2^{n-1}+b'2^{n-2}+k)\mod 3 = p$$ with $(a,b)\neq(1,1),\,\,(a',b')\neq(1,1),\,\,(a',b')\neq(a,b)$, then there exist $\,\,M,M'\in \Bbb{Z},\,\,\, M\neq M'$ s.t. $$a2^{n-1}+b2^{n-2}+k = 3M +p$$ and $$a'2^{n-1}+b'2^{n-2}+k = 3M' +p$$
Subtracting the second equation from the first we obtain 
$(a-a')2^{n-1}+(b-b')2^{n-2}=3(M-M')$ 
$((a-a')2+(b-b'))2^{n-2}=3(M-M')\;\;\;{\rm(i)}$ 
Now, let’s observe that 
$(a-a'),(b-b') \in \{-1,0,1\}$ 
$(a-a',b-b')\neq(0,0) \Leftarrow (a,b)\neq(a',b')$
$(a-a',b-b')\neq(1,1) \Leftarrow (a,b)\neq(1,1)$
$(a-a',b-b')\neq(-1,-1) \Leftarrow (a',b')\neq(1,1)$
and we are left with $(a-a')\neq(b-b')$.
If $a-a'=0$, $\,\,{\rm(i)}$ becomes $\pm2^{n-2}=3(M-M')$, impossible because a power of 2 cannot be a multiple of 3. Similarly, if $b-b'=0$, $\,\,{\rm(i)}$ becomes $\pm2^{n-1}=3(M-M')$, also impossible. 
The only case left is $(a-a')2+(b-b')=\pm1$, which is also impossible because it would reduce ${\rm(i)}$ to $\pm2^{n-2}=3(M-M')$ as well.
This proves that $(a,b)$ is unique, given $k,n,p$, under the given conditions.
To actually compute $a$ and $b$, consider $r_3:\Bbb{Z}\rightarrow\{0,1,2\}\,\,$ s.t. $\,\,\,n\,{\rm mod}\,3 = r_3(n) $. Then $$2a+b= \overline{ab} =r_3((-1)^{n}(p-k))$$
In python this is ab = ((-1)**n*(p-k))%3, but you might consider more efficient ways in your programming language, in particular invoking if’s instead of actual exponentiation to compute $(-1)^{n}$, bit shifts, and the like. Beware that the operator % works as expected in python, but there are languages where e.g. -2%3 yields -2 and not 1, so check what you are actually using.
