[Question]
  [
Given an integer \$N>3\$, you have to find the minimum number of bits that need to be inverted in \$N\$ to turn it into a [square number](https://en.wikipedia.org/wiki/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 < N < 10000\$ in less than 1 minute.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged '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]
```
  
[Answer]
## Ruby, 74 bytes
```
->n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size>Math.log2(n)?n:a.count(?1)}.min}
```
[Try it online!](https://tio.run/##FYpdCoJAFIXfXcV9nAm7ODpaFuoKWoFYTP6kkFdJBctx7TYeON8Hh/OZnt@tgmg7xrQwgUgcW9UvetYqYnSfDzPHsXsMzOVXhUPzK@ObGmt8dy@XEU/oojDvJhpZIviKbUPrlkobXNfU2HNsCI3PnthhVuH4vg2BDA1DExuk4wTefj8FQmZYqryGogNN2gKTfhoHqFLKrJKK7Q8)
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](https://codegolf.stackexchange.com/users/26724/piccolo) for saving a byte.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 [bytes](https://github.com/DennisMitchell/jellylanguage/wiki/Code-page)
```
²,BẈEðƇ²^B§Ṃ
```
[Try it online!](https://tio.run/##ASIA3f9qZWxsef//wrIsQuG6iEXDsMaHwrJeQsKn4bmC////ODMx "Jelly – Try It Online")
[Check out a test suite!](https://tio.run/##y0rNyan8///QJh2nh7s6XA9vONZ@aFOc06HlD3c2/T@653D7o6Y17v//R5voGBnpGJnoGBvoWJroWBgbArGRjqGBqamOmYmlqY4lEMQCAA)
Monadic link. Should be golfable. ~~But I am too dumb to think of a way to get rid of the `³`s.~~ It's my first answer in which I successfully use filtering / mapping / looping in general along with a dyadic chain \o/
### Explanation
```
²,BẈEðƇ²^B§Ṃ – Full program / Monadic link. Call the argument N.
     ðƇ      – Filter-keep [1 ... N] with the following dyadic chain:
