Apakah angka ini kekuatan tepat -2: Mode Keras (Sangat)

26

Ini adalah versi dari tantangan terakhir. Apakah angka ini bilangan bulat dari -2? dengan serangkaian kriteria yang berbeda yang dirancang untuk menyoroti sifat menarik dari masalah dan membuat tantangan lebih sulit. Saya menaruh beberapa pertimbangan di sini .

Tantangan seperti yang dinyatakan oleh Toby dalam pertanyaan terkait, adalah:

Ada cara pintar untuk menentukan apakah integer adalah kekuatan tepat dari 2. Itu bukan lagi masalah yang menarik, jadi mari kita tentukan apakah integer yang diberikan adalah kekuatan yang tepat dari -2 . Sebagai contoh:

-2 => yes: (-2)¹
-1 => no
0 => no
1 => yes: (-2)⁰
2 => no
3 => no
4 => yes: (-2)²

Aturan:

  • Integer adalah 64 bit, ditandatangani, komplemen dua. Ini adalah satu - satunya tipe data yang dapat Anda gunakan.
  • Anda hanya dapat menggunakan operasi berikut. Masing-masing dihitung sebagai satu operasi.
    • n << k, n >> k: Pergeseran kiri / kanan nmenurut kbit. Bit tanda diperpanjang di shift kanan.
    • n >>> k: Bergeser ke kanan tetapi tidak memperpanjang bit tanda. 0 bergeser masuk.
    • a & b, a | b, a ^ b: Bitwise AND, OR, XOR.
    • a + b, a - b, a * b: Menambah, mengurangi, mengalikan.
    • ~b: Bitwise terbalik
    • -b: Negasi komplemen dua.
    • a / b, a % b: Membagi (hasil bagi bilangan bulat, putaran ke 0), dan modulo.
      • Modulo angka negatif menggunakan aturan yang ditentukan dalam C99 : (a/b) * b + a%bharus sama a. Begitu 5 % -3juga 2, dan -5 % 3adalah -2:
      • 5 / 3is 1, 5 % 3is 2, karena 1 * 3 + 2 = 5.
      • -5 / 3is -1, -5 % 3is -2, -1 -1 3 + -2 = -5.
      • 5 / -3is -1, 5 % -3is 2, -1 -1 -3 + 2 = 5.
      • -5 / -3is 1, -5 % -3is -2, sebagai 1 * -3 + -2 = -5.
      • Perhatikan bahwa //operator pembagian lantai Python tidak memenuhi properti pembagian "putaran menuju 0" di sini, dan %operator Python juga tidak memenuhi persyaratan.
    • Tugas tidak dihitung sebagai operasi. Seperti dalam C, tugas mengevaluasi ke nilai sisi kiri setelah penugasan: a = (b = a + 5)set bke a + 5, lalu set ake b, dan dihitung sebagai satu operasi.
    • Penugasan majemuk dapat digunakan a += bsarana a = a + bdan dihitung sebagai satu operasi.
  • Anda dapat menggunakan konstanta integer, mereka tidak dihitung sebagai apa pun.
  • Tanda kurung untuk menentukan urutan operasi dapat diterima.
  • Anda dapat mendeklarasikan fungsi. Deklarasi fungsi bisa dalam gaya apa pun yang nyaman untuk Anda tetapi perhatikan bahwa integer 64 bit adalah satu - satunya tipe data yang valid. Deklarasi fungsi tidak dihitung sebagai operasi, tetapi sebuah fungsi panggilan dianggap sebagai satu. Juga, harus jelas: Fungsi dapat berisi beberapa returnpernyataan dan returns dari titik mana pun diizinkan. Itu returnsendiri tidak dihitung sebagai operasi.
  • Anda dapat mendeklarasikan variabel tanpa biaya.
  • Anda dapat menggunakan whileloop, tetapi Anda tidak dapat menggunakan ifatau for. Operator yang digunakan dalam whilekondisi tersebut menghitung skor Anda. whileloop dijalankan selama kondisinya mengevaluasi ke a tidak nol ("benar" 0 dalam bahasa yang memiliki konsep ini bukan hasil yang valid). Sejak awal-return diperbolehkan, Anda diijinkan untuk menggunakan breakjuga
  • Overflow / underflow diizinkan dan tidak ada penjepitan nilai yang akan dilakukan. Itu diperlakukan seolah-olah operasi benar-benar terjadi dengan benar dan kemudian dipotong menjadi 64 bit.

