Toggle some bits and get a square Given an integer \$N&gt;3\$, you have to find the minimum number of bits that need to be inverted in \$N\$ to turn it into a square number. You are only allowed to invert bits below the most significant one.

Examples


\$N=4\$ already is a square number (\$2^2\$), so the expected output is \$0\$.
\$N=24\$ can be turned into a square number by inverting 1 bit: \$11000 \rightarrow 1100\color{red}1\$ (\$25=5^2\$), so the expected output is \$1\$.
\$N=22\$ cannot be turned into a square number by inverting a single bit (the possible results being \$23\$, \$20\$, \$18\$ and \$30\$) but it can be done by inverting 2 bits: \$10110 \rightarrow 10\color{red}0\color{red}00\$ (\$16=4^2\$), so the expected output is \$2\$.


Rules


It is fine if your code is too slow or throws an error for the bigger test-cases, but it should at least support \$3 &lt; N &lt; 10000\$ in less than 1 minute.
This is code-golf!


Test cases

    Input | Output
----------+--------
        4 | 0
       22 | 2
       24 | 1
       30 | 3
       94 | 4
      831 | 5
      832 | 1
     1055 | 4
     6495 | 6
     9999 | 4
    40063 | 6
   247614 | 7        (smallest N for which the answer is 7)
  1049310 | 7        (clear them all!)
  7361278 | 8        (smallest N for which the answer is 8)
100048606 | 8        (a bigger "8")


Or in copy/paste friendly format:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
Ruby, 74 bytes



-&gt;n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size&gt;Math.log2(n)?n:a.count(?1)}.min}


Try it online!

This simply generates the sequence \$\left[1^2, 2^2, \ldots, n^2\right]\$ (which is far more than enough), XORs it with \$n\$, and then takes either the number of 1s in its binary representation if the number of bits is less than or equal to \$\log_2n\$, or \$n\$ otherwise. It then takes the minimum number of bits flipped. Returning \$n\$ instead of the number of bits flipped when the highest bit flipped is greater than \$\log_2n\$ prevents these cases from being chosen as the minimum, as \$n\$ will always be greater than the number of bits it has.

Thanks to Piccolo for saving a byte.