To jest wersja ostatniego wyzwania. Czy ta liczba jest potęgą całkowitą -2? z innym zestawem kryteriów zaprojektowanych w celu podkreślenia interesującej natury problemu i utrudnienia wyzwania. Zastanowiłem się nad tym tutaj .

Wyzwanie, jak wspaniale stwierdził Toby w powiązanym pytaniu, to:

Istnieją sprytne sposoby określania, czy liczba całkowita jest dokładną potęgą 2. To już nie jest interesujący problem, więc ustalmy, czy dana liczba całkowita jest dokładną potęgą -2 . Na przykład:

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

Zasady:

• Liczba całkowita to 64 bity, ze znakiem, uzupełnienie dwóch. To jedyny typ danych, z którym możesz pracować.
• Możesz używać tylko następujących operacji. Każda z nich liczy się jako jedna operacja.
  • n << k, n >> k: Przesunięcie w lewo / prawo no kbity. Bit znaku jest przedłużany przy przesunięciu w prawo.
  • n >>> k: Przesunięcie w prawo, ale nie przedłużaj bitu znakowego. Zera są przesunięte.
  • a & b, a | b, a ^ b: Bitowe AND, OR, XOR.
  • a + b, a - b, a * b: Dodawanie, odejmowanie, mnożenie.
  • ~b: Odwrócenie bitowe.
  • -b: Negacja dopełniacza Two.
  • a / b, a % b: Podziel (iloraz liczby całkowitej, zaokrągla w kierunku 0) i modulo.
    • Modulo liczb ujemnych wykorzystuje reguły określone w C99 : (a/b) * b + a%bpowinno być równe a. Tak 5 % -3jest 2i -5 % 3jest -2:
    • 5 / 3jest 1, 5 % 3jest 2, ponieważ 1 * 3 + 2 = 5.
    • -5 / 3jest -1, -5 % 3jest -2, ponieważ -1 * 3 + -2 = -5.
    • 5 / -3jest -1, 5 % -3jest 2, ponieważ -1 * -3 + 2 = 5.
    • -5 / -3jest 1, -5 % -3jest -2, ponieważ 1 * -3 + -2 = -5.
    • Zauważ, że //operator podziału podłogi w Pythonie nie spełnia tutaj właściwości podziału zaokrąglenie do zera, a %operator języka Python również nie spełnia wymagań.
  • Przydziały nie są liczone jako operacja. Podobnie jak w C, przypisania oceniają wartość po lewej stronie po przypisaniu: a = (b = a + 5)ustawia się bna a + 5, następnie ustawia się ana bi liczy się jako jedna operacja.
  • Przypisania złożone mogą być użyte jako a += bśrodki a = a + bi można je liczyć jako jedną operację.
• Możesz użyć stałych całkowitych, nie liczą się jako nic.
• Dopuszczalne są nawiasy określające kolejność operacji.
• Możesz zadeklarować funkcje. Deklaracje funkcji mogą mieć dowolny dogodny styl, ale należy pamiętać, że 64-bitowe liczby całkowite są jedynym prawidłowym typem danych. Deklaracje funkcji nie liczą się jako operacje, ale wywołanie funkcji liczy się jako jedna. Dla jasności: funkcje mogą zawierać wiele returninstrukcji returnis z dowolnego punktu są dozwolone. returnSama nie liczy się jako operacji.
• Możesz zadeklarować zmienne bez żadnych kosztów.
• Możesz używać whilepętli, ale nie możesz używać iflub for. Operatory użyte w tym whilestanie liczą się do twojego wyniku. whilepętle działają, dopóki ich stan nie jest zerowy („prawda” 0 w językach, które mają tę koncepcję, nie jest poprawnym wynikiem). Od wczesnego powrotu jest dozwolone, są dopuszczone do wykorzystania break, jak również
• Przepełnienie / niedopełnienie jest dozwolone i nie zostanie wykonane żadne ustalanie wartości. Traktuje się to tak, jakby operacja faktycznie przebiegła poprawnie, a następnie została obcięta do 64 bitów.