Kriteria Penilaian / Kemenangan:

Kode Anda harus menghasilkan nilai yang bukan nol jika inputnya adalah kekuatan -2, dan nol sebaliknya.

Ini adalah . Skor Anda adalah jumlah total operasi yang ada dalam kode Anda (sebagaimana didefinisikan di atas), bukan jumlah total operasi yang dijalankan pada saat run-time. Kode berikut:

function example (a, b) {
    return a + ~b;
}

function ispowerofnegtwo (input) {
    y = example(input, 9);
    y = example(y, 42);
    y = example(y, 98);
    return y;
}

Berisi 5 operasi: dua di fungsi, dan tiga panggilan fungsi.

Tidak masalah bagaimana Anda mempresentasikan hasil Anda, gunakan apa pun yang nyaman dalam bahasa Anda, baik itu akhirnya menyimpan hasil dalam variabel, mengembalikannya dari suatu fungsi, atau apa pun.

Pemenangnya adalah pos yang terbukti benar (berikan bukti kasual atau formal jika perlu) dan memiliki skor terendah seperti dijelaskan di atas.

Bonus Tantangan Mode Sangat Keras!

Untuk kesempatan memenangkan apa pun kecuali kemampuan potensial untuk mengesankan orang di pesta, kirimkan jawaban tanpa menggunakan whileloop! Jika cukup dari ini diajukan saya bahkan dapat mempertimbangkan membagi kelompok yang menang menjadi dua kategori (dengan dan tanpa loop).


Catatan: Jika Anda ingin memberikan solusi dalam bahasa yang hanya mendukung bilangan bulat 32-bit, Anda dapat melakukannya, asalkan Anda cukup membenarkan bahwa bilangan bulat 64-bit akan tetap benar untuk penjelasan.

Juga: Beberapa fitur bahasa tertentu dapat diizinkan tanpa biaya jika mereka tidak menghindari aturan tetapi diperlukan untuk memaksa bahasa Anda ke dalam berperilaku sesuai dengan aturan di atas . Sebagai contoh (dibuat-buat), saya akan mengizinkan gratis tidak sama dengan 0 perbandingan dalam whileloop, ketika diterapkan pada kondisi secara keseluruhan, sebagai solusi untuk bahasa yang memiliki "benar" 0's. Upaya yang jelas untuk mengambil keuntungan dari hal-hal semacam ini tidak diperbolehkan - mis. Konsep nilai "benar" 0 atau "tidak terdefinisi" tidak ada dalam aturan di atas, dan karenanya tidak dapat diandalkan.

Jason C
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis
@ hvd Jika Anda membaca ini: Anda harus benar-benar membatalkan penghapusan jawaban Anda! Dengan asumsi itu benar, bahkan tanpa m ^= s itu masih mengesankan, dan saya pikir itu akan benar-benar baik untuk membuat substitusi untuk memperbaikinya lebih.
Jason C
Bagaimana masuk akal untuk mengizinkan whiledan breaktetapi tidak if? if (x) { ... }setara dengan while (x) { ... break; }.
R ..
@R .. Itu tidak masuk akal 100% ( breakdan pengembalian awal adalah bagian yang disesalkan) dan merupakan cerita panjang dan pelajaran yang dipetik dalam aturan untuk tantangan di masa depan. Selalu ada versi "bonus"! :)
Jason C
1
Mengapa ifdan fortidak diizinkan? int x=condition; while (x) { ... x=0; }gratis, hanya lebih banyak kode. Sama halnya dengan c-style for.
Qwertiy

