Dies ist eine Version der letzten Herausforderung. Ist diese Zahl eine ganzzahlige Potenz von -2? mit einem anderen Satz von Kriterien, um die interessante Natur des Problems hervorzuheben und die Herausforderung zu erschweren. Ich habe einige Überlegungen in sie hier .

Die Herausforderung, die Toby in der verknüpften Frage so wunderbar formuliert hat, ist:

Es gibt clevere Methoden, um festzustellen, ob eine Ganzzahl eine exakte Potenz von 2 ist. Das ist kein interessantes Problem mehr. Lassen Sie uns also feststellen, ob eine bestimmte Ganzzahl eine exakte Potenz von -2 ist . Beispielsweise:

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

Regeln:

• Eine Ganzzahl ist 64 Bit, vorzeichenbehaftet, Zweierkomplement. Dies ist der einzige Datentyp, mit dem Sie arbeiten können.
• Sie dürfen nur die folgenden Vorgänge ausführen. Jede davon zählt als eine Operation.
  • n << k, n >> k: Links- / Rechtsverschiebung num kBits. Vorzeichenbit wird bei Rechtsverschiebung verlängert.
  • n >>> k: Rechtsverschiebung, aber Vorzeichenbit nicht verlängern. Nullen werden verschoben.
  • a & b, a | b, a ^ b: Logisches AND, OR, XOR.
  • a + b, a - b, a * bAddieren, subtrahieren, multiplizieren.
  • ~b: Bitweise invertieren.
  • -b: Zweierkomplement-Negation.
  • a / b, a % b: Dividieren (ganzzahliger Quotient, rundet in Richtung 0) und Modulo.
    • Das Modulo negativer Zahlen verwendet die in C99 angegebenen Regeln : (a/b) * b + a%bmuss gleich sein a. So 5 % -3ist 2und -5 % 3ist -2:
    • 5 / 3ist 1, 5 % 3ist 2, als 1 * 3 + 2 = 5.
    • -5 / 3ist -1, -5 % 3ist -2, als -1 * 3 + -2 = -5.
    • 5 / -3ist -1, 5 % -3ist 2, als -1 * -3 + 2 = 5.
    • -5 / -3ist 1, -5 % -3ist -2, als 1 * -3 + -2 = -5.
    • Beachten Sie, dass der //Floor Division Operator von Python die Divisionseigenschaft "round towards 0" hier %nicht erfüllt und der Operator von Python auch nicht die Anforderungen erfüllt.
  • Aufträge zählen nicht als Vorgang. Wie in C werden Zuweisungen nach der Zuweisung mit dem Wert auf der linken Seite bewertet: a = (b = a + 5)setzt bauf a + 5, setzt aauf bund zählt als eine Operation.
  • Verbindung Zuordnungen verwendet werden a += bMittel a = a + bund als eine Operation zählen.
• Sie können Integer-Konstanten verwenden, sie zählen nicht als etwas.
• Klammern zur Angabe der Operationsreihenfolge sind zulässig.
• Sie können Funktionen deklarieren. Funktionsdeklarationen können in jedem für Sie geeigneten Stil vorliegen. Beachten Sie jedoch, dass 64-Bit-Ganzzahlen der einzige gültige Datentyp sind. Funktionsdeklarationen gelten nicht als Operationen, sondern eine Funktion Anruf zählt. Um auch klar zu sein: Funktionen können mehrere returnAnweisungen enthalten und sind returnvon jedem Punkt aus erlaubt. Das returnselbst zählt nicht als Operation.
• Sie können Variablen kostenlos deklarieren.
• Sie können whileSchleifen verwenden, jedoch nicht ifoder for. In der whileBedingung verwendete Operatoren zählen zu Ihrer Punktzahl. whileSchleifen werden ausgeführt, solange ihre Bedingung einen Wert ungleich Null ergibt (eine "wahrheitsgemäße" 0 in Sprachen mit diesem Konzept ist kein gültiges Ergebnis). Seit früh Rückkehr erlaubt ist, werden Sie nutzen breakals auch
• Überlauf / Unterlauf ist erlaubt und es erfolgt keine Werteklemmung. Es wird so behandelt, als ob die Operation tatsächlich korrekt ausgeführt und dann auf 64 Bit gekürzt wurde.

