A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots$

$[]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \: head(l)$ returns the first element of $l$, and $tail(l)$ returns the list obtained by removing the first element from $l. \: \: a:l$ denotes a new list formed by adding a at the head of list $l$.

For example:

$head([0,1,0]) \: =\: 0, tail([0,1,0]) = [1,0]$,

$head([1]) \: = \: 1, tail([1]) = [],$ and

$1:[0,1,0] \: = \: [1,0,1,0]$.

Consider the following functions:

$xor$ takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b) return(0)
else return(1)
endif

$f1$ takes as input a list and returns another list.

f1(s)
if (s == []) then return([1])
else if (head(s) == 0) then return(1:tail(s))
else if (head(s) == 1) then return(0:f1(tail(s)))
endif

$f2$ takes as input a bit and a list and returns a bit.

f2(b,s)

if (s == []) then return(b)

else if (head(s) == 0) then return(f2(xor(b,1),tail(s)))

else if (head(s) == 1) then return(xor(b,1))

endif

$g1$ takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then return([0])
else return f1(g1(n-1))
endif

$g2$ takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then return(0)
else return f2(g2(n-1),g1(n))
endif

- What is the value of $g2(256)$ and $g2(257)$?