Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $x$ by $m$ bits. For example, if $x = 0100110001110000$, then $l = 16$ and $$\begin{array}{l}
R(x,0) = x = {\rm{0100110001110000}},\\
R(x,1) = {\rm{1001100011100000}},\\
R(x,2) = {\rm{0011000111000001}},\\
\ldots \\
R(x,15) = {\rm{0010011000111000}}.
\end{array}$$
Let $A \oplus B$ denote the result of the bitwise “exclusive or” operation for two sequences of $l$ bits. For example, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$
Let $H(x)$ denote the number of non-zero bits in $x$ (i.e. the Hamming weight of $x$).
Assuming that $x$ is an $l$-bit word, let $f(x)$ denote the minimal element (the smallest number) in the tuple $$\begin{array}{l}
(H(x \oplus R(x, 1)),\\
H(x \oplus R(x, 2)),\\
\ldots, \\
H(x \oplus R(x, l – 2)),\\
H(x \oplus R(x, l – 1))).
\end{array}$$
For example, $$\begin{array}{l}
f(10011110100010010011) = 10,\\
f(11111111111111111111111111111111) = 0,\\
f(10000000000000000000000000000000) = 2,\\
f(10011100001111100000011111110000) = 8,\\
f(01000110111111100011100100100101) = 16.
\end{array}$$
Question: assuming that for any even natural number $n \ge 2$ there exists a $2n$-bit word $x$ such that $f(x) = n$ and $H(x) = n$, what can be a time- and space-efficient algorithm which, given an arbitrary (even) $n \ge 2$, allows to find at least one such $x$? For example, if $n = 10$, it is easy to check all $20$-bit words and find (in the lexicographic order) $$\begin{array}{l}
x_0 = 00000101011011001111,\\
x_1 = 00000101011110011011,\\
x_2 = 00000101101110011101,\\
x_3 = 00000101110011101101,\\
\ldots,\\
x_{718} = 11111010100001100100,\\
x_{719} = 11111010100100110000.
\end{array}$$
But as the value of $n$ grows, it becomes infeasible to check the huge amount of elements, even if one skips any element $x$ such that $H(x) \neq n$. For example, how can one find a $256$-bit word $x$ such that $f(x) = H(x) = 128$?
Let $S_n (n = 2, 4, 6, \ldots)$ denote cardinality of the set of solutions for the corresponding $n$. Note that each solution $x$ is an element of the family of solutions, and this family contains exactly $2n$ elements, namely, $x$ and $(2n-1)$ its rotations. So we can pick a single (e.g. lexicographically first) element of a family and call it a canonical solution (all other elements of the corresponding family can be generated from this solution in a trivial way). Then let $C_n (n = 2, 4, 6, \ldots)$ denote cardinality of the set of canonical solutions for the corresponding $n$. If my computations are correct, we have
$$\begin{array}{l}
S_2 = 4 = 2^2,\\
C_2 = 1 = 2^0,\\
S_4 = 48 = 2^5 + 2^4,\\
C_4 = 6 = 2^2 + 2^1,\\
S_6 = 144 = 2^7 + 2^4,\\
C_6 = 12 = 2^3 + 2^2,\\
S_8 = 768 = 2^9 + 2^8,\\
C_8 = 48 = 2^5 + 2^4,\\
S_{10} = 720 = 2^9 + 2^7 + 2^6 + 2^4,\\
C_{10} = 36 = 2^5 + 2^2,\\
S_{12} = 5376 = 2^{12} + 2^{10} + 2^8,\\
C_{12} = 224 = 2^7 + 2^6 + 2^5,\\
S_{14} = 3360 = 2^{11} + 2^{10} + 2^8 + 2^5,\\
C_{14} = 120 = 2^6 + 2^5 + 2^4 + 2^3,\\
S_{16} = 4096 = 2^{12},\\
C_{16} = 128 = 2^7.
\end{array}$$
Interestingly, six of the first eight elements of the tuple $(C_2, C_4, \ldots)$ are highly composite numbers: $1, 6, 12, 48, 36, 120$. I cannot explain the fact that $S_{16}$ and $C_{16}$ are powers of two, but it does not look like a random coincidence.
Best Answer
The function $f(x)$ is closely related to the notion of autocorrelation, which for a binary sequence $x$ of length $|x|=N$ and shift $w$ can be expressed as $$\textbf{AC}_x(w) := N - 2H(x\oplus R(x,w)).$$ The values of $\textbf{AC}_x(w)$ for various non-trivial shifts (i.e. $1\leq w\leq N-1$) are called out-of-phase autocorrelation values.
So, $$f(x) = \min_{1\leq w\leq N-1} H(x\oplus R(x,w)) = \frac{N}2 - \frac12\max_{1\leq w\leq N-1} \textbf{AC}_x(w).$$
For the known constructions for optimal binary sequence w.r.t. autocorrelation, I refer to the paper Cai and Ding (2009).
In particular, for $N=q-1\equiv 0\pmod{4}$, where $q$ is a power of prime, the Sidelnikov–Lempel–Cohn–Eastman construction produces a sequence $x$ with $H(x)=\frac{N}2$ and out-of-phase autocorrelation values $\{0,-4\}$, thus giving $f(x)=\frac{N}2$ as requested in the question. The value $N=256$ well fits into this construction since $q=257$ is prime. Here is one such 256-bit word: