Toggle some bits and get a square

Clash Royale CLAN TAG#URR8PPP

up vote
25
down vote

favorite

1

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. 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 1100colorred1$ ($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 10colorred0colorred00$ ($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!

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]

code-golf integer bitwise

share|improve this question

edited Aug 9 at 19:23

qwr

5,49552456

asked Aug 8 at 21:36

Arnauld

63.2k580266

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
  – Magic Octopus Urn
  Aug 9 at 17:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
  – Arnauld
  Aug 9 at 17:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This would be a nice fastest-code question as well (without the input size restriction)
  – qwr
  Aug 9 at 19:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
  – Arnauld
  Aug 9 at 19:27
  

  
  
  
  

add a comment | 

up vote
25
down vote

favorite

1

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. 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 1100colorred1$ ($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 10colorred0colorred00$ ($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!

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]

code-golf integer bitwise

share|improve this question

edited Aug 9 at 19:23

qwr

5,49552456

asked Aug 8 at 21:36

Arnauld

63.2k580266

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
  – Magic Octopus Urn
  Aug 9 at 17:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
  – Arnauld
  Aug 9 at 17:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This would be a nice fastest-code question as well (without the input size restriction)
  – qwr
  Aug 9 at 19:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
  – Arnauld
  Aug 9 at 19:27
  

  
  
  
  

add a comment | 

up vote
25
down vote

favorite

1

up vote
25
down vote

favorite

1

1

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. 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 1100colorred1$ ($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 10colorred0colorred00$ ($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!

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]

code-golf integer bitwise

share|improve this question

edited Aug 9 at 19:23

qwr

5,49552456

asked Aug 8 at 21:36

Arnauld

63.2k580266

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. 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 1100colorred1$ ($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 10colorred0colorred00$ ($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!

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]

code-golf integer bitwise

share|improve this question

edited Aug 9 at 19:23

qwr

5,49552456

asked Aug 8 at 21:36

Arnauld

63.2k580266

share|improve this question

share|improve this question

edited Aug 9 at 19:23

qwr

5,49552456

edited Aug 9 at 19:23

qwr

5,49552456

edited Aug 9 at 19:23

qwr

5,49552456

5,49552456

asked Aug 8 at 21:36

Arnauld

63.2k580266

asked Aug 8 at 21:36

Arnauld

63.2k580266

asked Aug 8 at 21:36

Arnauld

63.2k580266

63.2k580266

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
  – Magic Octopus Urn
  Aug 9 at 17:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
  – Arnauld
  Aug 9 at 17:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This would be a nice fastest-code question as well (without the input size restriction)
  – qwr
  Aug 9 at 19:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
  – Arnauld
  Aug 9 at 19:27
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
  – Magic Octopus Urn
  Aug 9 at 17:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
  – Arnauld
  Aug 9 at 17:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This would be a nice fastest-code question as well (without the input size restriction)
  – qwr
  Aug 9 at 19:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
  – Arnauld
  Aug 9 at 19:27
  

  
  
  
  

Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
– Magic Octopus Urn
Aug 9 at 17:04

Almost half of the answers don't execute for 100048606 on TIO, is that a problem?
– Magic Octopus Urn
Aug 9 at 17:04

@MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
– Arnauld
Aug 9 at 17:10

@MagicOctopusUrn Thanks, I've updated the rules to make it more clear that supporting $Nge 10000$ is optional.
– Arnauld
Aug 9 at 17:10

1

1

This would be a nice fastest-code question as well (without the input size restriction)
– qwr
Aug 9 at 19:20

This would be a nice fastest-code question as well (without the input size restriction)
– qwr
Aug 9 at 19:20

@qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
– Arnauld
Aug 9 at 19:27

@qwr Yes, probably. Or if you want to go hardcore: given $k$, find the smallest $N$ such that $f(N) = k$.
– Arnauld
Aug 9 at 19:27

add a comment | 

15 Answers
15

active

oldest

votes

up vote
14
down vote

Ruby, 74 bytes

->n(1..n).mapx.min

Try it online!

This simply generates the sequence $left[1^2, 2^2, ldots, n^2right]$ (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.

share|improve this answer

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
  – Piccolo
  Aug 9 at 22:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Piccolo Can't believe I missed that, thanks!
  – Doorknob♦
  Aug 9 at 22:34
  

  
  
  
  

add a comment | 

up vote
6
down vote

Jelly, 12 bytes

²,BẈEðƇ²^B§Ṃ

Try it online!

Check out a test suite!

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.

share|improve this answer

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

add a comment | 

up vote
5
down vote

Husk, 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

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

share|improve this answer

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

• 
  
  
  

  
  

  
  
  
  
  
  

  
  ▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
  – Mr. Xcoder
  Aug 8 at 23:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
  – BWO
  Aug 8 at 23:12
  

  
  
  
  

add a comment | 

up vote
5
down vote

Perl 6, 65 bytes

min map +$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/./,^2**.msb

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.

share|improve this answer

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

add a comment | 

up vote
4
down vote

05AB1E, 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

L # Create a list in the range [1, input]
 # i.e. 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 input
 # 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 input
 # i.e. [16,25] and 22 → [6,15]
 b # Convert each to a binary string again
 # i.e. [6,15] → ['110','1111']
 €S # Change the binary strings to a list of digits
 # i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
 O # Take the sum of each
 # i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß # And then take the lowest value in the list
 # i.e. [2,4] → 2

share|improve this answer

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
  – Mr. Xcoder
  Aug 9 at 18:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
  – Kevin Cruijssen
  Aug 9 at 19:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
  – Mr. Xcoder
  Aug 9 at 19:38
  
  

  
  
  
  

add a comment | 

up vote
3
down vote

Java (JDK 10), 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!

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You can save 1 byte by using bitwise and & instead of logical and &&
  – kirbyquerby
  Aug 9 at 21:20
  

  
  
  
  

add a comment | 

up vote
3
down vote

Gaia, 18 bytes

Near-port of my Jelly answer.

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

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.

share|improve this answer

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

add a comment | 

up vote
2
down vote

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!

share|improve this answer

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just realized zipping is a thing. I'll shorten it after i come back from diner
  – Kroppeb
  Aug 9 at 15:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
  – Kroppeb
  Aug 9 at 20:36
  

  
  
  
  

add a comment | 

up vote
2
down vote

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

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest replacing at least one of your movs with an xchg
  – ceilingcat
  Aug 31 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
  – ObsequiousNewt
  2 days ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

Wolfram Language (Mathematica), 67 bytes

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Try it online!

Takes $1, 2, ldots, n$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

share|improve this answer

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

add a comment | 

up vote
1
down vote

Charcoal, 31 bytes

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

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

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

add a comment | 

up vote
1
down vote

Jelly, 20 bytes

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Try it online!

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

add a comment | 

up vote
1
down vote

Python 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!

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

add a comment | 

up vote
1
down vote

Japt -g, 20 bytes

This can be golfed down.

op f_¤Ê¥¢lî^U ¤¬xÃn

Try it online!

share|improve this answer

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

add a comment | 

up vote
1
down vote

C (gcc), 93 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));n=m;

Try it online!

---

Edit: I think my original solution (Try it online!) 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

share|improve this answer

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170281%2ftoggle-some-bits-and-get-a-square%23new-answer', 'question_page');

);

Post as a guest

Name Email

15 Answers
15

active

oldest

votes

15 Answers
15

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
14
down vote

Ruby, 74 bytes

->n(1..n).mapx.min

Try it online!

This simply generates the sequence $left[1^2, 2^2, ldots, n^2right]$ (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.

share|improve this answer

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
  – Piccolo
  Aug 9 at 22:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Piccolo Can't believe I missed that, thanks!
  – Doorknob♦
  Aug 9 at 22:34
  

  
  
  
  

add a comment | 

up vote
14
down vote

Ruby, 74 bytes

->n(1..n).mapx.min

Try it online!

This simply generates the sequence $left[1^2, 2^2, ldots, n^2right]$ (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.

share|improve this answer

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
  – Piccolo
  Aug 9 at 22:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Piccolo Can't believe I missed that, thanks!
  – Doorknob♦
  Aug 9 at 22:34
  

  
  
  
  

add a comment | 

up vote
14
down vote

up vote
14
down vote

Ruby, 74 bytes

->n(1..n).mapx.min

Try it online!

This simply generates the sequence $left[1^2, 2^2, ldots, n^2right]$ (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.

share|improve this answer

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

Ruby, 74 bytes

->n(1..n).mapx.min

Try it online!

This simply generates the sequence $left[1^2, 2^2, ldots, n^2right]$ (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.

share|improve this answer

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

share|improve this answer

share|improve this answer

edited Aug 9 at 22:34

edited Aug 9 at 22:34

edited Aug 9 at 22:34

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

answered Aug 8 at 22:16

Doorknob♦

52.9k15110338

52.9k15110338

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
  – Piccolo
  Aug 9 at 22:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Piccolo Can't believe I missed that, thanks!
  – Doorknob♦
  Aug 9 at 22:34
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
  – Piccolo
  Aug 9 at 22:24
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Piccolo Can't believe I missed that, thanks!
  – Doorknob♦
  Aug 9 at 22:34
  

  
  
  
  

You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
– Piccolo
Aug 9 at 22:24

You can save a byte by using (n^x*x).to_s 2;... instead of (n^x*x).to_s(2);...
– Piccolo
Aug 9 at 22:24

@Piccolo Can't believe I missed that, thanks!
– Doorknob♦
Aug 9 at 22:34

@Piccolo Can't believe I missed that, thanks!
– Doorknob♦
Aug 9 at 22:34

add a comment | 

up vote
6
down vote

Jelly, 12 bytes

²,BẈEðƇ²^B§Ṃ

Try it online!

Check out a test suite!

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.

share|improve this answer

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

add a comment | 

up vote
6
down vote

Jelly, 12 bytes

²,BẈEðƇ²^B§Ṃ

Try it online!

Check out a test suite!

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.

share|improve this answer

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

add a comment | 

up vote
6
down vote

up vote
6
down vote

Jelly, 12 bytes

²,BẈEðƇ²^B§Ṃ

Try it online!

Check out a test suite!

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.

share|improve this answer

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

Jelly, 12 bytes

²,BẈEðƇ²^B§Ṃ

Try it online!

Check out a test suite!

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.

share|improve this answer

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

share|improve this answer

share|improve this answer

edited Aug 15 at 21:30

edited Aug 15 at 21:30

edited Aug 15 at 21:30

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

answered Aug 9 at 19:00

Mr. Xcoder

30k756193

30k756193

add a comment | 

add a comment | 

up vote
5
down vote

Husk, 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

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

share|improve this answer

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

• 
  
  
  

  
  

  
  
  
  
  
  

  
  ▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
  – Mr. Xcoder
  Aug 8 at 23:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
  – BWO
  Aug 8 at 23:12
  

  
  
  
  

add a comment | 

up vote
5
down vote

Husk, 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

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

share|improve this answer

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

• 
  
  
  

  
  

  
  
  
  
  
  

  
  ▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
  – Mr. Xcoder
  Aug 8 at 23:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
  – BWO
  Aug 8 at 23:12
  

  
  
  
  

add a comment | 

up vote
5
down vote

up vote
5
down vote

Husk, 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

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

share|improve this answer

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

Husk, 20 bytes

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

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

share|improve this answer

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

share|improve this answer

share|improve this answer

edited Aug 8 at 23:11

edited Aug 8 at 23:11

edited Aug 8 at 23:11

answered Aug 8 at 22:30

BWO

9,27011569

answered Aug 8 at 22:30

BWO

9,27011569

answered Aug 8 at 22:30

BWO

9,27011569

9,27011569

• 
  
  
  

  
  

  
  
  
  
  
  

  
  ▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
  – Mr. Xcoder
  Aug 8 at 23:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
  – BWO
  Aug 8 at 23:12
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  ▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
  – Mr. Xcoder
  Aug 8 at 23:09
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
  – BWO
  Aug 8 at 23:12
  

  
  
  
  

▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
– Mr. Xcoder
Aug 8 at 23:09

▼mΣfo¬â†á¹ Mz≠ȯfo£Ä°â–¡á¸‹Ï€Å€2Lḋ saves 2 bytes. RIP you perfect square score.
– Mr. Xcoder
Aug 8 at 23:09

@Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
– BWO
Aug 8 at 23:12

@Mr.Xcoder: Shame about the score.. But I got rid of some more, now targetting 16 ;P
– BWO
Aug 8 at 23:12

add a comment | 

up vote
5
down vote

Perl 6, 65 bytes

min map +$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/./,^2**.msb

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.

share|improve this answer

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

add a comment | 

up vote
5
down vote

Perl 6, 65 bytes

min map +$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/./,^2**.msb

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.

share|improve this answer

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

add a comment | 

up vote
5
down vote

up vote
5
down vote

Perl 6, 65 bytes

min map +$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/./,^2**.msb

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.

share|improve this answer

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

Perl 6, 65 bytes

min map +$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/./,^2**.msb

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.

share|improve this answer

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

share|improve this answer

share|improve this answer

edited Aug 8 at 23:29

edited Aug 8 at 23:29

edited Aug 8 at 23:29

answered Aug 8 at 23:15

Sean

2,86636

answered Aug 8 at 23:15

Sean

2,86636

answered Aug 8 at 23:15

Sean

2,86636

2,86636

add a comment | 

add a comment | 

up vote
4
down vote

05AB1E, 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

L # Create a list in the range [1, input]
 # i.e. 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 input
 # 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 input
 # i.e. [16,25] and 22 → [6,15]
 b # Convert each to a binary string again
 # i.e. [6,15] → ['110','1111']
 €S # Change the binary strings to a list of digits
 # i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
 O # Take the sum of each
 # i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß # And then take the lowest value in the list
 # i.e. [2,4] → 2

share|improve this answer

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
  – Mr. Xcoder
  Aug 9 at 18:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
  – Kevin Cruijssen
  Aug 9 at 19:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
  – Mr. Xcoder
  Aug 9 at 19:38
  
  

  
  
  
  

add a comment | 

up vote
4
down vote

05AB1E, 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

L # Create a list in the range [1, input]
 # i.e. 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 input
 # 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 input
 # i.e. [16,25] and 22 → [6,15]
 b # Convert each to a binary string again
 # i.e. [6,15] → ['110','1111']
 €S # Change the binary strings to a list of digits
 # i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
 O # Take the sum of each
 # i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß # And then take the lowest value in the list
 # i.e. [2,4] → 2

share|improve this answer

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
  – Mr. Xcoder
  Aug 9 at 18:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
  – Kevin Cruijssen
  Aug 9 at 19:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
  – Mr. Xcoder
  Aug 9 at 19:38
  
  

  
  
  
  

add a comment | 

up vote
4
down vote

up vote
4
down vote

05AB1E, 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

L # Create a list in the range [1, input]
 # i.e. 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 input
 # 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 input
 # i.e. [16,25] and 22 → [6,15]
 b # Convert each to a binary string again
 # i.e. [6,15] → ['110','1111']
 €S # Change the binary strings to a list of digits
 # i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
 O # Take the sum of each
 # i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß # And then take the lowest value in the list
 # i.e. [2,4] → 2

share|improve this answer

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

05AB1E, 20 15 bytes

Lnʒ‚b€gË}^b€SOß

-5 bytes thanks to @Mr.Xcoder using a port of his Jelly answer.

Try it online or verify all test cases (biggest three test cases are removed because they time out after 60 sec; still takes about 35-45 sec with the other test cases).

Explanation:

L # Create a list in the range [1, input]
 # i.e. 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 input
 # 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 input
 # i.e. [16,25] and 22 → [6,15]
 b # Convert each to a binary string again
 # i.e. [6,15] → ['110','1111']
 €S # Change the binary strings to a list of digits
 # i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
 O # Take the sum of each
 # i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß # And then take the lowest value in the list
 # i.e. [2,4] → 2

share|improve this answer

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

share|improve this answer

share|improve this answer

edited Aug 9 at 19:12

edited Aug 9 at 19:12

edited Aug 9 at 19:12

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

answered Aug 9 at 7:52

Kevin Cruijssen

29.3k547162

29.3k547162

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
  – Mr. Xcoder
  Aug 9 at 18:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
  – Kevin Cruijssen
  Aug 9 at 19:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
  – Mr. Xcoder
  Aug 9 at 19:38
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
  – Mr. Xcoder
  Aug 9 at 18:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
  – Kevin Cruijssen
  Aug 9 at 19:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
  – Mr. Xcoder
  Aug 9 at 19:38
  
  

  
  
  
  

1

1

Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
– Mr. Xcoder
Aug 9 at 18:31

Okay then, a valid 15-byter: Lnʒ‚b€gË}^b€SOß. It breaks your test suite unfortunately, though
– Mr. Xcoder
Aug 9 at 18:31

1

1

@Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
– Kevin Cruijssen
Aug 9 at 19:12

@Mr.Xcoder Thanks! And my test suite almost always breaks after I golf something.. XD But it's fixed now as well.
– Kevin Cruijssen
Aug 9 at 19:12

I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
– Mr. Xcoder
Aug 9 at 19:38

I guess I'm not good at writing test suites in 05AB1E ¯_(ツ)_/¯, it's nice that you have fixed it :)
– Mr. Xcoder
Aug 9 at 19:38

add a comment | 

up vote
3
down vote

Java (JDK 10), 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!

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You can save 1 byte by using bitwise and & instead of logical and &&
  – kirbyquerby
  Aug 9 at 21:20
  

  
  
  
  

add a comment | 

up vote
3
down vote

Java (JDK 10), 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!

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You can save 1 byte by using bitwise and & instead of logical and &&
  – kirbyquerby
  Aug 9 at 21:20
  

  
  
  
  

add a comment | 

up vote
3
down vote

up vote
3
down vote

Java (JDK 10), 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!

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

Java (JDK 10), 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!

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

share|improve this answer

share|improve this answer

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

answered Aug 9 at 9:19

Olivier Grégoire

7,48311739

7,48311739

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You can save 1 byte by using bitwise and & instead of logical and &&
  – kirbyquerby
  Aug 9 at 21:20
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  You can save 1 byte by using bitwise and & instead of logical and &&
  – kirbyquerby
  Aug 9 at 21:20
  

  
  
  
  

1

1

You can save 1 byte by using bitwise and & instead of logical and &&
– kirbyquerby
Aug 9 at 21:20

You can save 1 byte by using bitwise and & instead of logical and &&
– kirbyquerby
Aug 9 at 21:20

add a comment | 

up vote
3
down vote

Gaia, 18 bytes

Near-port of my Jelly answer.

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

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.

share|improve this answer

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

add a comment | 

up vote
3
down vote

Gaia, 18 bytes

Near-port of my Jelly answer.

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

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.

share|improve this answer

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

add a comment | 

up vote
3
down vote

up vote
3
down vote

Gaia, 18 bytes

Near-port of my Jelly answer.

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

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.

share|improve this answer

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

Gaia, 18 bytes

Near-port of my Jelly answer.

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

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.

share|improve this answer

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

share|improve this answer

share|improve this answer

edited Aug 10 at 13:31

edited Aug 10 at 13:31

edited Aug 10 at 13:31

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

answered Aug 10 at 7:51

Mr. Xcoder

30k756193

30k756193

add a comment | 

add a comment | 

up vote
2
down vote

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!

share|improve this answer

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just realized zipping is a thing. I'll shorten it after i come back from diner
  – Kroppeb
  Aug 9 at 15:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
  – Kroppeb
  Aug 9 at 20:36
  

  
  
  
  

add a comment | 

up vote
2
down vote

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!

share|improve this answer

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just realized zipping is a thing. I'll shorten it after i come back from diner
  – Kroppeb
  Aug 9 at 15:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
  – Kroppeb
  Aug 9 at 20:36
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

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!

share|improve this answer

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

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!

share|improve this answer

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

share|improve this answer

share|improve this answer

edited Aug 9 at 20:34

edited Aug 9 at 20:34

edited Aug 9 at 20:34

answered Aug 9 at 15:28

Kroppeb

82628

answered Aug 9 at 15:28

Kroppeb

82628

answered Aug 9 at 15:28

Kroppeb

82628

82628

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just realized zipping is a thing. I'll shorten it after i come back from diner
  – Kroppeb
  Aug 9 at 15:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
  – Kroppeb
  Aug 9 at 20:36
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just realized zipping is a thing. I'll shorten it after i come back from diner
  – Kroppeb
  Aug 9 at 15:31
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
  – Kroppeb
  Aug 9 at 20:36
  

  
  
  
  

Just realized zipping is a thing. I'll shorten it after i come back from diner
– Kroppeb
Aug 9 at 15:31

Just realized zipping is a thing. I'll shorten it after i come back from diner
– Kroppeb
Aug 9 at 15:31

1

1

@Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
– Kroppeb
Aug 9 at 20:36

@Arnauld Yeah, the main problem was that for each i in range(0,n+1) i recalculated the range, squared it and to binary. Putting this outside recuired a few more bytes but it's way faster now
– Kroppeb
Aug 9 at 20:36

add a comment | 

up vote
2
down vote

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

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest replacing at least one of your movs with an xchg
  – ceilingcat
  Aug 31 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
  – ObsequiousNewt
  2 days ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

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

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest replacing at least one of your movs with an xchg
  – ceilingcat
  Aug 31 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
  – ObsequiousNewt
  2 days ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

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

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

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

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

share|improve this answer

share|improve this answer

answered Aug 10 at 0:04

ObsequiousNewt

76635

answered Aug 10 at 0:04

ObsequiousNewt

76635

answered Aug 10 at 0:04

ObsequiousNewt

76635

76635

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest replacing at least one of your movs with an xchg
  – ceilingcat
  Aug 31 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
  – ObsequiousNewt
  2 days ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest replacing at least one of your movs with an xchg
  – ceilingcat
  Aug 31 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
  – ObsequiousNewt
  2 days ago
  

  
  
  
  

Suggest replacing at least one of your movs with an xchg
– ceilingcat
Aug 31 at 23:55

Suggest replacing at least one of your movs with an xchg
– ceilingcat
Aug 31 at 23:55

As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
– ObsequiousNewt
2 days ago

As far as I can tell there's only one that would save a byte (mov %ecx,%eax) and I can't let %ecx die there.
– ObsequiousNewt
2 days ago

add a comment | 

up vote
1
down vote

Wolfram Language (Mathematica), 67 bytes

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Try it online!

Takes $1, 2, ldots, n$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

share|improve this answer

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

add a comment | 

up vote
1
down vote

Wolfram Language (Mathematica), 67 bytes

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Try it online!

Takes $1, 2, ldots, n$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

share|improve this answer

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

add a comment | 

up vote
1
down vote

up vote
1
down vote

Wolfram Language (Mathematica), 67 bytes

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Try it online!

Takes $1, 2, ldots, n$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

share|improve this answer

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

Wolfram Language (Mathematica), 67 bytes

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Try it online!

Takes $1, 2, ldots, n$ and squares them. Then, the numbers with same BitLength as the input are Picked, and BitXored with the input. Next, the Minimum DigitCount of 1s in binary is returned.

share|improve this answer

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

share|improve this answer

share|improve this answer

edited Aug 8 at 22:36

edited Aug 8 at 22:36

edited Aug 8 at 22:36

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

answered Aug 8 at 22:29

JungHwan Min

12.4k31465

12.4k31465

add a comment | 

add a comment | 

up vote
1
down vote

Charcoal, 31 bytes

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

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

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

add a comment | 

up vote
1
down vote

Charcoal, 31 bytes

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

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

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

add a comment | 

up vote
1
down vote

up vote
1
down vote

Charcoal, 31 bytes

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

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

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

Charcoal, 31 bytes

ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨責⁼λ§ιμ

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

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

share|improve this answer

share|improve this answer

answered Aug 8 at 23:21

Neil

74.9k744169

answered Aug 8 at 23:21

Neil

74.9k744169

answered Aug 8 at 23:21

Neil

74.9k744169

74.9k744169

add a comment | 

add a comment | 

up vote
1
down vote

Jelly, 20 bytes

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Try it online!

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

add a comment | 

up vote
1
down vote

Jelly, 20 bytes

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Try it online!

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

add a comment | 

up vote
1
down vote

up vote
1
down vote

Jelly, 20 bytes

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Try it online!

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

Jelly, 20 bytes

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Try it online!

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

share|improve this answer

share|improve this answer

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

answered Aug 9 at 0:03

Erik the Outgolfer

29.4k42698

29.4k42698

add a comment | 

add a comment | 

up vote
1
down vote

Python 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!

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

add a comment | 

up vote
1
down vote

Python 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!

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

add a comment | 

up vote
1
down vote

up vote
1
down vote

Python 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!

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

Python 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!

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

share|improve this answer

share|improve this answer

answered Aug 9 at 11:54

TFeld

11.2k2833

answered Aug 9 at 11:54

TFeld

11.2k2833

answered Aug 9 at 11:54

TFeld

11.2k2833

11.2k2833

add a comment | 

add a comment | 

up vote
1
down vote

Japt -g, 20 bytes

This can be golfed down.

op f_¤Ê¥¢lî^U ¤¬xÃn

Try it online!

share|improve this answer

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

add a comment | 

up vote
1
down vote

Japt -g, 20 bytes

This can be golfed down.

op f_¤Ê¥¢lî^U ¤¬xÃn

Try it online!

share|improve this answer

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

add a comment | 

up vote
1
down vote

up vote
1
down vote

Japt -g, 20 bytes

This can be golfed down.

op f_¤Ê¥¢lî^U ¤¬xÃn

Try it online!

share|improve this answer

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

Japt -g, 20 bytes

This can be golfed down.

op f_¤Ê¥¢lî^U ¤¬xÃn

Try it online!

share|improve this answer

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

share|improve this answer

share|improve this answer

edited Aug 9 at 19:27

edited Aug 9 at 19:27

edited Aug 9 at 19:27

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

answered Aug 9 at 19:20

Luis felipe De jesus Munoz

2,9211044

2,9211044

add a comment | 

add a comment | 

up vote
1
down vote

C (gcc), 93 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));n=m;

Try it online!

---

Edit: I think my original solution (Try it online!) 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

share|improve this answer

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

add a comment | 

up vote
1
down vote

C (gcc), 93 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));n=m;

Try it online!

---

Edit: I think my original solution (Try it online!) 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

share|improve this answer

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

add a comment | 

up vote
1
down vote

up vote
1
down vote

C (gcc), 93 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));n=m;

Try it online!

---

Edit: I think my original solution (Try it online!) 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

share|improve this answer

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

C (gcc), 93 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;g(d=i*i^n)<m&&d<n/2&&(m=g(d)));n=m;

Try it online!

---

Edit: I think my original solution (Try it online!) 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

share|improve this answer

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

share|improve this answer

share|improve this answer

edited Aug 10 at 15:44

edited Aug 10 at 15:44

edited Aug 10 at 15:44

answered Aug 10 at 14:55

Annyo

1213

answered Aug 10 at 14:55

Annyo

1213

answered Aug 10 at 14:55

Annyo

1213

1213

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170281%2ftoggle-some-bits-and-get-a-square%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email