Ceci est une version du défi récent. Ce nombre est-il une puissance entière de -2? avec un ensemble différent de critères conçus pour mettre en évidence la nature intéressante du problème et rendre le défi plus difficile. J'y ai réfléchi ici .

Le défi merveilleusement énoncé par Toby dans la question connexe est le suivant:

Il existe des moyens intelligents pour déterminer si un entier est une puissance exacte de 2. Ce n'est plus un problème intéressant, alors déterminons si un entier donné est une puissance exacte de -2 . Par exemple:

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

Règles:

• Un entier est de 64 bits, signé, complément à deux. Il s'agit du seul type de données avec lequel vous pouvez travailler.
• Vous ne pouvez utiliser que les opérations suivantes. Chacune de ces opérations compte pour une opération.
  • n << k, n >> k: Décalage gauche / droiten par kbits. Le bit de signe est étendu dans le décalage à droite.
  • n >>> k: Décalage à droite mais sans étendre le bit de signe. Les 0 sont décalés.
  • a & b, a | b,a ^ b : Bitwise ET, OU, XOR.
  • a + b, a - b,a * b : Ajouter, soustraire, multiplier.
  • ~b: Inversion au niveau du bit.
  • -b: Négation du complément à deux.
  • a / b, a % b : Diviser (quotient entier, arrondi vers 0) et modulo.
    • Le module des nombres négatifs utilise les règles spécifiées en C99 : (a/b) * b + a%bdoit être égal a. Il en 5 % -3est de même 2et -5 % 3est-2 :
    • 5 / 3est 1, 5 % 3est2 , comme 1 * 3 + 2 = 5.
    • -5 / 3est -1, -5 % 3est-2 , comme -1 * 3 + -2 = -5.
    • 5 / -3est -1, 5 % -3est2 , comme -1 * -3 + 2 = 5.
    • -5 / -3est 1, -5 % -3est-2 , comme 1 * -3 + -2 = -5.
    • Notez que l' //opérateur de division de plancher de Python ne satisfait pas ici la propriété de "division vers 0" de la division et que l' %opérateur de Python ne satisfait pas non plus aux exigences.
  • Les affectations ne comptent pas comme une opération. Comme en C, les affectations sont évaluées à la valeur du côté gauche après l'affectation: a = (b = a + 5)définit bsur a + 5, puis définit asur bet compte comme une opération.
  • Les affectations composées peuvent être utilisées comme des a += bmoyens a = a + bet comptent comme une opération.
• Vous pouvez utiliser des constantes entières, elles ne comptent pour rien.
• Les parenthèses pour spécifier l'ordre des opérations sont acceptables.
• Vous pouvez déclarer des fonctions. Les déclarations de fonction peuvent être dans n'importe quel style qui vous convient, mais notez que les entiers 64 bits sont le seul type de données valide. Les déclarations de fonction ne comptent pas comme des opérations, mais un appel de fonction compte comme un. En outre, pour être clair: les fonctions peuvent contenir plusieurs returninstructions et les returns de n'importe quel point sont autorisés. Le returnlui-même ne compte pas comme une opération.
• Vous pouvez déclarer des variables sans frais.
• Vous pouvez utiliser des whileboucles, mais vous ne pouvez pas utiliser ifou for. Les opérateurs utilisés dans la whilecondition comptent pour votre score. whileles boucles s'exécutent tant que leur condition est évaluée à une valeur non nulle (un 0 "véridique" dans les langues qui ont ce concept n'est pas un résultat valide). Le retour anticipé étant autorisé, vous êtes autorisé à utiliserbreak aussi bien
• Le débordement / sous-dépassement est autorisé et aucun serrage de valeur ne sera effectué. Il est traité comme si l'opération s'est réellement déroulée correctement et a ensuite été tronqué à 64 bits.

Critères de pointage / de victoire:

Votre code doit produire une valeur non nulle si l'entrée est une puissance de -2 et zéro sinon.

C'est le golf à code atomique . Votre score est le nombre total d'opérations présentes dans votre code (tel que défini ci-dessus), et non le nombre total d'opérations exécutées au moment de l'exécution. Le code suivant:

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

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

Contient 5 opérations: deux dans la fonction et trois appels de fonction.

Peu importe la façon dont vous présentez votre résultat, utilisez ce qui est pratique dans votre langage, que ce soit finalement le stockage du résultat dans une variable, le retour d'une fonction, ou autre.

Le gagnant est le poste qui est manifestement correct (fournissez une preuve occasionnelle ou formelle si nécessaire) et qui a le score le plus bas comme décrit ci-dessus.

Bonus en mode très difficile!

Pour avoir une chance de gagner absolument rien, sauf la capacité potentielle d'impressionner les gens lors des fêtes, soumettez une réponse sans utiliser de whileboucles! Si suffisamment de ceux-ci sont soumis, je peux même envisager de diviser les groupes gagnants en deux catégories (avec et sans boucles).

Remarque: Si vous souhaitez fournir une solution dans une langue qui ne prend en charge que les entiers 32 bits, vous pouvez le faire, à condition de justifier suffisamment qu'elle sera toujours correcte pour les entiers 64 bits dans une explication.

