Here's how to do it using closure operations; a similar idea can be used for constructing an NFA.
There are three cases to consider. The first case is words consisting only of ones. In this case, we want to transform $1^n$ to $10^n$. We accomplish this as follows. Let $h\colon \{0,1\} \to \{0,1\}^*$ be the homomorphism defined by $h(0) = 1$ and $h(1) = 0$. We capture this part of $\operatorname{plus}(L)$ by the expression $1h(L \cap 1^*)$.
The second case is words of the form $1x01^n$, which should be transformed to $1x10^n$. Here the construction is a bit more complicated. Let $a\colon \{0,1,0',1'\} \to \{0,1\}^*$ be defined by $a(\sigma) = a(\sigma') = \sigma$ (where $\sigma \in \{0,1\}$). The expression $a^{-1}(L) \cap 1(0+1)^*0'1'^*$ replaces $x01^n$ with $x0'1'^n$. To complete the transformation, define $b\colon \{0,1,0',1'\} \to \{0,1\}^*$ by $b(\sigma) = \sigma$, $b(0') = 1$, and $b(1') = 0'$. The expression $b(a^{-1}(L) \cap 1(0+1)^*0'1'^*)$ handles this part of $\operatorname{plus}(L)$.
The final case is the word $0$ (if it is in $L$), which should be transformed to $1$. This is accomplished by $h(L \cap 0)$.
In total, we obtain
$$
\mathrm{plus}(L) = 1h(L \cap 1^*) \cup b(a^{-1}(L) \cap 1(0+1)^*0'1'^*) \cup h(L \cap 0).
$$
Note that any words in $L$ which are not binary encodings (in other words, the empty string and strings with leading zeroes) are just ignored. This can of course be changed if wanted.
0
is changed into a special symbolX
. So0010011
would become0010X11
. $\endgroup$ – Hendrik Jan Feb 13 '18 at 0:20