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 atom-kode-golf . 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.

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
}

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.

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.

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 :-)

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

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

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

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

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.

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)

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)