Verdopple, XOR und mach es noch einmal

20

Wir definieren die Funktion g als g (n) = n XOR (n * 2) für eine beliebige ganze Zahl n> 0 .

Wenn x> 0 ist , finde die kleinste ganze Zahl y> 0, so dass g k (y) = x für einige k> 0 ist .

Beispiel

x = 549

549 = 483 XOR (483 * 2)     (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2)     (as binary:  111100011 =  10100001 XOR  101000010)

Was bedeutet, dass g 2 (161) = 549 ist . Wir können nicht weiter gehen, da es keine n , so dass g (n) 161 = . Die erwartete Ausgabe für x = 549 ist also y = 161 .

Regeln

  • Sie dürfen keine ungültigen Einträge unterstützen. Für den Eingabewert x ist garantiert ein Paar (y, k) vorhanden .
  • Das ist , also gewinnt die kürzeste Antwort in Bytes!

Testfälle

     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1
Arnauld
quelle
3
Verwandte OEIS: A048274, die die Sequenz ista(n) = g(n)
Giuseppe

Antworten:

5

Java 8, 68 57 53 52 Bytes

n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}

-5 Bytes dank @ OlivierGrégoire .

Probieren Sie es online aus.

Erläuterung:

n->{                 // Method with integer as both parameter and return-type
  for(int i=0;i<n;)  //  Loop `i` in the range (1,n)
    i-=(i*2^i)==n?   //   If `i*2` XOR-ed with `i` equals `n`
        n=i          //    Set `n` to `i`, and set `i` to 0 to reset the loop
       :             //   Else:
        -1;          //    Increase `i` by 1 to go to the next iteration
  return n;}         //  Return `n` after the entire loop
Kevin Cruijssen
quelle
1
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}(52 Bytes). Sorry ^^ '
Olivier Grégoire
@ OlivierGrégoire Noch schlauer, danke!
Kevin Cruijssen
for(int i=0;n>i-=i+i^i^n?-1:n=i;);?
Titus
@Titus Ich fürchte, das wird in Java nicht funktionieren (obwohl ich diesen Ansatz in meiner iterativen JavaScript-Antwort verwendet habe ). In Java i+i^i^n?ist es kein Boolescher Wert, daher wird es nicht einmal kompiliert. Außerdem n>i-=...wird parenthesis ( n>(i-=...)) benötigt und n=iist in der else-Klausel des ternary-if nicht erlaubt, nur in der if-Klausel (diese letzte weiß ich nicht warum, aber das ist es leider in Java ).
Kevin Cruijssen
1
@KevinCruijssen "und n=iist in der else-Klausel des ternary-if nicht erlaubt". Weil Java es als (i-=(i*2^i)!=n?-1:n)=iillegal analysieren würde .
Olivier Grégoire
3

JavaScript, 53 Byte

f=x=>(i=0,y=(G=x=>x&&(i^=x&1)+2*G(x>>1))(x),i?x:f(y))

Gist g^-1, die festgelegt iauf , 0wenn der Erfolg, setzen Sie iauf , 1wenn fehlgeschlagen.

tsh
quelle
1
Dies war der Ansatz , den ich zu verwenden versucht , obwohl ich mit einer 50-Bit - Version kam: f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n. Leider ist der langweilige Ansatz 12 Bytes kürzer.
Neil
3

Pyth , 13 12 10 Bytes

1 Byte dank @MrXcoder und 2 weitere Bytes nach ihrem Vorschlag gespeichert

fqQ.W<HQxy

Probieren Sie es online aus

Erläuterung:

fqQ.W<HQxyZZT   Implicit: Q=eval(input()), trailing ZZT inferred

f               Return the first T in [1,2,3...] where the following is truthy
   .W       T     Functional while - loop until condition is true, starting value T
     <HQ            Condition: continue while iteration value (H) less than input
        xyZZ        Body: xor iteration value (Z) with double (y) iteration value (Z)
 qQ               Is the result of the above equal to input?