Jawaban:

35

C ++, 15 operasi

Saya tidak tahu mengapa whileloop diizinkan karena mereka menghancurkan seluruh tantangan. Inilah jawaban tanpa:

int64_t is_negpow2(int64_t n) {
    int64_t neg = uint64_t(n) >> 63; // n >>> 63
    n = (n ^ -neg) + neg; // if (n < 0) n = -n;
    int64_t evenbits = n & int64_t(0xaaaaaaaaaaaaaaaaull >> neg);
    int64_t n1 = n - 1;
    int64_t pot = n & n1;
    int64_t r = pot | (n1 >> 63) | evenbits;
    return ~((r | -r) >> 63); // !r
}
orlp
sumber
Mengapa whileloop menghancurkan seluruh tantangan ?
Tn. Xcoder
10
@ Mr.Xcoder Karena tantangannya adalah tentang melakukannya dengan operasi bitwise sederhana dan whilebertentangan dengan itu dalam segala hal.
orlp
Maksud saya, kecuali jika Anda membuat loop sementara gandakan jumlah operasi kali jumlah kali dieksekusi dalam loop untuk statis natau sesuatu.
Magic Gurita Guci
Saya berkomentar tentang ini di sini .
Jason C
@ JasonC Itu karena saya seharusnya menggunakan shift yang tepat tanpa tanda bit. Saya mengedit kode (menggunakan uint64_tkarena itulah satu-satunya cara untuk mendapatkan giliran yang tepat tanpa ekstensi tanda.)
orlp
25

Operasi Python 2 , 3

def f(n):
 while n>>1:
  while n&1:return 0
  n=n/-2
 return n

Cobalah online!

Operasi yang >>, &, /.

Idenya adalah untuk berulang kali membaginya dengan -2. Powers -2 rantai turun ke 1: -8 -> 4 -> -2 -> 1. Jika kita menekan a 1, terima. Jika kami menekan nomor ganjil sebelum memukul 1, tolak. Kita juga perlu menolak 0, yang selamanya berlaku untuk dirinya sendiri.

The while n>>1:loop sampai nadalah 0 atau 1. Ketika loop istirahat, nitu sendiri dikembalikan, dan 1merupakan output truthy dan 0satu Falsey. Di dalam loop, kami menolak berulang kali menerapkan n -> n/-2dan menolak yang anehn .

Karena /hanya digunakan pada nilai yang sama, perilaku pembulatannya tidak pernah berlaku. Jadi, tidak masalah bahwa putaran Python berbeda dari spec.

Tidak
sumber
Bagus. Logika yang cerdas dalam algoritma dan kerja yang baik menggabungkan kondisi menjadi operasi bit. Juga, dapat mengkonfirmasi, implementasi bekerja dalam C.
Jason C
Kenapa while n&1bukannya if n&1?
Mark Ransom
2
@MarkRansom Tantangannya tidak memungkinkan if.
xnor
Aha, merindukan itu. Substitusi yang sangat pintar.
Mark Ransom
1
@EvSunWoodard Penilaian adalah jumlah operator dalam kode, bukan jumlah panggilan kepada mereka selama eksekusi, yang tergantung pada input: "Ini adalah kode atom-golf. Skor Anda adalah jumlah total operasi yang ada dalam kode Anda . "
xnor
11

Karat, 14 12 operasi (tanpa loop)

Memerlukan pengoptimalan ( -O) atau -C overflow-checks=nountuk mengaktifkan pengurangan yang berlebihan alih-alih panik.

fn is_power_of_negative_2(input: i64) -> i64 {
    let sign = input >> 63;
    // 1 op
    let abs_input = (input ^ sign) - sign;
    // 2 ops
    let bad_power_of_two = sign ^ -0x5555_5555_5555_5556; // == 0xaaaa_aaaa_aaaa_aaaa
    // 1 op
    let is_not_power_of_n2 = abs_input & ((abs_input - 1) | bad_power_of_two);
    // 3 ops 
    let is_not_power_of_n2 = (is_not_power_of_n2 | -is_not_power_of_n2) >> 63;
    // 3 ops 
    input & !is_not_power_of_n2
    // 2 ops
}