Bewertungskriterien / Gewinnkriterien:

Ihr Code muss einen Wert ungleich Null erzeugen, wenn die Eingabe eine Potenz von -2 ist, und ansonsten Null.

Das ist Atomic-Code-Golf . Ihre Punktzahl ist die Gesamtzahl der in Ihrem Code vorhandenen Vorgänge (wie oben definiert), nicht die Gesamtzahl der Vorgänge, die zur Laufzeit ausgeführt werden. Der folgende Code:

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

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

Enthält 5 Operationen: zwei in der Funktion und drei Funktionsaufrufe.

Es spielt keine Rolle, wie Sie Ihr Ergebnis präsentieren, was auch immer in Ihrer Sprache angezeigt wird, ob Sie das Ergebnis letztendlich in einer Variablen speichern, von einer Funktion zurückgeben oder was auch immer.

Der Gewinner ist der Beitrag, der nachweislich korrekt ist (ggf. einen beiläufigen oder formellen Beweis vorlegen) und die niedrigste Punktzahl aufweist, wie oben beschrieben.

Bonus Very Hard Mode Challenge!

Senden Sie eine Antwort, ohne whileSchleifen zu verwenden, um eine Chance zu haben, absolut nichts zu gewinnen, außer die potenzielle Fähigkeit, Leute auf Partys zu beeindrucken ! Wenn genug von diesen eingereicht werden, kann ich sogar in Betracht ziehen, die Gewinnergruppen in zwei Kategorien (mit und ohne Schleifen) zu unterteilen.

Hinweis: Wenn Sie eine Lösung in einer Sprache bereitstellen möchten, die nur 32-Bit-Ganzzahlen unterstützt, können Sie dies tun, sofern Sie hinreichend begründen, dass dies für 64-Bit-Ganzzahlen in einer Erläuterung weiterhin korrekt ist.

Außerdem: Bestimmte sprachspezifische Funktionen sind möglicherweise kostenlos zulässig, wenn sie sich nicht den Regeln widersetzen, aber erforderlich sind, um Ihre Sprache dazu zu zwingen, sich gemäß den obigen Regeln zu verhalten . Zum Beispiel (erfunden), erlaube ich ein freies entspricht nicht 0 Vergleich in whileSchleifen, wenn die Bedingung als Ganze angewandt, als Behelfslösung für eine Sprache , die „truthy“ 0 hat. Eindeutige Versuche, diese Art von Dingen auszunutzen, sind nicht zulässig - z. B. gibt es in dem obigen Regelsatz kein Konzept für "wahrheitsgemäße" 0- oder "undefinierte" Werte, und daher kann man sich möglicherweise nicht auf sie verlassen.

C ++, 15 Operationen

Ich habe keine Ahnung, warum whileSchleifen zulässig sind, da sie die gesamte Herausforderung zerstören. Hier ist eine Antwort ohne:

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
}

Python 2 , 3 Operationen

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

Probieren Sie es online!

Die Operationen sind >>, &, /.

Die Idee ist, immer wieder durch -2 zu teilen. Potenzen von -2 Kette von bis zu 1: -8 -> 4 -> -2 -> 1. Wenn wir a drücken 1, akzeptieren Sie. Wenn wir vor dem Schlagen eine ungerade Zahl treffen 1, lehnen Sie ab. Wir müssen auch ablehnen 0, was für immer für sich bleibt.

Die while n>>1:Schleife bis nist 0 oder 1. Wenn die Schleife unterbrochen wird , wird sie nselbst zurückgegeben und 1ist eine Wahrheits- und 0eine Falschausgabe. Innerhalb der Schleife lehnen wir wiederholt das Anwenden ab n -> n/-2und lehnen jede ungerade ab n.

Da das /immer nur für gerade Werte verwendet wird, kommt sein Rundungsverhalten nie ins Spiel. Es spielt also keine Rolle, dass Python anders rundet als die Spezifikation.

Rost, 14 12 Operationen (keine Schleifen)

Erfordert Optimierung ( -O) oder -C overflow-checks=noum die überlaufende Subtraktion anstelle von Panik zu aktivieren.

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
}

(Zur Verdeutlichung: !xist bitweise-NICHT hier, nicht logisch-NICHT)