Sok
quelle
1
Sie können das Trailing Tfür 12 Bytes löschen.
Mr. Xcoder
3

R , 73 65 Bytes

f=function(x){for(i in 1:x)if(x==bitwXor(i,i*2)){i=f(i);break};i}

Probieren Sie es online!

Vielen Dank, Giuseppe (-8), aufgrund deiner Optimierungen, so einfach und doch sehr effektiv

DS_UNI
quelle
1
wie zu einer früheren Antwort von Ihnen gegenüber , da diese Funktion rekursiv ist, Sie tun müssen , die f=da die Funktion Bedürfnisse gebunden sein , um frichtig zu funktionieren. Davon abgesehen, gute Arbeit, und nimm eine +1 von mir!
Giuseppe
2
Sie können auch Ihre Logik neu triggern und dies auf 65 Bytes bringen
Giuseppe
2

JavaScript, 38 36 Bytes

f=(n,x=n)=>x?x^x+x^n?f(n,--x):f(x):n

Online testen - Startet das Auslösen von Überlauffehlern zwischen 9999& 57308.

Zottelig
quelle
2

Gelee , 8 7 Bytes

Verwenden Sie ⁺¿diese Option , um das letzte Element ungleich Null zurückzugeben (danke Dennis für -1 Byte).

^Ḥ)i$⁺¿

Probieren Sie es online!

Brute Force gewinnt erneut :(

user202729
quelle
1
^Ḥ)i$⁺¿Speichert ein Byte.
Dennis
Und es ist 2x langsamer.
user202729
2

C (gcc) , 57 56 55 51 Bytes

X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}

Probieren Sie es online!

Jonathan Frech
quelle
1
+1 fürX(O,R)
JayCe
@ceilingcat Guter Vorschlag, danke.
Jonathan Frech
for(R=1;R;O=R?R:O)Speichert ein Byte.
R=O;am ende scheint das unnötig zu sein und erspart euch weitere 4 bytes.
@Rogem Scheint zu sein, danke.
Jonathan Frech
2

Z80Golf , 22 Bytes

