By Tennenbaum's theorem, there exists no computable non-standard model of $\mathsf{PA}$. That is, for any nonstandard model $M$, we cannot define an encoding of the integers $x\in M$ such that $+_M$, $\times_M$, $<_M$ are computable functions on this encoding.
However, this isn't necessarily an issue for subsets of non-standard models: in fact, for certain sets of operations $\mathcal O$, we can find a subset $M_{\mathcal O}$ such that
- $\mathbb N\subset M_{\mathcal O}$, i.e., $M_{\mathcal O}$ contains all standard integers and some non-standard integers in $M$;
- $M_{\mathcal O}$ is closed under $\mathcal O$;
- the integers $x\in M_{\mathcal O}$ can be encoded such that the operations in $\mathcal O$ are computable, and further, the integers $x\in\mathbb N$ can be computably decoded to their standard values.
For a simple example, take $\mathcal O=\{+,-,\times,\lfloor\div\rfloor,\operatorname{mod},<\}$. First, we take some non-standard integer $\xi\in M\setminus\mathbb N$, and set $\omega=\xi!$, so that $\omega\equiv0\pmod k$ for all $k\in\mathbb N^+$. Then, our $M_{\mathcal O}$ is the set of integers $x=a_0+\frac{a_1}{b_1}\omega+\frac{a_2}{b_2}\omega^2+\dots+\frac{a_n}{b_n}\omega^n$, where $n\in\mathbb N,a_i\in\mathbb Z,b_i\in\mathbb N^+,$ and $a_n>0$ (except for $x=0$, which has $a_0=0$). Addition, multiplication, and comparison are trivial. To compute $\lfloor\frac xy\rfloor$, we perform polynomial long division, then round down any fractional $a_0$; from there, we can take $x\bmod y=x-y\lfloor\frac xy\rfloor$. Thus, all operations on our $M_{\mathcal O}$ are computable, and any standard value can be decoded.
It turns out that we can extend $\mathcal O$ somewhat further. Let $d_b(x,y)$ denote the digit at $b^y$ in the base-$b$ expansion of $x$. Then, there is seemingly a construction which lets us add $\{d_2(x,y),\lfloor\log_2(x)\rfloor,2^x\}$ to $\mathcal O$, alongside the usual bitwise operators $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR},\operatorname{popcount},\dots\}$. Here, let $b\uparrow\uparrow x$ denote tetration, as in $b\uparrow\uparrow0=1,b\uparrow\uparrow(x+1)=b^{b\uparrow\uparrow x}$. Then, take some $\xi\in M\setminus\mathbb N$ as before, and set $\omega=2\uparrow\uparrow\xi$. For our encoding, we first define a descending sequence $\omega_0=\omega,\omega_{k+1}=\log_2(\omega_k)$. Then, we start with base values $x=0$ and $x=\omega_k$ for $k\in\mathbb N$, and recursively construct new values $$x=\frac{a_1\cdot2^{p_1}+a_2\cdot2^{p_2}+\cdots+a_n\cdot2^{p_n}}{b_1\cdot2^{q_1}+b_2\cdot2^{q_2}+\cdots+b_m\cdot2^{q_m}},$$ where $a_i,b_i\in\mathbb Z,a_n>0,b_m>0,$ the exponents $p_i,q_i\in M_{\mathcal O}$ were constructed in an earlier step, and the two values are divisible.
I haven't fully explored the full range of possibilities with non-standard divisors (e.g., I'm not sure exactly how to check divisibility). But if we restrict ourselves only to standard divisors, we find that the bits of $x$ are grouped into a finite number of "segments", each with an initial part and a periodic part that runs to the next segment. For instance, $(\omega-1)^2/15$ has a binary expansion of $$\overbrace{1000\,1000\cdots1000\,1000}^{\omega_1-4\text{ bits}}\,\overbrace{0111\,0111\cdots0111\,0111}^{\omega_1\text{ bits}}\,1_2.$$ With judicious use of Euler's theorem, this simple structure allows us to determine $d_2(x,y)$ for any $y$, as well as the other bitwise operators. In the general case with non-standard divisors (which can include numbers like $(\omega^\omega-1)/(\omega-1)$ with infinitely many segments), I expect the binary expansion to follow a finite hierarchy of nested cycles, all of which can be evaluated modulo any standard integer. [Though I would appreciate it if someone could point out any big issues in this rough sketch of a construction!]
By themselves, these encodings are simply weird algebraic structures with a number of additional operations defined on them. But since they represent subsets of a non-standard model of $\mathsf{PA}$, we know that any standard result from the operations will be indistinguishable from the same operations on $\mathbb N$, if you were to set $\omega=N!$ or $\omega=2\uparrow\uparrow N$ for $N$ sufficiently large. So I'm interested in whether there is any existing literature on sets like these $M_{\mathcal O}$s.
Also, I'm particularly wondering how many operations can we fit into $\mathcal O$ without running into computability issues. E.g., could we support $d_b(x,y)$ for $b=2,3,5$ simultaneously? Could we support it for every standard $b$? Clearly, we can't support every operation computable on $\mathbb N$, since that includes things like "Does this Turing machine halt before time $t$?", but we can still capture a surprising amount of elementary integer arithmetic.