Testfälle:

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

Probieren Sie es online!

Die Idee ist zu prüfen, ob | x | ist eine Potenz von 2 ( (y & (y - 1)) == 0wie üblich). Wenn x eine Potenz von 2 ist, dann weiter wir Prüfung (1) , wenn x >= 0, sollte es auch eine gerade Potenz von 2 sein, oder (2) wenn x < 0, sollte es eine ungerade Potenz von 2 sein wir dies überprüfen , indem &-Ing die " bad_power_of_two"mask 0x ... aaaa when x >= 0(erzeugt nur 0, wenn es eine gerade Potenz ist), oder 0x ... 5555 when x < 0.

Haskell, 2 3 Operationen

import Data.Bits (.&.)

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

Definiert eine rekursive Funktion f(n). Verwendete Operationen sind Funktionsaufruf ( f), Division ( div) und bitweise und ( .&.).

Enthält keine Schleifen, da Haskell keine Schleifenanweisungen hat :-)

Python 3, 10 oder 11 9 Operationen

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

Rückgabe 5für Potenzen von -2, 0ansonsten

C, 5 Operationen

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 Operationen, ohne Schleifen

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 Operation

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

Montage, 1 Operation

.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

Verwendet eine große Nachschlagetabelle, um festzustellen, ob die Zahl eine Potenz von 2 ist. Sie können diese auf 64 Bit erweitern, aber einen Computer zu finden, auf dem so viele Daten gespeichert sind, bleibt dem Leser als Übung :-P

C, 31 Operationen

Live-Demo

Meine Idee ist einfach, wenn es eine Zweierpotenz ist, wenn das Protokoll gerade ist, muss es positiv sein, andernfalls muss das Protokoll ungerade sein.

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 Operationen

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

oder:

C, 13 Operationen ohne Schleifen als Bedingungen

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

Erläuterung:

• n&-nergibt das niedrigste gesetzte Bit von n.
• aist der negierte Absolutwert von n/2, der notwendigerweise negativ ist, weil ein /2Überlaufen der Negation ausgeschlossen ist.
• a/xist nur dann Null, wenn aes sich um eine exakte Zweierpotenz handelt; Andernfalls wird mindestens ein anderes Bit gesetzt und es ist höher als xdas niedrigste Bit, was zu einem negativen Ergebnis führt.
• ~(a/x >> 63)dann ergibt sich eine Bitmaske, die nur Einsen enthält, wenn noder -neine Zweierpotenz ist, andernfalls nur Nullen.
• ^swird auf die Maske angewendet, um das Vorzeichen von zu überprüfen, um festzustellen n, ob es sich um eine Potenz von handelt -2.

PHP, 3 Operationen

ternär und ifunzulässig sind; Also lasst uns missbrauchen 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: Wenn die Zahl 0 oder 1 ist, wird die Zahl zurückgegeben
2. $n&1: Wenn die Zahl ungerade ist, wird 0 zurückgegeben
3. else test $n/-2(+ cast to int)

JavaScript ES6, 7 Operationen

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

Probieren Sie es online!

Erläuterung

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

Während x! = 0 und x% 2 == 0 4 ops
x / x gleich 1 ist , solange x nicht 0 (0/0 gibt NaN , die als falsch bewertet wird)
& bitweise und
x & 1 ^ 1 gleich 1 wenn x gerade ist (x und 1) xoder 1

x/=-2;x=x|0

Dies ist die Form der Teilung, die durch die Frage 1 op

while(x&0xfffffffe)  

Solange x! = 1 und x! = 0 1 op
Die Bedingung, die zum Beenden erforderlich ist, wenn x == 0 oder x == 1 die Rückgabewerte sind und eine Endlosschleife eingegeben wird, wäre nicht produktiv. Dies könnte theoretisch durch Erhöhen der Hexadezimalzahl für größere Werte erweitert werden. Funktioniert derzeit für bis zu ± 2 ^ 32-1

x-=x

Setze x auf 0 1 op
Während ich 0 für 0 ops hätte zurückgeben können, hatte ich das Gefühl, dass jede while-Schleife, die durch eine andere Anweisung unterbrochen wird, zu sehr nach Schummeln aussieht.

return x

gibt x zurück (1 wenn Potenz von -2, sonst 0)