(Untuk memperjelas: !xadalah bitwise-tidak di sini, tidak logis-TIDAK)

Kasus uji:

#[test]
fn test_is_power_of_negative_2() {
    let mut value = 1;
    for _ in 0 .. 64 {
        assert_ne!(0, is_power_of_negative_2(value), "wrong: {} should return nonzero", value);
        value *= -2;
    }
}

#[test]
fn test_not_power_of_negative_2() {
    for i in &[0, -1, 2, 3, -3, -4, 5, -5, 6, -6, 7, -7, 8, 1<<61, -1<<62, 2554790084739629493, -4676986601000636537] {
        assert_eq!(0, is_power_of_negative_2(*i), "wrong: {} should return zero", i);
    }
}

Cobalah online!


Idenya adalah untuk memeriksa apakah | x | adalah kekuatan 2 (menggunakan (y & (y - 1)) == 0seperti biasa). Jika x adalah kekuatan 2, maka kami selanjutnya memeriksa (1) kapan x >= 0, itu juga harus menjadi kekuatan genap 2, atau (2) kapan x < 0, itu harus menjadi kekuatan aneh dari 2. Kami memeriksa ini dengan &-ing the " bad_power_of_two"mask 0x… aaaa when x >= 0(menghasilkan 0 hanya ketika itu adalah kekuatan genap), atau 0x ... 5555 kapan x < 0.

kennytm
sumber
Saya mencuri ~((r | -r) >> 63)trik Anda untuk menyelesaikan memperbaiki jawaban saya.
orlp
6

Haskell, 2 3 operasi

import Data.Bits (.&.)

f 0 = False
f 1 = True
f n | n .&. 1 == 0 = f (n `div` -2)
f n | otherwise    = False

Menentukan fungsi rekursif f(n). Operasi yang digunakan adalah pemanggilan fungsi ( f), pembagian ( div), dan bitwise dan ( .&.).

Tidak mengandung loop karena fakta bahwa Haskell tidak memiliki pernyataan loop :-)

Oportunis
sumber
4
Mengapa saya tidak terkejut bahwa solusi Haskell tanpa menggunakan loop disediakan oleh seseorang bernama "Opportunist?" =)
Cort Ammon - Reinstate Monica
1
Saya sangat ragu-ragu tentang f 0, f 1, f n ...di sini karena mereka pada dasarnya if's menyamar, meskipun sekali lagi, saya membiarkan while+ breakdan awal returns, sehingga tampaknya adil. Meskipun tampaknya memanfaatkan aturan saya yang secara tidak sengaja dibiarkan terbuka untuk interpretasi, itu adalah solusi yang bagus.
Jason C
3
Khususnya |s terutama di udara. Yang mengatakan, ini memang melanggar satu aturan tertentu dengan cara yang tidak terlalu diperdebatkan: Perbandingan ==tidak diperbolehkan. Catatan, bagaimanapun, bahwa jika interpretasi saya kode ini benar, penggunaan boolean sini tidak muncul diterima sebagai substitusi nilai integer sewenang-wenang di tempat mereka tidak muncul untuk mengubah hasil, dan mereka lebih dari bentuk presentasi akhir.
Jason C
@ JasonC Saya hanya menggunakan ==karena tidak ada cara lain untuk melemparkan dari Intke Boolatau "Kebenaran" di Haskell. Apakah pencocokan pola dan penjaga melanggar aturan "tidak ada if" adalah panggilan Anda ;-)
Opportunis
18
Dengan pencocokan pola, Anda bisa membuat hardcode hasil untuk semua integer 64-bit menggunakan 0 operasi.
xnor
5

Python 3, Operasi 10 atau 11 9