²,BẈE        – The square of the current item has the same bit length as N.
²            – Square.
 ,           – Pair with N.
  B          – Convert both to binary.
   Ẉ         – Retrieve their lengths.
    E        – And check whether they equate.
       ²^    – After filtering, square the results and XOR them with N.
         B   – Binary representation of each.
          §  – Sum of each. Counts the number of 1s in binary.
           Ṃ – Minimum.
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 20 bytes
```
▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ
```
[Try it online!](https://tio.run/##ATcAyP9odXNr///ilrxtzqNmb8Ks4oaSU@KGkShNb8KkxbziiaDihpThuIvEsOKWoeG4i////zQwMDYz "Husk – Try It Online")
## Explanation
```
▼mΣf(¬→)S↑(M(¤ż≠↔ḋ)İ□ḋ) -- example input n=4
        S↑(           ) -- take n from n applied to (..)
                     ḋ  -- | convert to binary: [1,0,0]
                   İ□   -- | squares: [1,4,9,16,...]
           M(     )     -- | map with argument ([1,0,0]; example with 1)
                 ḋ      -- | | convert to binary: [1]
             ¤  ↔       -- | | reverse both arguments of: [1] [0,0,1]
              ż≠        -- | | | zip with inequality (absolute difference) keeping longer elements: [1,0,1]
                        -- | : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1],[1,0,1,1,1],....
                        -- : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1]]
    f(  )               -- filter elements where
       →                -- | last element
      ¬                 -- | is zero
                        -- : [[0,0,0]]
 mΣ                     -- sum each: [0]
▼                       -- minimum: 0
```
[Answer]
# [Perl 6](http://perl6.org/), 65 bytes
```
{min map {+$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/\./},^2**.msb}
```
[Try it online!](https://tio.run/##DcPdCoMgAAbQV/kWMvoZVqaxYPUkQ7GREORquZsQe3W3A2eb9qWN9sDVoI/ezm9YvcEXRGo6ajelLKOv1Y7pWWeYDdxn/6ZEF5Ko7HKe5ZOW4SZZnlPrxhCdPpAQhX6ANyAqJDDrjgcHY2AcTYWO497U/wx1JQRa3okh/gA "Perl 6 – Try It Online")
I feel a little dirty for testing for a perfect square by looking for a period in the string representation of the number's square root, but...anything to shave off bytes.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~20~~ ~~15~~ 14 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Lnʒ‚b€gË}^b1öß
```
-5 bytes thanks to *@Mr.Xcoder* using a port of [his Jelly answer](https://codegolf.stackexchange.com/a/170373/52210).
[Try it online](https://tio.run/##ASIA3f8wNWFiMWX//0xuypLigJpi4oKsZ8OLfV5iMcO2w5///zk0) or [verify all test cases](https://tio.run/##MzBNTDJM/W9o5OZ5eILLoZX2SgqP2iYpKNn/98k7NenQukcNs5IeNa1JP9xdG5dkeHjb4fn/df6bcBkZcRmZcBkbcFmacFkYGwKxEZehgakpl5mJpSmXJRBwmRgYmBkDAA) (the biggest four test cases are removed, because they'll timeout after 60 sec).
**Explanation:**
```
L          # Create a list in the range [1, (implicit) input-integer]
           #  i.e. input=22 → [0,1,2,...,20,21,22]
 n         # Take the square of each
           #  i.e. [0,1,2,...,20,21,22] → [0,1,4,...,400,441,484]
  ʒ     }  # Filter this list by:
   ,       #  Pair the current value with the (implicit) input-integer
           #   i.e. 0 and 22 → [0,22]
           #   i.e. 25 and 22 → [25,22]
    b      #  Convert both to binary strings
           #   i.e. [0,22] → ['0','10110']
           #   i.e. [25,22] →  ['10000','11001']
     €g    #  Take the length of both
           #   i.e. ['0','10110'] → [1,5]
           #   ['10000','11001'] → [5,5]
       Ë   #  Check if both are equal
           #   i.e. [1,5] → 0 (falsey)
           #   i.e. [5,5] → 1 (truthy)
^          # After we've filtered, Bitwise-XOR each with the (implicit) input-integer
           #  i.e. [16,25] and 22 → [6,15]
 b         # Convert each to a binary string again
           #  i.e. [6,15] → ['110','1111']
  1ö       # Convert each to base-1, which effectively is a vectorized sum of their
           # digits, to get the amount of 1-bits in each binary string
           #  i.e. ['110','1111'] → [2,4]
ß          # Pop and leave the minimum of this list
           #  i.e. [2,4] → 2
           # (which is output implicitly as result)
```
[Answer]
# [Java (JDK 10)](http://jdk.java.net/), 110 bytes
```
n->{int i=1,s=1,b,m=99,h=n.highestOneBit(n);for(;s<h*2;s=++i*i)m=(s^n)<h&&(b=n.bitCount(s^n))<m?b:m;return m;}
```
[Try it online!](https://tio.run/##ZZHfa4MwEMff@1eEQou2VhK1tlbt2AaDPYw9dG9jA62/0mkUcxZK6d/uou02dYEjuc9d7o7vHbyjtzgEXzXNirwEdBC@WgFN1Zk9@seiiu2B5qwJFpWf0j3apx7n6MWjDJ1HCN0oBw/EdcxpgDIRk3ZQUha/fyCvjLncpiL0lj8zeLrVdMQ7jMNyiyK3ZovtmTJA1CUKF@YrmWtZSuIyNaFxEnJ4ZeEDBYnJdpSXks2dZKbZ3J3P6YzKmSvxTyY7yXQq@eKPT@Exrxi0VHayO3@T2WUIVclQZl9qux1HNBQDgijOkXsb8e8YSh9o2hAMM3Q8ANYgY62TIegXJXi57AHTsPrAEqcLDIxNvQM0Y2WSTluCDUsnncFWukm01foHEIyxsTax2fqXqzCNws02Gmk2V4HkX312Jw5hpuYVqIXYMUTSeEJwsEGTYMLGSpuuoEj1iiI93XOxZalBsnytfRk1dqm/AQ "Java (JDK 10) – Try It Online")
[Answer]
# [Gaia](https://github.com/splcurran/Gaia), 18 [bytes](https://github.com/splcurran/Gaia/blob/master/codepage.md)
Near-port of [my Jelly answer](https://codegolf.stackexchange.com/a/170373/59487).
```
s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋
```
[Try it online!](https://tio.run/##S0/MTPz/v/jQskfzV@kkHVqWc2hZ5aP5qx81tgMF4pLOLQZygJI93f//GxqYmgIA "Gaia – Try It Online")
### Breakdown
```
s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋ – Full program. Let's call the input N.
s¦                 – Square each integer in the range [1 ... N].
  ⟪      ⟫⁇        – Select those that fulfil a certain condition, when ran through
                     a dyadic block. Using a dyadic block saves one byte because the
                     input, N, is implicitly used as another argument.
   ,               – Pair the current element and N in a list.
    b¦             – Convert them to binary.
      l¦           – Get their lengths.
        y          – Then check whether they are equal.
           ⟪   ⟫¦  – Run all the valid integers through a dyadic block.
            ^      – XOR each with N.
             bΣ    – Convert to binary and sum (count the 1s in binary)
                 ⌋ – Minimum.
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 67 bytes
```
Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&
```
[Try it online!](https://tio.run/##FYtfC4IwFMXf9ymEgRQs2uZciRijeiyQngIxGOKfkU7Q9RT51df1wu@cw733DNp19aCdqbRvso2/G6uupjXuMn6sK/rsbNyttq3rUrxAfo7TkpvqXczZQ9u2VvjFSa9mAJeEE1aGfpuifDLQxsHuFDRwCPfqiwRBnAPgESUoAT9GbBXYMhrHBEmRgCYwBAlKZbS@HyQT6Of/ "Wolfram Language (Mathematica) – Try It Online")
Takes \$\{1, 2, \ldots, n\}\$ and squares them. Then, the numbers with same `BitLength` as the input are `Pick`ed, and `BitXor`ed with the input. Next, the `Min`imum `DigitCount` of `1`s in binary is returned.
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 56 41 bytes
It's not gonna break any length records but thought i'd post it anyway
```
⟨⟨{⟦^₂ᵐḃᵐ}{h∋Q.l~t?∧}ᶠ{ḃl}⟩zḃᶠ⟩{z{∋≠}ᶜ}ᵐ⌋
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r//9H8FUBU/Wj@srhHTU0Pt054uKMZSNZWZzzq6A7Uy6krsX/Usbz24bYF1UCZnNpH81dWgZRsWwBkVVdVA1U96lwAlJ9TC9T2qKf7/39DAyD4HwUA "Brachylog – Try It Online")
[Answer]
# x86-64 assembly, 37 bytes
Bytecode:
```
53 89 fb 89 f9 0f bd f7 89 c8 f7 e0 70 12 0f bd
d0 39 f2 75 0b 31 f8 f3 0f b8 c0 39 d8 0f 42 d8
e2 e6 93 5b c3
```
Nicely, this computes even the highest example in less than a second.
Heart of the algorithm is xor/popcount as usual.
```
    push %rbx
    /* we use ebx as our global accumulator, to see what the lowest bit
     * difference is */
    /* it needs to be initialized to something big enough, fortunately the
     * answer will always be less than the initial argument */
    mov %edi,%ebx
    mov %edi,%ecx
    bsr %edi,%esi
.L1:
    mov %ecx,%eax
    mul %eax
    jo cont     /* this square doesn't even fit into eax */
    bsr %eax,%edx
    cmp %esi,%edx
    jnz cont    /* can't invert bits higher than esi */
    xor %edi,%eax
    popcnt %eax,%eax
    cmp %ebx,%eax   /* if eax < ebx */
    cmovb %eax,%ebx
cont:
    loop .L1
    xchg %ebx,%eax
    pop %rbx
    retq
```
[Answer]
# PARI/GP 136 bytes
```
t(n)=b=#digits(n\2,2);for(j=0,b,v=concat(vector(b-j),vector(j,i,1));forperm(v,p,if(issquare(bitxor(n,fromdigits(Vec(p),2))),return(j))))
```
## Test
```
T=[4, 22, 24, 30, 94, 831, 832, 1055, 6495, 9999, 40063, 247614, 1049310, 7361278, 100048606];
for (i=1, #T, print(T[i]," | "t(T[i])))
4 | 0
22 | 2
24 | 1
30 | 3
94 | 4
831 | 5
832 | 1
1055 | 4
6495 | 6
9999 | 4
40063 | 6
247614 | 7
1049310 | 7
7361278 | 8
100048606 | 8
> ##
***   last result computed in 736 ms.
Test with OEIS A358701(9):
t(743300286)
9
##
last result computed in 3,813 ms.
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 31 bytes
```
ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨θ²¬⁼λ§ιμ
```
[Try it online!](https://tio.run/##RYxBCsIwFET3niLLH4ibbLtSUSjYUtALxBrshyRtkh/x9rEpEWcxDMObGScVxlmZnFu3JOqTfegAnje7IaAjOKlI0KFDmyx0aoELGlqJEr1gRxU13NHqCCgYcsEkX@3skzIRrtq9aIJS17jxfqMKd6un/1qwfiaoeyPYgVr31J/ybvlPTc5S5v3bfAE "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
Ｎθ                              Input N
       θ                        N
      Ｅ                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              Ｌ Ｌ               Length
             ⁼                  Equals
    Ｅ                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     Ｅ          Map over digits
                           λ    Current base 2 digit of N
                             ι  Current base 2 value
                              μ Inner index
                            §   Get digit of value
                          ⁼     Equals
                         ¬      Not (i.e. XOR)
                    Σ           Take the sum
   ⌊                            Take the minimum
  Ｉ                             Cast to string
                                Implicitly print
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 20 bytes
```
BL’Ø.ṗŻ€©Ḅ^⁸Æ²a§ɼ¹ƇṂ
```
[Try it online!](https://tio.run/##ATgAx/9qZWxsef//QkzigJnDmC7huZfFu@KCrMKp4biEXuKBuMOGwrJhwqfJvMK5xofhuYL///80MDA2Mw "Jelly – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 82 bytes
```
lambda n:min(bin(i*i^n).count('1')for i in range(n)if len(bin(i*i^n))<len(bin(n)))
```
[Try it online!](https://tio.run/##bc7dCoIwFMDx@57iQBe6iDhnm1Oj3iQC@7AGdRSxi55@6UiwrQOD7cefw9p3f29Yunp/cI/qebpUwNun5fQ0HLuyRxabc/PiPk0oEXXTgQXL0FV8u6YsbA2P6zwWu@k93IVrO8s91Cl8RwtYAy4ClnJkGbGvKWSFI6uQS1/rgAtFI2cRyz@7CbPszxKjS8/ml8th4lojGhXVUueG/AfzGRPqUhGGnCtDMi9GLhbLyQkRdWHQeHcf "Python 2 – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt) `-g`, 20 bytes
*This can be golfed down.*
```
op f_¤Ê¥¢lÃ®^U ¤¬xÃn
```
[Try it online!](https://tio.run/##ASsA1P9qYXB0//9vcCBmX8Kkw4rCpcKibMODwq5eVSDCpMKseMODbv//ODMxIC1n "Japt – Try It Online")
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~93~~ 91 bytes
```
g(n){n=n?n%2+g(n/2):0;}m;i;d;f(n){m=99;for(i=0;++i*i<2*n;m=g(d=i*i^n)<m&d<n/2?g(d):m);n=m;}
```
[Try it online!](https://tio.run/##JY/basMwDIbv8xSikGE3DnMcx4nreH2QroUQk8wEq6OM3ZQ8e6Z0AiE@Sb8OYzmP47bNDPkTPZ4xVwXBu@In6dbkogtu2ovJW@um@4NFL11RxGPs1RFd8jMLnuiGvE9voSfpmVL8lLhDn9y6/d5jgC8W8QeQwzMDsu8H4cQOuQ1Qlh@Qh088CEAB@zLusjXLdkEaIjL@r9l5uFzBw1MLpYTSopbCatHVFbkSlWwaYbRthCUTWkpTU1drKk01betKirY2lWo7Yil1Z6RZ3Wv46zNasHgJDpa@aigUxcLp8uGyXPeTtj8 "C (gcc) – Try It Online")
---
Edit: I think my original solution ([Try it online!](https://tio.run/##JU/haoQwDP7vU4QDpT0jq7VWu9rtQW53IBa9IvbGMfZHfHYXb4GQfEm@fMlQTMOw7xOLfI0ufsZU5gTeJH8XdlucMTZYb8ejPz6eLDhh8zycQyfP0U7MO8pvkXdLlvmOeFnGFkd1zrmNbrHb/vsIHu4sxB@IHNYEyL6fBEd2So2HoviA1H/FE0JEOJS4TbYkOQhLHyLj/5wD95crOFgVSolSYSXQKGyrklxiKeoatTI1GjJUQuiKphpdKuopU5UCm0qXsmkJC6FaLfRmX8tfv5HA7ARYmLuyppDnM4fFaYV31l/m63HX/gc)) is not valid, because one of the variables, `m`, global to save a few bytes by not specifying type, was initialized outside of `f(n)` and therefore had to be reinitialized between calls
---
# Ungolfed and commented code :
```
g(n){n=n?n%2+g(n/2):0;} // returns the number of bits equal to 1 in n
m; //miminum hamming distance between n and a square
i; //counter to browse squares
d; //bitwise difference between n and a square
f(n){m=99; //initialize m to 99 > size of int (in bits)
    for(
        i=0;
        ++i*i<2*n; //get the next square number, stop if it's greater than 2*n
        g(d=i*i^n)<m&&d<n/2&&(m=g(d)) //calculate d and hamming distance
//      ^~~~~~~~~~~^ if the hamming distance is less than the minimum
//                    ^~~~^ and the most significant bit of n did not change (the most significant bit contains at least half the value)
//                           ^~~~~~~^ then update m
       );
    n=m;} // output m
```
---
# Edits:
* Saved 2 bytes thanks to ceilingcat
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 79 bytes
```
x=>g=(i=z=x)=>i?g(i-1,t=i*i^x,u=(N=i=>i&&i%2+N(i>>1))(t),z=z<u|t>x&i*i>x?z:u):z
```
[Try it online!](https://tio.run/##JYpBCsIwEADv/sOwq4lYb1Z3@4M@QSi1DaulKSaVEHy7MeAcZ@bRvTvfv2QJZnb3IY@UI7ElEEoUkVgaC2IqHUh2cot6JWhJildKtqd9C8JcIUJAnShd10/gqMrKsUn1inXKl03vZu@m4TA5CyNUxwICYv66JUhp2fjQ9U/jJQ10/vMD "JavaScript (Node.js) – Try It Online")
If `t` and `t^x` are both larger than `x` then `t` is longer than `x`
]