Compute the inverse XOR
Pyth, 33 30 - 25 = 5 bytes

Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ


Run it by input from stdin like (online interpreter: https://pyth.herokuapp.com/):

111
3


and the result will be written to stdout. 

This is a direct translation of:

Python 2, 127 118 79 - 25 = 54 bytes

def i(s,k):
 l=int(s,8);t=len(s)+k
 while k&lt;1&lt;&lt;t:l^=l/8;k+=1
 print'%0*o'%(t,l)


Call it like i("111", 3), and the result will be written to stdout.

Note that we expect k not being too large, since for code-golfing purpose the inner loop will run for O(2k) times.



I think we usually call this operation "xorshift" or something. If we express the input as big-endian integers, then the function f is simply:


f(x) = x ⊕ (x ≫ 1)


If we apply f twice we will get:


f2(x) = x ⊕ (x ≫ 2)


However applying 3 times will have a different pattern:


f3(x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)


Applying 4 times get back to the basic form:


f4(x) = x ⊕ (x ≫ 4)


And so on:


f2k(x) = x ⊕ (x ≫ 2k)


Note that if we choose a big-enough 2k, then (x ≫ 2k) = 0, meaning f2k(x) = x, and the inverse is trivially the identity function! 

So the strategy for finding f-k(x) without calling f-1(x) at all is:


Find K such that:


K ≥ k
K > log2 x
K is a power of 2

Express f-k(x) = f-K + (K-k)(x) = f-K(fK-k(x)) = fK-k(x)
Thus, the result is f called K-k times
25 chars profit :p




Update 1: Used octal representation instead of binary so that we could use % formatting to save lots of bytes.

Update 2: Exploit the periodic structure of f. Retired the iterative version since the non-iterative one is shorter even without the -25 bytes bonus.

Update 3: Reduced 3 bytes from Pyth, thanks isaacg!