Periksa apakah bilangan bulat adalah kekuatan 2 tanpa menggunakan +, - operasi [tertutup]

30

Tulis program yang memeriksa apakah bilangan bulat adalah kekuatan 2.


Input sampel:

8

Output sampel:

Yes

Input sampel:

10

Output sampel:

No

Aturan:

  • Jangan gunakan +, -operasi.

  • Gunakan semacam aliran input untuk mendapatkan nomor. Input semula tidak seharusnya disimpan dalam variabel.

  • Kode terpendek (dalam byte) menang.

Anda dapat menggunakan respons yang benar / salah (misalnya, true/ false). Anda dapat berasumsi bahwa jumlah input lebih besar dari 0.

gthacoder
sumber
1
Apakah itu juga diizinkan untuk menampilkan "benar", bukan "ya" dan "salah", bukan "tidak"?
ProgramFOX
2
Ya, Anda dapat menggunakan respons positif / negatif. Pertanyaan diperbarui.
gthacoder
1
The predFungsi, bila diterapkan ke integer n, kembali n - 1. Apakah fungsi seperti ini, yang penyamaran tipis sekitar operator dilarang, juga dilarang?
Wayne Conrad
1
@Wayne sama seperti skrip golf ), atau sebagian besar bahasa berbasis c ' --.
Gagang Pintu
2
Saya tahu kami 3 tahun di masa depan sekarang, tetapi "+/- operator" tidak dapat diamati, atau paling tidak didefinisikan dengan lemah.
ATaco

Jawaban:

13

GolfScript, 6 karakter, tanpa pengurangan

~.3/&!

Inilah solusi yang tidak menggunakan x & (x-1)metode dalam bentuk apa pun . Ini menggunakan x & (x/3)sebagai gantinya. ;-) Keluaran 0jika salah, 1jika benar.

Penjelasan:

  • ~ evals string input untuk mengubahnya menjadi angka,
  • .duplikat (untuk selanjutnya &),
  • 3/ membaginya dengan tiga (memotong ke bawah),
  • & menghitung bitwise AND dari nilai yang dibagi dengan yang asli, yang akan menjadi nol jika dan hanya jika inputnya nol atau memiliki kekuatan dua (yaitu memiliki paling banyak satu set bit), dan
  • ! secara logis meniadakan ini, memetakan nol ke satu dan semua nilai lainnya ke nol.

Catatan:

  • Sesuai aturan yang diklarifikasi, nol bukan input yang valid , jadi kode ini tidak apa-apa, meskipun output 1jika inputnya nol.

  • Jika operator decrement GolfScript (diperbolehkan, maka 5 karakter solusi ~.(&! diposting oleh aditsu cukup. Namun, tampaknya bertentangan dengan semangat aturan , jika bukan surat itu.

  • Saya menemukan x & (x/3)triknya bertahun-tahun yang lalu di milis Fun With Perl. (Saya yakin saya bukan orang pertama yang menemukannya, tetapi saya memang menciptakannya kembali.) Berikut ini tautan ke pos asli , termasuk bukti bahwa itu benar-benar berfungsi.

Ilmari Karonen
sumber
Saya pikir itu agak konyol sebenarnya, skrip golf memungkinkan seseorang untuk menulis solusi tepat yang ingin dikeluarkan OP tanpa benar-benar melanggar aturan.
Tim Seguine
1
@Tim: Oke, ini dia tanpa pengurangan, lalu. ;)
Ilmari Karonen
bagaimana ini bisa bekerja? Sebagai contoh 7/3 = 2 (0010), jadi 7 & 2 = 0111 & 0010 = 0010yang jelas bit terakhir bukan 1
phuclv
@ LưuVĩnhPhúc: Tidak, tetapi bit kedua adalah. Coba lakukan pembagian panjang dengan 3 dalam biner dan itu cukup jelas mengapa ini selalu terjadi jika dividen memiliki lebih dari satu bit yang ditetapkan.
Ilmari Karonen
ah saya salah membaca ini dengan "habis dibagi 2"
phuclv
15

APL (7)

Ya, itu 7 byte . Asumsikan untuk saat ini saya menggunakan IBM codepage 907 alih-alih Unicode dan kemudian setiap karakter adalah byte :)

