Gandakan, XOR dan lakukan lagi

20

Kami mendefinisikan fungsi g sebagai g (n) = n XOR (n * 2) untuk bilangan bulat apa pun n> 0 .

Diberikan x> 0 , temukan bilangan bulat terkecil y> 0 sedemikian sehingga g k (y) = x untuk beberapa k> 0 .

Contoh

x = 549

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

Yang berarti bahwa g 2 (161) = 549 . Kita tidak bisa melangkah lebih jauh, karena tidak ada n sedemikian sehingga g (n) = 161 . Jadi, output yang diharapkan untuk x = 549 adalah y = 161 .

Aturan

  • Anda tidak seharusnya mendukung entri yang tidak valid. Sepasang (y, k) dijamin ada untuk nilai input x .
  • Ini , jadi jawaban tersingkat dalam byte menang!

Uji kasus

     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
sumber
3
OEIS terkait: A048274 yang merupakan urutana(n) = g(n)
Giuseppe

Jawaban:

5

Java 8, 68 57 53 52 byte

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

-5 byte terima kasih kepada @ OlivierGrégoire .

Cobalah online.

Penjelasan:

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
sumber
1
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}(52 byte). Maaf ^^ '
Olivier Grégoire
@ OlivierGrégoire Bahkan lebih pintar, terima kasih!
Kevin Cruijssen
for(int i=0;n>i-=i+i^i^n?-1:n=i;);?
Titus
@Itus Saya khawatir itu tidak akan berhasil di Jawa (walaupun saya telah menggunakan pendekatan itu dalam jawaban JavaScript berulang saya ). Di Jawa i+i^i^n?bukan boolean, jadi tidak akan dikompilasi. Selain itu, n>i-=...akan membutuhkan tanda kurung ( n>(i-=...)), dan n=itidak diperbolehkan dalam klausa lain dari ternary-if, hanya dalam if-klausa (yang terakhir ini saya tidak tahu mengapa, tapi itulah yang ada di Jawa sayangnya ).
Kevin Cruijssen
1
@KevinCruijssen "dan n=itidak diizinkan dalam klausa lain dari ternary-if". Karena Jawa akan menguraikannya sebagai (i-=(i*2^i)!=n?-1:n)=iyang ilegal.
Olivier Grégoire
4

Python 2 , 54 53 byte

f=lambda n:next((f(i)for i in range(n)if n==i^i*2),n)

Cobalah online!

TFeld
sumber
3

JavaScript, 53 byte

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

Gadalah g^-1, yang disetel ike 0jika berhasil, diatur ike 1jika gagal.

tsh
sumber
1
Ini adalah pendekatan yang saya mencoba untuk menggunakan meskipun saya datang dengan versi 50-byte: f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n. Sayangnya pendekatan yang membosankan lebih pendek 12 byte.
Neil
3

Pyth , 13 12 10 byte

Disimpan 1 byte berkat @MrXcoder, dan 2 byte lainnya mengikuti saran mereka

fqQ.W<HQxy

Cobalah online

Penjelasan:

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
sumber
1
Anda dapat menjatuhkan trailing Tselama 12 byte.
Tn. Xcoder
3

R , 73 65 byte

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

Cobalah online!

Terima kasih banyak, Giuseppe (-8) karena tweak Anda, sangat sederhana namun sangat efektif

DS_UNI
sumber
1
sebagai lawan dari jawaban Anda sebelumnya, karena fungsi ini bersifat rekursif, Anda memang memerlukannya f=karena fungsi tersebut harus terikat fagar berfungsi dengan benar. Yang sedang berkata, kerja bagus, dan ambil +1 dari saya!
Giuseppe
2
Anda juga dapat melakukan beberapa jiggering logika Anda dan mendapatkan ini hingga 65 byte
Giuseppe
2

JavaScript, 38 36 byte

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

Cobalah online - Mulai melempar kesalahan overflow di antara 9999& 57308.

Shaggy
sumber
2

Jelly , 8 7 byte

Gunakan ⁺¿untuk mengembalikan elemen non-nol terakhir (terima kasih Dennis untuk -1 byte)

^Ḥ)i$⁺¿

Cobalah online!

Brute force menang lagi :(

pengguna202729
sumber
1
^Ḥ)i$⁺¿menghemat satu byte.
Dennis
Dan itu 2x lebih lambat.
user202729
2

C (gcc) , 57 56 55 51 byte

  • Menyimpan satu byte berkat plafon ; !=-.
  • Menyimpan byte lima byte berkat Rogem ; memanfaatkan ekspresi terner dan kebiasaan gcc.
X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}

Cobalah online!

Jonathan Frech
sumber
1
+1 untukX(O,R)
JayCe
@ceilingcat Saran yang bagus, terima kasih.
Jonathan Frech
for(R=1;R;O=R?R:O)menghemat satu byte.
R=O;pada akhirnya tampaknya tidak perlu, menghemat 4 byte lagi.
@Rogem Sepertinya, terima kasih.
Jonathan Frech
2

Z80Golf , 22 byte

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

Jawaban Java dari Port @ KevinCruijssen

Contoh dengan input 9-Coba online!

Contoh dengan input 85-Coba online!

Majelis:

;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

Contoh perakitan untuk memanggil fungsi dan mencetak hasilnya:

ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
Logern
sumber
Jika Anda membuat apenghitung lingkaran alih-alih d, maka Anda dapat mengganti ld d,0instruksi dengan xor adua kali, yang menghemat dua byte.
Misha Lavrov
1

Java (JDK 10) , 78 byte

int g(int n){return f(n)%2<1?g(f(n)/2):n;}int f(int x){return 1>x?0:x^f(x/2);}

Cobalah online!