Aussi: Certaines fonctionnalités spécifiques à une langue peuvent être autorisées sans frais si elles n'échappent pas aux règles mais sont nécessaires pour contraindre votre langue à se comporter conformément aux règles ci-dessus . Par exemple (artificiel), je permettrai une comparaison libre non égale à 0 dans les whileboucles, lorsqu'elle est appliquée à la condition dans son ensemble, comme solution de contournement pour une langue qui a des «vrais» 0. Des tentatives claires de tirer parti de ces types de choses ne sont pas autorisées - par exemple, le concept de valeurs "véridiques" 0 ou "non définies" n'existe pas dans le jeu de règles ci-dessus, et il est donc possible de ne pas s'y fier.

C ++, 15 opérations

Je ne sais pas pourquoi les whileboucles sont autorisées car elles détruisent l'ensemble du défi. Voici une réponse sans aucune:

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 opérations

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

Essayez-le en ligne!

Les opérations sont >>, &, /.

L'idée est de diviser à plusieurs reprises par -2. Pouvoirs de -2 à chaîne vers le bas à 1: -8 -> 4 -> -2 -> 1. Si nous frappons un 1, acceptez. Si nous frappons un nombre impair avant de frapper 1, rejetez. Nous devons également rejeter 0ce qui va pour toujours à lui-même.

Les while n>>1:boucles jusqu'à nest 0 ou 1. Lorsque la boucle se rompt, nelle-même est renvoyée et 1est une sortie Truthy et 0Falsey. À l'intérieur de la boucle, nous refusons d'appliquer à plusieurs reprises n -> n/-2et rejetons toute impaire n.

Étant donné que le /n'est utilisé que sur des valeurs paires, son comportement d'arrondi n'entre jamais en jeu. Donc, peu importe que Python arrondisse différemment de la spécification.

Rouille, 14 12 opérations (pas de boucles)

Nécessite une optimisation ( -O) ou -C overflow-checks=nopour activer la soustraction débordante au lieu de la panique.

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
}

(Pour clarifier: !xest bit à bit-PAS ici, pas logique-PAS)

Cas de test:

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

Essayez-le en ligne!

L'idée est de vérifier si | x | est une puissance de 2 (à utiliser (y & (y - 1)) == 0comme d'habitude). Si x est une puissance de 2, alors nous vérifions en outre (1) quand x >= 0, ce devrait également être une puissance paire de 2, ou (2) quand x < 0, ce devrait être une puissance impaire de 2. Nous vérifions cela en &-ing le " bad_power_of_two"masque 0x… aaaa quand x >= 0(produit 0 seulement quand il s'agit d'une puissance paire), ou 0x… 5555 quand x < 0.

Haskell, 2 3 opérations

import Data.Bits (.&.)

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

Définit une fonction récursive f(n). Les opérations utilisées sont appel de fonction ( f), division ( div) et au niveau du bit et ( .&.).

Ne contient pas de boucles car Haskell n'a pas d'instructions de boucle :-)

Opérations Python 3, 10 ou 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

Retourne 5pour les pouvoirs de -2, 0sinon

C, 5 opérations

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 opérations, sans boucles

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 opération

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

Assemblage, 1 opération

.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

Utilise une énorme table de recherche pour déterminer si le nombre est une puissance de 2. Vous pouvez l'étendre à 64 bits, mais trouver un ordinateur pour stocker autant de données est laissé au lecteur comme exercice :-P

C, 31 opérations

Démo en direct

Mon idée est simple, si c'est une puissance de deux, alors si son log est pair alors il doit être positif, sinon son log doit être impair.

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 opérations

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

ou:

C, 13 opérations sans boucles en tant que conditions

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

Explication:

• n&-ndonne le bit de jeu le plus bas de n.
• aest la valeur absolue niée de n/2, nécessairement négative car/2 empêche le débordement de la négation.
• a/xest nul seulement si aest une puissance exacte de deux; sinon au moins un autre bit est défini, et il est supérieur àx au bit le plus bas, ce qui donne un résultat négatif.
• ~(a/x >> 63)donne alors un masque de bits qui est tout-si si nou -nest une puissance de deux, sinon tout-zéros.
• ^sest appliqué au masque pour vérifier le signe de npour voir s'il s'agit d'une puissance de -2.

PHP, 3 opérations

ternaire et ifsont interdits; alors abusons 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: si le nombre est 0 ou 1, renvoie le numéro
2. $n&1: si le nombre est impair, retourne 0
3. test else $n/-2(+ transtypage en entier)

JavaScript ES6, 7 opérations

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

Essayez-le en ligne!

Explication

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

Alors que x! = 0 et x% 2 == 0 4 ops
x / x est égal à 1 tant que x n'est pas 0 (0/0 donne NaN qui est évalué comme faux)
& au niveau du bit et
x & 1 ^ 1 est égal à 1 si x est pair (x et 1) xou 1

x/=-2;x=x|0

C'est la forme de division définie par la question 1 op

while(x&0xfffffffe)  

Tandis que x! = 1 et x! = 0 1 op
La condition requise pour sortir lorsque x == 0 ou x == 1 car ces deux sont les valeurs de retour et entrer dans une boucle infinie ne serait pas productive. Cela pourrait théoriquement être étendu pour des valeurs plus élevées en augmentant le nombre hexadécimal. Fonctionne actuellement jusqu'à ± 2 ^ 32-1

x-=x

Mettre x à 0 1 op
Alors que j'aurais pu utiliser return 0 pour 0 ops, je sentais que toute boucle while qui est rompue par une autre instruction ressemble trop à de la triche.

return x

renvoie x (1 si puissance de -2, 0 sinon)