0=1|2⍟⎕

yaitu 0 = mod(log(input(),2),1)

marinus
sumber
Hanya ingin tahu, apa yang terjadi jika Anda memberikannya 0 atau angka negatif?
aditsu
@aditsu Saya tidak tahu apa itu infinity mod 1, tetapi tentu tidak boleh nol.
Tim Seguine
1
@TimSeguine Mathematica memberi saya Indeterminateketika saya mencobanya.
LegionMammal978
7

GolfScript, 11 (untuk 1 (benar) dan 0 (salah))

.,{2\?}%?0>

Masukkan nomor pada tumpukan dan kemudian jalankan.

GolfScript, 22 (untuk Ya / Tidak)

.,{2\?}%?0>'Yes''No'if

Saya suka bagaimana mengkonversi 1/ 0ke Yes/ Nomengambil kode sebanyak tantangan itu sendiri: D

Peringatan: SANGAT tidak efisien;) Tidak berfungsi dengan baik untuk angka hingga 10.000, tetapi begitu Anda mendapatkan setinggi itu, Anda mulai melihat sedikit jeda.

Penjelasan:

  • .,: berubah nmenjadi n 0..n( .duplikat, ,rentang 0..n)
  • {2\?}: dengan kekuatan 2
  • %: memetakan "kekuatan 2" lebih dari "0..n" sehingga menjadi n [1 2 4 8 16 ...]
  • ?0>: memeriksa untuk melihat apakah array berisi angka (0 lebih besar dari indeks)
Gagang pintu
sumber
1
1 byte lebih pendek untuk Ya / Tidak .,{2\?}%?0<'YesNo'3/=:; juga saya pikir Anda curang dengan meminta "Masukkan nomor di tumpukan", Anda harus mulai dengan ~.
aditsu
1
Gagal pada 1, yaitu 2 ^ 0
Joachim Isaksson
6

Mathematica 28

Numerator[Input[]~Log~2]==1

Untuk kekuatan bilangan bulat 2, pembilang dari log basis 2 akan menjadi 1 (artinya log adalah fraksi satuan).