Kryteria punktacji / wygranej:

Twój kod musi generować wartość niezerową, jeśli dane wejściowe mają potęgę -2, a w przeciwnym razie zero.

To jest golf atomowy . Twój wynik to całkowita liczba operacji obecnych w kodzie (jak zdefiniowano powyżej), a nie całkowita liczba operacji wykonanych w czasie wykonywania. Następujący kod:

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

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

Zawiera 5 operacji: dwie w funkcji i trzy wywołania funkcji.

Nie ma znaczenia, w jaki sposób prezentujesz swój wynik, używasz wszystkiego, co jest wygodne w twoim języku, czy to ostatecznie przechowuje wynik w zmiennej, zwraca go z funkcji, czy cokolwiek innego.

Zwycięzcą jest post, który jest w sposób oczywisty poprawny (w razie potrzeby należy przedstawić zwykły lub formalny dowód) i ma najniższą ocenę, jak opisano powyżej.

Bonus Very Hard Mode wyzwanie!

Aby uzyskać szansę na wygranie absolutnie nic oprócz potencjalnej zdolności do zaimponowania ludziom na przyjęciach, prześlij odpowiedź bez użycia whilepętli! Jeśli zostanie dostarczonych wystarczająca ich liczba, mogę nawet rozważyć podzielenie zwycięskich grup na dwie kategorie (z pętlami i bez).

Uwaga: jeśli chcesz podać rozwiązanie w języku, który obsługuje tylko 32-bitowe liczby całkowite, możesz to zrobić, pod warunkiem, że wystarczająco uzasadnisz, że będzie to nadal poprawne dla 64-bitowych liczb całkowitych w wyjaśnieniu.

Ponadto: Niektóre funkcje specyficzne dla języka mogą być dozwolone bez ponoszenia kosztów, jeśli nie omijają zasad, ale są niezbędne do zmuszenia języka do zachowywania się zgodnie z powyższymi zasadami . Na przykład (wymyślony), zezwalam na bezpłatne porównanie z równością 0 w whilepętlach, gdy zostanie zastosowane do warunku jako całości, jako obejście dla języka, który ma „prawdziwe” zera. Wyraźne próby wykorzystania tego rodzaju rzeczy są niedozwolone - np. Koncepcja „prawdy” 0 lub „niezdefiniowanych” wartości nie istnieje w powyższym zestawie reguł, więc nie można na nich polegać.

C ++, 15 operacji

Nie mam pojęcia, dlaczego whilepętle są dozwolone, ponieważ niszczą całe wyzwanie. Oto odpowiedź bez żadnej:

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
}

Operacje w języku Python 2 , 3

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

Wypróbuj online!

Operacje są >>, &, /.

Chodzi o wielokrotne dzielenie przez -2. Uprawnienia -2 łańcucha do 1: -8 -> 4 -> -2 -> 1. Jeśli trafimy a 1, zaakceptuj. Jeśli trafimy nieparzystą liczbę przed uderzeniem 1, odrzuć. Musimy także odrzucić 0, co na zawsze idzie w parze.

while n>>1:Pętli aż nwynosi 0 lub 1. W przypadku przerwy w pętli, nzwracana jest, i 1ma wyjście Truthy i 0jeden Falsey. Wewnątrz pętli wielokrotnie odrzucamy stosowanie n -> n/-2i odrzucamy wszelkie nieparzyste n.

Ponieważ /zawsze stosuje się go w parzystych wartościach, jego zaokrąglanie nigdy nie wchodzi w grę. Więc nie ma znaczenia, że ​​Python zaokrągla inaczej niż w specyfikacji.

Rdza, 14 12 operacji (bez pętli)

Wymaga optymalizacji ( -O) lub -C overflow-checks=nowłączenia przepełnienia odejmowania zamiast paniki.

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
}

(Aby wyjaśnić: !xjest bitowe-NIE tutaj, nie logiczne-NIE)

Przypadki testowe:

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

Wypróbuj online!

