Compute the inverse XOR Let f be the function that maps a bitfield ({0 1}) of size n+1 to bitfield of size n by applying XOR to the ith and i+1th bit and writing the result in the new bitfield.

Example: f("0101") = "111"

Informal calculation:

0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1


Let f_inverse be the inverse function of f. Since the inverse is not unique, f_inverse returns one valid solution.

Input: bitfield as string (i.e. "0101111101011") and a given natural number k

Output: bitfield as string, so that the string contains the result if f_inverse is applied k times to the input bitfield. (i.e. f_inverse(f_inverse(f_inverse(input))) )

Winning criteria: fewest Characters

Bonus: 

-25 Characters if f_inverse is not applied recursively/iteratively, instead the output string is directly calculated

Testscript:

a = "011001"
k = 3

def f(a):
    k = len(a)
    r = ""
    for i in xrange(k-1):
        r += str(int(a[i]) ^ int(a[i+1]))
    return r

def iterate_f(a, k):
    print "Input ", a
    for i in xrange(k):
        a = f(a)
        print "Step " + str(i+1), a

iterate_f(a, k)


You can paste it for example here and then try it.
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!