def g(x):
 while x:
  while 1 - (1 + ~int(x - -2 * int(float(x) / -2))) & 1: x /= -2
  break
 while int(1-x):
     return 0
 return 5  # or any other value

Pengembalian 5untuk kekuatan -2, 0jika tidak

Tuan Xcoder
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis
5

C, 5 operasi

long long f(long long x){
    x=x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    while(x){
        while(x&(x-1))
            return 0;
        return 1;
    }
    return 0;
}

C, 10 operasi, tanpa loop

long long f(long long x){
    x = x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    long long t = x & (x-1);
    return (((t-1) & ~t) >> 63) * x;
}

C, 1 operasi

long long f(long long x){
    long long a0=1, a1=-2, a2=4, a3=-8, a4=16, a5=-32, a6=64, a7=-128, a8=256, a9=-512, a10=1024, a11=-2048, a12=4096, a13=-8192, a14=16384, a15=-32768, a16=65536, a17=-131072, a18=262144, a19=-524288, a20=1048576, a21=-2097152, a22=4194304, a23=-8388608, a24=16777216, a25=-33554432, a26=67108864, a27=-134217728, a28=268435456, a29=-536870912, a30=1073741824, a31=-2147483648, a32=4294967296, a33=-8589934592, a34=17179869184, a35=-34359738368, a36=68719476736, a37=-137438953472, a38=274877906944, a39=-549755813888, a40=1099511627776, a41=-2199023255552, a42=4398046511104, a43=-8796093022208, a44=17592186044416, a45=-35184372088832, a46=70368744177664, a47=-140737488355328, a48=281474976710656, a49=-562949953421312, a50=1125899906842624, a51=-2251799813685248, a52=4503599627370496, a53=-9007199254740992, a54=18014398509481984, a55=-36028797018963968, a56=72057594037927936, a57=-144115188075855872, a58=288230376151711744, a59=-576460752303423488, a60=1152921504606846976, a61=-2305843009213693952, a62=4611686018427387904, a63=-9223372036854775807-1, a64=0;
    while(a0){
        long long t = x ^ a0;
        long long f = 1;
        while(t){
            f = 0;
            t = 0;
        }
        while(f)
            return 1;
        a0=a1; a1=a2; a2=a3; a3=a4; a4=a5; a5=a6; a6=a7; a7=a8; a8=a9; a9=a10; a10=a11; a11=a12; a12=a13; a13=a14; a14=a15; a15=a16; a16=a17; a17=a18; a18=a19; a19=a20; a20=a21; a21=a22; a22=a23; a23=a24; a24=a25; a25=a26; a26=a27; a27=a28; a28=a29; a29=a30; a30=a31; a31=a32; a32=a33; a33=a34; a34=a35; a35=a36; a36=a37; a37=a38; a38=a39; a39=a40; a40=a41; a41=a42; a42=a43; a43=a44; a44=a45; a45=a46; a46=a47; a47=a48; a48=a49; a49=a50; a50=a51; a51=a52; a52=a53; a53=a54; a54=a55; a55=a56; a56=a57; a57=a58; a58=a59; a59=a60; a60=a61; a61=a62; a62=a63; a63=a64;
    }
    return 0;
}
jimmy23013
sumber
2
Ya ampun, yang terakhir itu jahat. Bagus.
Jason C
4

Majelis, 1 operasi

.data

    .space 1         , 1 # (-2)^31
    .space 1610612735, 0
    .space 1         , 1 # (-2)^29
    .space 402653183 , 0
    .space 1         , 1 # (-2)^27
    .space 100663295 , 0
    .space 1         , 1 # (-2)^25
    .space 25165823  , 0
    .space 1         , 1 # (-2)^23
    .space 6291455   , 0
    .space 1         , 1 # (-2)^21
    .space 1572863   , 0
    .space 1         , 1 # (-2)^19
    .space 393215    , 0
    .space 1         , 1 # (-2)^17
    .space 98303     , 0
    .space 1         , 1 # (-2)^15
    .space 24575     , 0
    .space 1         , 1 # (-2)^13
    .space 6143      , 0
    .space 1         , 1 # (-2)^11
    .space 1535      , 0
    .space 1         , 1 # (-2)^9
    .space 383       , 0
    .space 1         , 1 # (-2)^7
    .space 95        , 0
    .space 1         , 1 # (-2)^5 = -32
    .space 23        , 0
    .space 1         , 1 # (-2)^3 = -8
    .space 5         , 0
    .space 1         , 1 # (-2)^1 = -2
    .space 1         , 0