Chodzi o sprawdzenie, czy | x | jest potęgą 2 (używając (y & (y - 1)) == 0jak zwykle). Jeśli x jest potęgą 2, to dalej sprawdzamy (1) kiedy x >= 0, powinna to być również parzysta potęga 2, lub (2) kiedy x < 0, powinna to być nieparzysta potęga 2. Sprawdzamy to poprzez &„ bad_power_of_two"maska ​​0x… aaaa kiedy x >= 0(produkuje 0 tylko wtedy, gdy jest parzystą potęgą) lub 0x… 5555 kiedy x < 0.

Haskell, 2 3 operacje

import Data.Bits (.&.)

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

Definiuje funkcję rekurencyjną f(n). Stosowane operacje to wywołanie funkcji ( f), dzielenie ( div) oraz bitowe i ( .&.).

Nie zawiera żadnych pętli, ponieważ Haskell nie ma instrukcji pętli :-)

Operacje w Pythonie 3, 10 lub 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

Zwraca 5za moce -2, 0inaczej

C, 5 operacji

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 operacji, bez pętli

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 operacja

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

Montaż, 1 operacja

.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

Używa ogromnej tabeli odnośników, aby sprawdzić, czy liczba jest potęgą 2. Możesz ją rozszerzyć do 64 bitów, ale znalezienie komputera do przechowywania takiej ilości danych pozostało ćwiczeniu dla czytelnika :-P

C, 31 operacji

Demo na żywo

Mój pomysł jest prosty, jeśli jest potęgą dwóch, to jeśli jego log jest nawet wtedy, musi być dodatni, w przeciwnym razie jego log musi być nieparzysty.

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 operacji

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

lub:

C, 13 operacji bez pętli jako warunków

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

Wyjaśnienie:

• n&-ndaje najniższy ustawiony bit n.
• ajest zanegowaną wartością bezwzględną n/2, koniecznie ujemną, ponieważ /2wyklucza przepełnienie negacji.
• a/xwynosi zero tylko wtedy, gdy ajest dokładną siłą dwóch; w przeciwnym razie ustawiony jest co najmniej jeden inny bit i jest on wyższy niż xnajniższy bit, co daje wynik ujemny.
• ~(a/x >> 63)następnie zwraca maskę bitową, która jest jednością, jeśli nlub -njest potęgą dwóch, w przeciwnym razie zerami.
• ^sjest nakładany na maskę, aby sprawdzić znak, naby zobaczyć, czy jest to moc -2.

PHP, 3 operacje

trójskładnikowe i ifsą niedozwolone; więc nadużycie 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: jeśli liczba to 0 lub 1, zwróć liczbę
2. $n&1: jeśli liczba jest nieparzysta, zwróć 0
3. test else $n/-2(+ rzut na int)

JavaScript ES6, 7 operacji

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

Wypróbuj online!

Wyjaśnienie

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

Podczas X! = 0 i X% 2 == 0 4 OPS
/ x jest równe 1, tak długo jak nie ma wartości 0 x (0/0 daje NaN które oceniano jako FAŁSZ)
-bitowe i
X 1 ^ 1 jest równe 1 jeśli x jest parzyste (x i 1) x lub 1

x/=-2;x=x|0

Jest to forma podziału zdefiniowana w pytaniu 1 op

while(x&0xfffffffe)  

Podczas gdy x! = 1 i x! = 0 1 operacja
Warunek konieczny do wyjścia, gdy x == 0 lub x == 1, ponieważ te dwie wartości zwracają i wejście w nieskończoną pętlę nie byłoby produktywne. Można to teoretycznie rozszerzyć dla większych wartości poprzez zwiększenie liczby szesnastkowej. Obecnie działa do ± 2 ^ 32-1

x-=x

Ustaw x na 0 1 op.
Chociaż mógłbym użyć return 0 dla 0 operacji, czułem, że pętla while, która jest przerwana przez inną instrukcję, wydaje się zbyt podobna do oszustwa.

return x

zwraca x (1 jeśli moc -2, 0 w przeciwnym razie)