pengguna202729
sumber
1

JavaScript (Node.js), 48 45 38 byte

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

-7 byte terima kasih kepada @Neil membuat versi rekursif dari versi iteratif saya di bawah ini. Tidak berfungsi untuk kasus uji besar.

Cobalah online.


Versi berulang 45 byte yang berfungsi untuk semua kasus uji:

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

Port jawaban Java saya.
-3 byte terima kasih kepada @Arnauld .

Cobalah online.

Kevin Cruijssen
sumber
1
Anda dapat melakukannya i-=i*2^i^n?-1:n=i(tetapi sayangnya tidak di Jawa).
Arnauld
@Arnauld Berpikir ada sesuatu yang mungkin bagi boolean di Jawa hanya 1di JS. Terima kasih!
Kevin Cruijssen
1
38 byte ditulis secara rekursif (tidak bekerja untuk input yang lebih besar):f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Neil
1

Ruby , 39 byte

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

Cobalah online!

Seperti yang diharapkan untuk versi rekursif, mengeluh tentang "tingkat tumpukan terlalu dalam" pada kasus uji terakhir.

Kirill L.
sumber
1

Jelly , 11 9 byte

BÄḂṛḄß$Ṫ?

Cobalah online!

Tips: Gunakan fungsi rekursif bukan loop.


Sangat cepat, sayangnya kalah dari pendekatan brute force.

Perhatikan bahwa:

  • Untuk x> 0 , f (x)> x .
  • popcount (f (x)) genap, di mana popcount (n) adalah jumlah bit yang ditetapkan dalam n .
  • Jika n bahkan memiliki popcount, maka ada x sedemikian rupa sehingga f (x) = n .
  • Biarkan B (x) menjadi representasi biner dari x , dan Ṗ (l) menjadi daftar l dengan elemen terakhir dihapus. Maka B (x) adalah akumulasi XOR dari Ṗ (B (f (x))) .

Jadi, kami berulang kali:

  • Hitung representasi binernya ( B)
  • kemudian ambil akumulasi XOR (gunakan ^\atau ÄḂ, mereka memiliki efek yang sama).
  • Periksa apakah ( ?) ekor (elemen terakhir) ( ) dari akumulasi XOR adalah nol (jumlah pop aneh)
    • Jika demikian, konversikan daftar biner kembali ke desimal dan berulang.
    • Jika tidak, kembalikan input ( ).
pengguna202729
sumber
9 byte:B^\⁸Ḅß$Ṫ?
Leaky Nun
1

Keempat (gforth) , 71 byte

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

Cobalah online!

Penjelasan

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
sumber
1

Perl 6 , 44 byte

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

Cobalah

Diperluas:

{  # 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
sumber
1

PHP, 49 byte

Berdasarkan jawaban Kevin Cruijssen.

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

Jalankan sebagai pipa dengan -nratau coba online .

Titus
sumber
1

F #, 92 byte

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

Cobalah online!

Secara rekursif memeriksa angka-angka dari 1 hingga i-1. Jika ada kecocokan, periksa yang lebih kecil untuk nomor itu. Jika tidak ada yang cocok, kembalikan nomor input.

Ciaran_McCarthy
sumber
1

JavaScript (Node.js) , 40 byte

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

Cobalah online!

Terima kasih Shaggy untuk -1 byte.

Port jawaban Jelly- ku .

Akhirnya ada bahasa di mana pendekatan ini lebih pendek ( oops ). (Saya mencoba Python dan Java , tidak berhasil)

Adakah yang bisa menjelaskan mengapa saya bisa menggunakan /2bukan >>1?

pengguna202729
sumber
1
x/2bekerja karena aritmatika underflow. Setiap nomor IEEE 754 pada akhirnya akan dievaluasi sebagai 0 bila dibagi 2 kali cukup. (Dan bagian desimal diabaikan begitu saja ketika XOR, jadi ini tidak mempengaruhi hasilnya.)
Arnauld
40 byte
Shaggy
@ Shaggy Terkejut bahwa itu bekerja. Saya tahu ini berfungsi untuk Python dan Lua dll, tetapi tidak Javascript.
user202729
Pengembalian falsepada iterasi terakhir secara implisit dilemparkan ke 0oleh operator XOR bitwise.
Shaggy
@ Shaggy Bahkan, tidak ada falseyang terlibat . JS &&berperilaku hampir identik dengan Python / Lua and.
user202729
1

K (ngn / k) , 32 26 byte

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

Cobalah online!

{ } adalah fungsi dengan argumen x

/ menerapkannya sampai konvergensi

$[ ; ; ] jika-maka-lain

2\xdigit biner dari x(ini khusus untuk ngn / k)

+\ jumlah parsial

2! mod 2

a: ditugaskan kepada a

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

jika di atas adalah 1, xakan dikembalikan

jika tidak:

-1_a drop elemen terakhir dari a

2/ mendekode biner

ngn
sumber
0

C, 62 byte

Berdasarkan Java Kevin Cruijssen:

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

Untuk menguji:

#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);
}

Saat dijalankan, program pengujian menghasilkan:

     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 byte

Hanya bekerja dengan C89 atau K&R C:

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

JustinCB
sumber
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}Apakah 57 byte ini berfungsi?
Titus
0

Bahasa Wolfram (Mathematica) , 58 byte

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

Cobalah online!

Mulai dengan daftar yang hanya berisi input. Iteratif mengganti daftar dengan semua bilangan bulat yang sudah ada di dalamnya, atau memetakannya dengan operasi double-and-xor. Lalu //.katakan untuk melakukan ini sampai mencapai titik yang tetap. Jawabannya adalah elemen paling sedikit dari hasilnya.

Misha Lavrov
sumber