dataZero:
    .space 1         , 0
    .space 1         , 1 # (-2)^0 = 1
    .space 2         , 0
    .space 1         , 1 # (-2)^2 = 4
    .space 11        , 0
    .space 1         , 1 # (-2)^4 = 16
    .space 47        , 0
    .space 1         , 1 # (-2)^6 = 64
    .space 191       , 0
    .space 1         , 1 # (-2)^8
    .space 767       , 0
    .space 1         , 1 # (-2)^10
    .space 3071      , 0
    .space 1         , 1 # (-2)^12
    .space 12287     , 0
    .space 1         , 1 # (-2)^14
    .space 49151     , 0
    .space 1         , 1 # (-2)^16
    .space 196607    , 0
    .space 1         , 1 # (-2)^18
    .space 786431    , 0
    .space 1         , 1 # (-2)^20
    .space 3145727   , 0
    .space 1         , 1 # (-2)^22
    .space 12582911  , 0
    .space 1         , 1 # (-2)^24
    .space 50331647  , 0
    .space 1         , 1 # (-2)^26
    .space 201326591 , 0
    .space 1         , 1 # (-2)^28
    .space 805306367 , 0
    .space 1         , 1 # (-2)^30
    .space 3221225471, 0
    .space 1         , 1 # (-2)^32

.globl isPowNeg2
isPowNeg2:
    movl dataZero(%edi), %eax
    ret

Menggunakan tabel pencarian besar untuk menemukan apakah angka itu kekuatan 2. Anda dapat memperluas ini menjadi 64 bit, tetapi menemukan komputer untuk menyimpan banyak data yang tersisa sebagai latihan untuk pembaca :-P

Oportunis
sumber
1
Pengindeksan tabel bukan salah satu dari operasi yang diizinkan.
R ..
1
Juga ini jelas tidak dapat diperpanjang hingga 64 bit. :-)
R ..
Memang, pengindeksan tabel tidak dimaksudkan untuk diizinkan berdasarkan aturan saat ini. Saya menetapkan "Anda dapat mendeklarasikan variabel" dan "Anda dapat menentukan literal bilangan bulat" dengan maksud skalar, dan secara semantik ini adalah sebuah array (dan secara pedantis saya tidak mengizinkan tipe array atau saya tidak mengizinkan pengindeksan jenis apa pun sebagai salah satu dari operasi meskipun Anda bisa menyebutnya "tambahan" dalam konteks assembler), tetapi menjadi opportunis bahwa Anda ... :)
Jason C
3

C, 31 operasi

Demo Langsung

Ide saya sederhana, jika itu kekuatan dua, maka jika log-nya genap maka harus positif, kalau tidak log-nya harus aneh.

int isPositive(int x) // 6
{
    return ((~x & (~x + 1)) >> 31) & 1;
}

int isPowerOfTwo(int x) // 5
{
    return isPositive(x) & ~(x & (x-1));
}

int log2(int x) // 3
{
    int i = (-1);

    while(isPositive(x))
    {
        i  += 1;
        x >>= 1;
    }

    return i;
}