Di sini kita memodifikasi fungsi sedikit untuk menampilkan input yang diduga. Kami menggunakan #menggantikan Input[]dan menambahkan &untuk mendefinisikan fungsi murni. Ini mengembalikan jawaban yang sama yang akan dikembalikan jika pengguna memasukkan angka dalam fungsi di atas.

    Numerator[#~Log~2] == 1 &[1024]
    Numerator[#~Log~2] == 1 &[17]

Benar
salah

Menguji beberapa angka sekaligus.

    Numerator[#~Log~2] == 1 &&/@{64,8,7,0}

{Benar, Benar, Salah, Salah}

DavidC
sumber
4

Perl 6 (17 karakter)

say get.log(2)%%1

Program ini mendapat garis dari getfungsi STDIN , menghitung logaritma dengan basis 2 di atasnya ( log(2)), dan memeriksa apakah hasilnya dibagi dengan 1 ( %%1, di mana %%dibagi oleh operator). Tidak sesingkat solusi GolfScript, tapi saya menemukan ini dapat diterima (GolfScript memenangkan segalanya), tetapi lebih cepat (bahkan mengingat Perl 6 sedang lambat saat ini).

~ $ perl6 -e 'say get.log(2)%%1'
256
True
~ $ perl6 -e 'say get.log(2)%%1'
255
False
Konrad Borowski
sumber
2
Alasan bahwa +dan -dilarang untuk tantangan ini, adalah karena jika x & (x - 1)sama dengan 0, maka xadalah kekuatan 2.
ProgramFOX
@ProgramFOX: Begitu. Trik yang menarik.
Konrad Borowski
1
@ProgramFOX Tapi x&~(~0*x)masih berfungsi. Itu hanya 2 karakter lagi.
orlp
4

Oktaf ( 15 23)

EDIT: Diperbarui karena persyaratan input pengguna;

~mod(log2(input('')),1)

Memungkinkan pengguna memasukkan nilai dan output 1 untuk true, 0 untuk false.

Diuji dalam Oktaf, harus bekerja di Matlab juga.

Joachim Isaksson
sumber
Bekerja di Matlab juga :)
jub0bs
4

R, 13 11

Berdasarkan solusi Perl. Pengembalian FALSEatau TRUE.

!log2(i)%%1

Parameter i mewakili variabel input.

Versi alternatif dengan input pengguna:

!log2(scan())%%1
Sven Hohenstein
sumber
4

GolfScript, 5

Output 1 untuk true, 0 untuk false. Berdasarkan ide user3142747:

~.(&!

Catatan: (adalah pengurangan, mudah-mudahan itu tidak dihitung sebagai -:)
Jika ya (dan komentar OP menyarankan itu mungkin), maka silakan merujuk ke solusi Ilmari Karonen sebagai gantinya.
Untuk output Y / N, tambahkan 'NY'1/=di akhir (7 byte lebih).

aditsu
sumber
4

Python, 31

print 3>bin(input()).rfind('1')
stan
sumber
31 jika Anda melakukannyabin(input()).rfind('1')<3
Blender
@Blender Terlihat dengan baik. Saya telah menggunakan 2==karena saya pikir itu harus bekerja untuk nomor nonpositif juga. Itu secara eksplisit tidak diharuskan oleh aturan, jadi ...
stan
1
+1. Saya akan memposting print bin(input()).count('1')<2dengan total 31 karakter, tetapi terlalu mirip dengan Anda.
Steven Rumbalski
4

C, 48

main(x){scanf("%i",&x);puts(x&~(x*~0)?"F":"T");}
orlp
sumber
Dapat lebih pendek jika negasi unary diizinkan, lebih lama jika konstanta negatif tidak diperbolehkan. Mengasumsikan komplemen dua.
orlp
*memiliki prioritas lebih tinggi daripada biner &, Anda tidak perlu parens. Dan jika nilai pengembalian diterima (hanya diminta) exit(x&x*-1)akan jauh lebih pendek.
Kevin
Ada -: x*-1.
klingt.net
@ klingt.net ya, tapi itu bagian dari konstanta numerik. Secara teknis, seperti yang dikatakan sekarang, hanya operator -yang dilarang.
Kevin
1
@ klingt.net Menggantinya dengan versi yang tidak menggunakan tanda.
orlp
4

Saya memutuskan untuk menggunakan pendekatan lain, berdasarkan jumlah populasi atau jumlah sideways dari jumlah (jumlah 1-bit). Idenya adalah bahwa semua kekuatan dua memiliki tepat satu1 bit, dan tidak ada angka lainnya. Saya menambahkan versi JavaScript karena menurut saya itu lucu, meskipun tentu tidak akan memenangkan kompetisi golf.

J, 14 15 karakter (output 0 atau 1)

1=##~#:".1!:1]1

JavaScript, 76 karakter (output benar atau salah)

alert((~~prompt()).toString(2).split("").map(Number).filter(Boolean).length)
FireFly
sumber
Ini menggunakan tambahan, yang terhalang oleh tantangan.
FUZxxl
Hah. Saya tidak tahu apa yang saya pikirkan ketika saya menulis ini ... Saya sudah memperbaikinya sekarang sehingga benar-benar mengikuti aturan.
FireFly
4

Klip , 9 8 7

!%lnxWO

Membaca angka dari stdin.

Penjelasan:

Untuk mulai dengan, Z= 0, W= 2dan O= 1. Ini memungkinkan penempatan Wdan di Osamping satu sama lain, sedangkan menggunakan 2dan 1akan ditafsirkan sebagai angka 21 tanpa ruang pemisah (karakter tambahan yang tidak diinginkan). Dalam Klip, fungsi modulo ( %) bekerja pada non-integer, jadi, untuk mengetahui apakah beberapa nilai vadalah integer, Anda memeriksa apakah vmod 1 = 0. Menggunakan sintaksis Klip, ini ditulis sebagai =0%v1. Namun, sebagai booleans disimpan sebagai 1(atau apa pun) dan 0, memeriksa apakah ada yang sama dengan 0hanya 'tidak' itu. Untuk ini, Clip memiliki !operator. Dalam kode saya, vadalah lnx2. xadalah input dari stdin,nmengkonversi string ke nomor dan labbasis log .bdari a. Oleh karena itu, program ini menerjemahkan (lebih mudah dibaca) menjadi0 = ((log base 2 of parseInt(readLine)) mod 1)

Contoh:

8

output

1

dan

10

output

0

Sunting 1: diganti 0, 1dan 2dengan Z, OdanW .

Sunting 2: diganti =Zdengan! .

Juga:

Pyth , 5

Kompres versi Klip lebih jauh, karena Pyth memiliki Q untuk input yang sudah dievaluasi dan fungsi log2 (a), bukan hanya log umum (a, b).

!%lQ1
bcsb1001
sumber
3

Javascript (37)

a=prompt();while(a>1)a/=2;alert(a==1)

Skrip sederhana yang hanya dibagi 2 berulang kali dan memeriksa sisanya.

Joachim Isaksson
sumber
1
ide yang sama dengan satu forlingkaran (juga 37 karakter)for(i=prompt();i>1;i/=2){}alert(i==1)
Math chiller
3

Mathematica (21)

IntegerQ@Log2@Input[]

Tanpa input sedikit lebih pendek

IntegerQ@Log2[8]

Benar

IntegerQ@Log2[7]

Salah

ybeltukov
sumber
⌊#⌋==#&@Log2@Input[]
alephalpha
1
@alephalpha Akhirnya menggunakan 24 byte untuk karakter UTF-8. Program 21-byte lainnya adalah Log2@Input[]~Mod~1==0.
LegionMammal978
2

JavaScript, 41 40 karakter

l=Math.log;alert(l(prompt())/l(2)%1==0);

Cara kerjanya: Anda menggunakan logaritma di base 2 menggunakan l(prompt()) / l(2) , dan jika hasil modulo 1 sama dengan nol, maka itu adalah kekuatan 2.

Sebagai contoh: setelah mengambil logaritma 8 di pangkalan 2, Anda dapatkan 3.3 modulo 1sama dengan 0, jadi ini mengembalikan true.

Setelah mengambil logaritma 7 pada basis 2, Anda dapatkan 2.807354922057604. 2.807354922057604 modulo 1sama dengan 0.807354922057604, jadi ini mengembalikan false.

ProgramFOX
sumber
Anda tidak perlu memasukkan input ke nomor; Math.logakan melakukannya : "Masing-masing fungsi objek Matematika berikut menerapkan operator abstrak ToNumber ke setiap argumennya ..."
apsillers
Bukankah itu menderita ketidaktepatan numerik?
Mark Jeronimus
@ MarkJeronimus: Saya sebenarnya tidak tahu. Bisa jadi, tapi saya belum menemukan hasil yang salah.
ProgramFOX
2

JavaScript, 35

Bekerja untuk byte.

alert((+prompt()).toString(2)%9==1)

Versi 46 karakter , Berfungsi untuk angka 16 bit.

x=(+prompt()).toString(2)%99;alert(x==1|x==10)

Trik ini berfungsi dalam sebagian besar bahasa dinamis.

Penjelasan: Konversi angka menjadi basis 2, tafsirkan string itu sebagai basis 10, lakukan modulo 9 untuk mendapatkan jumlah digit, yang harus 1.

salinan
sumber
Bagaimana dengan 0x2ffbasis 2 mana 1111111111?
Peter Taylor
@PeterTaylor Anda benar, sudah diperbaiki
salin
sehingga hal yang nyata Anda lakukan adalah memeriksa modulo 10 tanpa sisa, tapi Anda digunakan 9 mencukur karakter dari kode Anda, +1!
Math chiller
Ini agak curang tetapi metode lain:alert(!(Number.MAX_VALUE%prompt()))
Pluto
2

Perl 5.10+, 13+ 1 = 14 karakter

say!($_&$_/3)

Menggunakan metode yang sama dari utas FWP lama sebagai entri GolfScript saya . Mencetak 1jika input adalah kekuatan dua, dan jalur kosong sebaliknya.

Perlu dijalankan perl -nE; yang n biaya satu char tambahan , untuk total 14 karakter. Atau, inilah versi 18 karakter yang tidak memerlukan n:

say!(($_=<>)&$_/3)
Ilmari Karonen
sumber
2

python 3, 38

print(1==bin(int(input())).count('1'))

python, 32

Namun, kode tidak berfungsi di setiap versi.

print 1==bin(input()).count('1')

Perhatikan bahwa solusinya juga berfungsi untuk 0 (cetak Salah).

Gari BN
sumber
Terpilih karena ini adalah solusi saya juga.
Josh Caswell
1
Bagaimana jika Anda ganti ==dengan &?
SimonT
@SimonT Ini tidak benar. Mengganti '==' dengan '&' akan mencetak 1 untuk setiap angka yang memiliki jumlah ganjil '1' dalam representasi binernya. Periksa misalnya 7 = 111. Ada 3 = 11 yang. Ini akan mengembalikan 11 & 1 = 1.
Gari BN
2

Ruby - 17 karakter (percobaan keempat)

p /.1/!~'%b'%gets

Yang terbaik saat ini adalah gabungan dari jawaban @ steenslag dengan jawaban saya sendiri. Di bawah ini adalah upaya saya sebelumnya.

Ruby - 19 karakter (percobaan ketiga)

p /10*1/!~'%b'%gets

Ruby - 22 karakter (percobaan kedua)

p !('%b'%gets)[/10*1/]

Ruby - 24 karakter (percobaan pertama)

p !!('%b'%gets=~/^10*$/)
OI
sumber
masih ada "+" di program Anda
phuclv
Aku tahu. : - / Saya telah meminta klarifikasi apakah '+' dan '-' dilarang keras, atau apakah mereka dapat digunakan dalam konteks lain selain penambahan dan pengurangan. Saya sedang dalam proses menulis ulang.
OI
Perbaikan luar biasa. Sepertinya ini adalah hasil Ruby terbaik sejauh ini. Saya memperbarui tabel pemimpin dalam teks pertanyaan.
gthacoder
@ gthacoder Baru saja menggabungkan regex steenslag dengan format biner. Jelas tidak bisa mengambil semua kredit.
OI
2

K / Kona ( 24 17)

d:{(+/(2_vs x))~1

Mengembalikan 1 jika benar dan 0 jika salah. Setiap kekuatan 2 memiliki bit tunggal sama dengan 1:

2_vs'_(2^'(!10))
(,1
1 0
1 0 0
1 0 0 0
1 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0)

(ini mencetak semua kekuatan 2 (dari 0 hingga 9) dalam bentuk biner)

Jadi saya meringkas semua komponen dari ekspresi biner xdan melihat apakah itu sama dengan 1; jika ya maka x=2^n, sebaliknya tidak.

... tahu aku bisa membuatnya lebih kecil

Kyle Kanos
sumber
@ gthacoder: Saya membuat kode lebih kecil, harap Anda dapat memperbarui posting utama Anda untuk mencerminkan ini!
Kyle Kanos
Tidakkah ini menggunakan penambahan? Dan bukankah pertanyaannya, err, melarang itu?
zgrep
2

C # (54 karakter)

 Math.Log(int.Parse(Console.ReadLine()),2)%1==0?"Y":"N"
Merin Nakarmi
sumber
Tugas ini dengan jelas menyatakan bahwa input tidak disimpan dalam variabel, itu harus diperoleh dari aliran input dari beberapa jenis (seperti stdin), juga, ini adalah kode-golf , coba persingkat kode Anda sedikit, setidaknya dengan menghapus spasi
mniip
Saya pikir Anda hanya bermaksud Int32, bukan ToInt32...
Chris
Ya ya Terima kasih telah menunjukkan Chris. Sebelumnya itu Convert.ToInt32 dan saya ingin mengubahnya ke Int32.Parse untuk mempersingkatnya. : D
Merin Nakarmi
2
gunakan intalih-alih Int32untuk 2 karakter lebih sedikit.
Rik
2

Rebmu (9 karakter)

z?MOl2A 1

Uji

>> rebmu/args [z?MOl2A 1] 7
== false

>> rebmu/args [z?MOl2A 1] 8 
== true

>> rebmu/args [z?MOl2A 1] 9 
== false

Rebmu adalah dialek bahasa Rebol yang terbatas. Kode dasarnya adalah:

z? mo l2 a 1  ; zero? mod log-2 input 1

Alternatif

14 karakter — Rebmu tidak memiliki bitwise 'bubur' DAN ~

z?AND~aTIddA 3

Dalam Rebol:

zero? a & to-integer a / 3
rgchris
sumber
1

GTB , 46 byte

2→P`N[@N=Pg;1P^2→P@P>1E90g;2]l;2~"NO"&l;1"YES"
Timtech
sumber
1

Python, 35

print bin(input()).strip('0')=='b1'

Tidak hanya menggunakan operasi +/-, tetapi operasi matematika selain mengonversi ke bentuk biner.

Hal-hal lain (menarik, tetapi tidak untuk kompetisi):

Saya juga memiliki versi regexp (61) :

import re;print re.match(r'^0b10+$',bin(input())) is not None

(Menyukai idenya, tetapi fungsi impor dan cocok membuatnya terlalu lama)

Dan versi operasi bitwise yang bagus, tetapi membosankan (31) :

x=input();print x and not x&~-x

(ya, ini lebih pendek, tetapi ia menggunakan ~ -x untuk decrement yang comtains - operasi)

Ivan Anishchuk
sumber
jawaban boothby menggunakan ide yang sama dengan yang pertama, tetapi lebih pendek :(
Ivan Anishchuk
1

Python 2.7 ( 30 29 39 37)

EDIT: Diperbarui karena persyaratan input pengguna;

a=input()
while a>1:a/=2.
print a==1

Brute force, coba bagi hingga = 1 (berhasil) atau <1 (gagal)

Joachim Isaksson
sumber
1
not a%2dapat ditulis sebagai a%2==0. Memang, ini akan lebih lama dalam banyak bahasa, tetapi tidak Python.
Konrad Borowski
@xfix Terima kasih, diuji dan diperbarui.
Joachim Isaksson
1
atau bahkan lebih baik a%2<1,.
Stanby
Anda memiliki ruang setelah 2.Menghapus yang akan menghemat satu byte!
Keerthana Prabhakaran
1

Python (33)

print int(bin(input())[3:]or 0)<1
Blender
sumber
int(bin(input()*2)[3:])<1juga bekerja dari shell python dengan hanya 25 karakter.
gmatht
1

Ruby, 33 , 28 , 25

p /.1/!~gets.to_i.to_s(2)
steenslag
sumber
1

APL (12 untuk 0/1, 27 untuk ya / tidak)

≠/A=2*0,ιA←⍞ 

atau, jika kita harus menampilkan teks:

3↑(3x≠/A=2*0,ιA←⍞)↓'YESNO '

Baca dalam A. Bentuk vektor 0..A, lalu vektor 2 0 ..2 A (ya, itu jauh lebih dari yang diperlukan), kemudian vektor yang membandingkan A dengan masing-masing (menghasilkan vektor 0 dan paling banyak satu 1), lalu xor itu (tidak ada xor operator di APL, tetapi ≠ yang diterapkan pada boolean akan bertindak sebagai satu.) Kita sekarang memiliki 0 atau 1.

Untuk mendapatkan YA atau TIDAK: kalikan 0 atau 1 dengan 3, jatuhkan jumlah karakter ini dari 'YESNO', lalu ambil 3 karakter pertama dari ini.

Tandai Plotnick
sumber
1

C, 65 byte

main(k){scanf("%i",&k);while(k&&!(k%2))k/=2;puts(k==1?"T":"F");}
vershov
sumber
Anda dapat memotong 5 karakter dengan menggunakan main(k){..., bergantung pada intpengetikan tersirat . Mungkin UB, tapi ini golf kode. TIDAK PERNAH menggunakan sesuatu seperti itu dalam produksi, tentu saja.
Kevin
1

Haskell ( 52 50)

k n=elem n$map(2^)[1..n]
main=interact$show.k.read
Zeta
sumber