00000000: 1600 1803 4216 007a b830 097a 82aa b828  ....B..z.0.z...(
00000010: f314 18f3 78c9                           ....x.

Portierung der Java-Antwort von @ KevinCruijssen

Beispiel mit Eingabe von 9-Online ausprobieren!

Beispiel mit Eingabe von 85-Online ausprobieren!

Versammlung:

;d=loop counter
;b=input and output
f:
	ld d,0
	jr loop
	begin:
	ld b,d
	ld d,0
	loop:
		ld a,d
		cp b
		jr nc,end	; if d==b end
		ld a,d
		add d		; mul by 2
		xor d
		cp b
		jr z,begin	; if (d*2)^d==b set b to d
		inc d
		jr loop
	end:
	ld a,b
	ret

Assembly-Beispiel zum Aufrufen der Funktion und zum Drucken des Ergebnisses:

ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
Logern
quelle
Wenn Sie astattdessen den Schleifenzähler erstellen d, können Sie die ld d,0Anweisungen durch xor abeide Male ersetzen , wodurch zwei Bytes eingespart werden.
Mischa Lawrow
1

JavaScript (Node.js), 48 45 38 Bytes

f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n

-7 Bytes dank @Neil, der unten eine rekursive Version meiner iterativen Version erstellt. Funktioniert nicht für große Testfälle.

Probieren Sie es online aus.


Iterative 45-Byte- Version, die für alle Testfälle funktioniert:

n=>{for(i=0;i<n;)i-=i*2^i^n?-1:n=i;return n;}

Port meiner Java-Antwort.
-3 Bytes dank @Arnauld .

Probieren Sie es online aus.

Kevin Cruijssen
quelle
1
Das kannst du i-=i*2^i^n?-1:n=i(aber leider nicht in Java).
Arnauld
@Arnauld Es stellte sich heraus, dass etwas für den Booleschen in Java möglich war, nur 1in JS. Vielen Dank!
Kevin Cruijssen
1
38 Bytes rekursiv geschrieben (funktioniert bei größeren Eingaben nicht):f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Neil
1

Ruby , 39 Bytes

f=->x,y=x{y<1?x:x==y^y*2?f[y]:f[x,y-1]}

Probieren Sie es online!

Wie in der rekursiven Version zu erwarten, wird in letzteren Testfällen eine zu tiefe Stapelebene beanstandet.

Kirill L.
quelle
1

Jelly , 11 9 Bytes

BÄḂṛḄß$Ṫ?

Probieren Sie es online!

Tipps: Verwenden Sie rekursive Funktionen anstelle von Schleifen.


Sehr schnell, verliert leider an der Brute-Force-Annäherung.

Beachten Sie, dass:

  • Für x> 0 gilt f (x)> x .
  • popcount (f (x)) ist gerade, wobei popcount (n) die Anzahl der in n gesetzten Bits ist .
  • Wenn n auch PopCount hat, dann gibt es x , so dass f (x) = n .
  • Sei B (x) die Binärdarstellung von x und Ṗ (l) die Liste l ohne letztes Element. Dann ist B (x) das akkumulierte XOR von Ṗ (B (f (x))) .

Also haben wir wiederholt:

  • Berechne seine Binärdarstellung ( B)
  • dann nimm das akkumulierte XOR (benutze ^\oder ÄḂ, sie haben den gleichen Effekt).
  • Überprüfen Sie, ob ( ?) das Ende (letztes Element) ( ) des akkumulierten XOR ungleich Null ist (ungerade Popcount).
    • Wenn ja, konvertieren Sie die Binärliste zurück in dezimal und rekursiv.
    • Wenn nicht, wird die Eingabe ( ) zurückgegeben.
user202729
quelle
9 Bytes:B^\⁸Ḅß$Ṫ?
Undichte Nonne
1

Viertens (gviertens) , 71 Bytes

: f 0 begin 2dup dup 2* xor = if nip 0 else 1+ then 2dup < until drop ;

Probieren Sie es online!

Erläuterung

0                 \ add an index variable to the top of the stack
begin             \ start an indefinite loop
  2dup            \ duplicate the top two stack items (n and i)
  dup 2* xor =    \ calculate i xor 2i and check if equal to n
  if nip 0        \ if equal, drop n (making i the new n) and use 0 as the new i
  else 1+         \ otherwise just increment i by 1
  then            \ end the if-statement
  2dup <          \ duplicate the top two stack items and check if n < i
until             \ if previous statement is true, end the loop
drop              \ drop i, leaving n on top of the stack
reffu
quelle
1

Perl 6 , 44 Bytes

{({first {($^a+^2*$a)==$_},^$_}...^!*).tail}

Versuch es

Erweitert:

{  # bare block lambda with implicit parameter $_

  (
    # generate a sequence

    # no need to seed the sequence with $_, as the following block will
    # default to using the outer $_
    # $_, 

    { # parameter $_

      first
        {  # block with placeholder parameter $a

          ( $^a +^ 2 * $a ) # double (numeric) xor
          == $_             # is it equal to the previous value
        },

        ^$_  # Range up to and excluding the previous value ( 0..^$_ )
    }

    ...^  # keep doing that until: (and throw away last value)

    !*    # it doesn't return a trueish value

  ).tail  # return the last generated value
}
Brad Gilbert b2gills
quelle
1

PHP, 49 Bytes

Basierend auf den Antworten von Kevin Cruijssen.

for($x=$argn;$x>$i-=$i*2^$i^$x?-1:$x=$i;);echo$x;

Laufen Sie als Pipe mit -nroder versuchen Sie es online .

Titus
quelle
1

F #, 92 Bytes

let rec o i=
 let r=Seq.tryFind(fun x->x^^^x*2=i){1..i-1}
 if r.IsNone then i else o r.Value

Probieren Sie es online!

Überprüft rekursiv die Zahlen von 1 bis i-1. Wenn eine Übereinstimmung vorliegt, suchen Sie nach einer kleineren für diese Nummer. Wenn es keine Übereinstimmung gibt, geben Sie die eingegebene Nummer zurück.

Ciaran_McCarthy
quelle
1

JavaScript (Node.js) , 40 Byte

f=n=>g(n)%2?n:f(g(n)/2)
g=x=>x&&x^g(x/2)

Probieren Sie es online!

Danke Shaggy für -1 Bytes.

Port meiner Gelee Antwort .

Schließlich gibt es eine Sprache, in der dieser Ansatz kürzer ist ( oops ). (Ich habe versucht, Python und Java , es funktioniert nicht)

Kann mir jemand erklären, warum ich /2anstelle von verwenden kann >>1?

user202729
quelle
1
x/2funktioniert wegen arithmetischem Unterlauf. Jede IEEE 754-Nummer wird schließlich als 0 gewertet, wenn sie zweimal geteilt wird. (Und der Dezimalteil wird beim XOR einfach ignoriert, daher hat dies keinen Einfluss auf das Ergebnis.)
Arnauld
40 Bytes
Shaggy
@ Shaggy Überrascht, dass es funktioniert. Ich weiß, dass es für Python und Lua usw. funktioniert, aber nicht für Javascript.
user202729
Der falsebei der letzten Iteration zurückgegebene Wert wird implizit 0vom bitweisen XOR-Operator umgewandelt.
Shaggy
@ Shaggy In der Tat ist kein falsebeteiligt . JS &&verhält sich fast identisch zu Python / Lua and.
user202729
1

K (ngn / k) , 32 26 Bytes

{$[*|a:2!+\2\x;x;2/-1_a]}/

Probieren Sie es online!

{ } ist eine Funktion mit Argument x

/ wendet es bis zur Konvergenz an

$[ ; ; ] wenn-dann-sonst

2\xBinärziffern von x(dies ist spezifisch für ngn / k)

+\ Teilsummen

2! mod 2

a: zuweisen a

*|last - reverse ( |) und get first ( *)

Wenn der obige Wert 1 ist, xwird er zurückgegeben

Andernfalls:

-1_a Lasse das letzte Element von fallen a

2/ binär dekodieren

ngn
quelle
0

C 62 Bytes

Basierend auf Kevin Cruijssens Java:

int n(int j){for(int i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}

Zu testen:

#include <stdio.h>
int n(int j);
#define p(i) printf("%6d --> %5d\n", i, n(i))
int main(void)
{
    p(3);
    p(5);
    p(6);
    p(9);
    p(10);
    p(23);
    p(85);
    p(549);
    p(960);
    p(1023);
    p(1155);
    p(1542);
    p(9999);
    p(57308);
    p(57311);
    p(983055);
}

Beim Ausführen gibt das Testprogramm Folgendes aus:

     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1

C 54 Bytes

Funktioniert nur mit C89 oder K & R C:

n(j){for(i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}

JustinCB
quelle
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}Funktionieren diese 57 Bytes?
Titus
0

Wolfram Language (Mathematica) , 58 Byte

Min[{#}//.x_:>Select[Range@#,MemberQ[x,#|BitXor[#,2#]]&]]&

Probieren Sie es online!

Beginnt mit einer Liste, die nur die Eingabe enthält. Ersetzt die Liste iterativ durch alle bereits enthaltenen Ganzzahlen oder ordnet sie durch die Operation double-and-xor zu. Dann //.sagt man dies bis zum Erreichen eines festen Punktes. Die Antwort ist das kleinste Element des Ergebnisses.

Mischa Lawrow
quelle