int isPowerOfNegativeTwo(int x) // 17
{
    return (  isPositive(x) &  isPowerOfTwo(x) & ~(log2(x) % 2) )
         | ( ~isPositive(x) & isPowerOfTwo(-x) & (log2(-x) % 2) );
}
Khaled.K
sumber
1
Anda sebenarnya melakukan lebih baik daripada yang Anda pikirkan. Panggilan fungsi hanya dihitung sebagai 1, bukan sebagai jumlah operator dalam fungsi. Jadi, jika saya menghitung dengan benar (periksa dua kali) Anda punya sesuatu seperti 6 untuk isPositive + 5 untuk isPowerOfTwo + 3 untuk logPower + 17 untuk isPowerOfNegativeTwo = 31.
Jason C
1

C, 7 operasi

int64_t is_power_of_neg2(int64_t n)
{
    int64_t x = n&-n;
    while (x^n) {
        while (x^-n)
            return 0;
        return x & 0xaaaaaaaaaaaaaaaa;
    }
    return x & 0x5555555555555555;
}

atau:

C, 13 operasi tanpa kondisi loop-as-conditional

int64_t is_power_of_neg2(int64_t n)
{
    int64_t s = ~(n>>63);
    int64_t a = ((n/2)^s)-s;
    int64_t x = n&-(uint64_t)n; // Cast to define - on INT64_MIN.
    return ~(a/x >> 63) & x & (0xaaaaaaaaaaaaaaaa^s);
}

Penjelasan:

  • n&-n menghasilkan bit set terendah n .
  • aadalah nilai absolut dinegasikan n/2, tentu negatif karena/2 menghalangi limpahan negasi.
  • a/xadalah nol hanya jika akekuatan tepat dua; jika tidak, setidaknya satu bit lainnya diatur, dan itu lebih tinggi darix , bit terendah, menghasilkan hasil negatif.
  • ~(a/x >> 63)kemudian menghasilkan bitmask itu semua-yang jika natau -nadalah kekuatan dua, jika tidak semua-nol.
  • ^sditerapkan ke topeng untuk memeriksa tanda nuntuk melihat apakah itu kekuatan -2.
R ..
sumber
1

PHP, 3 operasi

ternary dan ifdilarang; jadi mari kita menyalahgunakan while:

function f($n)
{
    while ($n>>1)               # 1. ">>1"
    {
        while ($n&1)            # 2. "&1"
            return 0;
        return f($n/-2|0);      # 3. "/-2" ("|0" to turn it into integer division)
    }
    return $n;
}
  1. $n>>1: jika angka 0 atau 1, kembalikan angka
  2. $n&1: jika angka ganjil, kembalikan 0
  3. Tes lain $n/-2(+ cor ke int)
Titus
sumber
0

JavaScript ES6, 7 operasi

x=>{
  while(x&1^1&x/x){
    x/=-2;x=x|0
  }
  while(x&0xfffffffe)x-=x
  return x
}

Cobalah online!

Penjelasan

while(x&1^1&x/x)

Sementara x! = 0 dan x% 2 == 0 4 ops
x / x sama dengan 1 selama x tidak 0 (0/0 memberikan NaN yang dievaluasi salah)
& bitwise dan
x & 1 ^ 1 sama dengan 1 jika x genap (x dan 1) xor 1

x/=-2;x=x|0

Ini adalah bentuk pembagian yang didefinisikan oleh pertanyaan 1 op

while(x&0xfffffffe)  

Sedangkan x! = 1 dan x! = 0 1 op
Kondisi yang diperlukan untuk keluar ketika x == 0 atau x == 1 karena keduanya adalah nilai balik dan memasukkan infinite loop tidak akan produktif. Secara teoritis ini dapat diperpanjang untuk nilai yang lebih besar dengan meningkatkan angka heksadesimal. Saat ini berfungsi hingga ± 2 ^ 32-1

x-=x

Set x ke 0 1 op
Sementara saya bisa menggunakan kembali 0 untuk 0 ops, saya merasa bahwa loop sementara yang rusak oleh pernyataan lain terasa terlalu banyak seperti curang.

return x

mengembalikan x (1 jika kekuatan -2, 0 sebaliknya)

fəˈnɛtɪk
sumber