26
\$\begingroup\$

This is a version of the recent challenge Is this number an integer power of -2? with a different set of criteria designed to highlight the interesting nature of the problem and make the challenge more difficult. I put some consideration into it here.

The challenge as wonderfully stated by Toby in the linked question, is:

There are clever ways of determining whether an integer is an exact power of 2. That's no longer an interesting problem, so let's determine whether a given integer is an exact power of -2. For example:

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

Rules:

  • An integer is 64 bits, signed, two's complement. This is the only data type you may work with.
  • You may only use the following operations. Each of these counts as one operation.
    • n << k, n >> k: Left/right shift n by k bits. Sign bit is extended in right shift.
    • n >>> k: Right shift but do not extend sign bit. 0's are shifted in.
    • a & b, a | b, a ^ b: Bitwise AND, OR, XOR.
    • a + b, a - b, a * b: Add, subtract, multiply.
    • ~b: Bitwise invert.
    • -b: Two's complement negation.
    • a / b, a % b: Divide (integer quotient, rounds towards 0), and modulo.
      • Modulo of negative numbers uses the rules specified in C99: (a/b) * b + a%b shall equal a. So 5 % -3 is 2, and -5 % 3 is -2:
      • 5 / 3 is 1, 5 % 3 is 2, as 1 * 3 + 2 = 5.
      • -5 / 3 is -1, -5 % 3 is -2, as -1 * 3 + -2 = -5.
      • 5 / -3 is -1, 5 % -3 is 2, as -1 * -3 + 2 = 5.
      • -5 / -3 is 1, -5 % -3 is -2, as 1 * -3 + -2 = -5.
      • Note that Python's // floor division operator does not satisfy the "round towards 0" property of division here, and Python's % operator does not meet the requirements, either.
    • Assignments do not count as an operation. As in C, assignments evaluate to the value of the left-hand side after the assignment: a = (b = a + 5) sets b to a + 5, then sets a to b, and counts as one operation.
    • Compound assignments may be used a += b means a = a + b and count as one operation.
  • You may use integer constants, they do not count as anything.
  • Parentheses to specify order of operations are acceptable.
  • You may declare functions. Function declarations can be in any style that is convenient for you but note that 64 bit integers are the only valid data type. Function declarations do not count as operations, but a function call counts as one. Also, to be clear: Functions may contain multiple return statements and returns from any point are allowed. The return itself does not count as an operation.
  • You may declare variables at no cost.
  • You may use while loops, but you may not use if or for. Operators used in the while condition count towards your score. while loops execute as long as their condition evaluates to a non-zero value (a "truthy" 0 in languages that have this concept is not a valid outcome). Since early-return is allowed, you are allowed to use break as well
  • Overflow/underflow is allowed and no value clamping will be done. It is treated as if the operation actually happened correctly and was then truncated to 64 bits.

Scoring / Winning Criteria:

Your code must produce a value that is non-zero if the input is a power of -2, and zero otherwise.

This is . Your score is the total number of operations present in your code (as defined above), not the total number of operations that are executed at run-time. The following 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;
}

Contains 5 operations: two in the function, and three function calls.

It doesn't matter how you present your result, use whatever is convenient in your language, be it ultimately storing the result in a variable, returning it from a function, or whatever.

The winner is the post that is demonstrably correct (supply a casual or formal proof if necessary) and has the lowest score as described above.

Bonus Very Hard Mode Challenge!

For a chance at winning absolutely nothing except the potential ability to impress people at parties, submit an answer without using while loops! If enough of these are submitted I may even consider dividing the winning groups into two categories (with and without loops).


Note: If you'd like to provide a solution in a language that only supports 32-bit integers, you may do so, provided that you sufficiently justify that it will still be correct for 64-bit integers in an explanation.

Also: Certain language-specific features may be permitted at no-cost if they do not evade the rules but are necessary to coerce your language into behaving according to the rules above. For example (contrived), I will permit a free not equals 0 comparison in while loops, when applied to the condition as a whole, as a workaround for a language that has "truthy" 0's. Clear attempts to take advantage of these types of things are not allowed -- e.g. the concept of "truthy" 0 or "undefined" values does not exist in the above ruleset, and so they may not be relied on.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Apr 7 '17 at 17:37
  • \$\begingroup\$ @hvd If you read this: You should totally undelete your answer! Assuming it is correct, even without m ^= s it's still impressive, and I think it'd be totally OK to make the substitution to improve it even more. \$\endgroup\$ – Jason C Apr 8 '17 at 21:25
  • \$\begingroup\$ How does it make sense to allow while and break but not if? if (x) { ... } is equivalent to while (x) { ... break; }. \$\endgroup\$ – R.. Apr 9 '17 at 2:06
  • \$\begingroup\$ @R.. It doesn't make 100% sense (break and early returns are the regrettable part) and is a long story and a lesson learned in rules for future challenges. There's always the "bonus" version! :) \$\endgroup\$ – Jason C Apr 9 '17 at 2:46
  • 1
    \$\begingroup\$ Why if and for are disallowed? int x=condition; while (x) { ... x=0; } is free, just more code. Same thing with c-style for. \$\endgroup\$ – Qwertiy Apr 10 '17 at 21:07

11 Answers 11

35
\$\begingroup\$

C++, 15 operations

I have no idea why while loops are allowed as they destroy the whole challenge. Here is an answer without any:

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
}
\$\endgroup\$
  • \$\begingroup\$ Why do while loops destroy the whole challenge? \$\endgroup\$ – Mr. Xcoder Apr 6 '17 at 16:52
  • 10
    \$\begingroup\$ @Mr.Xcoder Because the challenge is about doing it with simple bitwise operations and while goes against that in every way. \$\endgroup\$ – orlp Apr 6 '17 at 16:58
  • \$\begingroup\$ I mean, unless you make the while loops multiply the number of operations times the number times executed in the loop for a static n or something. \$\endgroup\$ – Magic Octopus Urn Apr 6 '17 at 17:09
  • \$\begingroup\$ I made a comment about this here. \$\endgroup\$ – Jason C Apr 6 '17 at 17:15
  • \$\begingroup\$ @JasonC That's because I should've used a right shift without sign bit. I edited the code (it uses uint64_t because that's the only way to get the right shift without sign extension.) \$\endgroup\$ – orlp Apr 6 '17 at 17:27
25
\$\begingroup\$

Python 2, 3 operations

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

Try it online!

The operations are >>, &, /.

The idea is to repeatedly divide by -2. Powers of -2 chain down to 1: -8 -> 4 -> -2 -> 1. If we hit a 1, accept. If we hit an odd number before hitting 1, reject. We also need to reject 0, which forever goes to itself.

The while n>>1: loops until n is 0 or 1. When the loop breaks, n itself is returned, and 1 is a Truthy output and 0 a Falsey one. Inside the loop, we reject repeatedly apply n -> n/-2 and reject any odd n.

Since the / is only ever used on even values, its rounding behavior never comes into play. So, it doesn't matter that Python rounds differently from the spec.

\$\endgroup\$
  • \$\begingroup\$ Nice. Clever logic in the algorithm and good work combining conditionals into bit operations. Also, can confirm, implementation works in C. \$\endgroup\$ – Jason C Apr 6 '17 at 19:27
  • \$\begingroup\$ Why while n&1 instead of if n&1? \$\endgroup\$ – Mark Ransom Apr 6 '17 at 21:16
  • 2
    \$\begingroup\$ @MarkRansom The challenge doesn't allow if. \$\endgroup\$ – xnor Apr 6 '17 at 21:19
  • \$\begingroup\$ Aha, missed that. Very clever substitution. \$\endgroup\$ – Mark Ransom Apr 6 '17 at 21:21
  • 1
    \$\begingroup\$ @EvSunWoodard The scoring is the number of operators in the code, not the number of calls to them during execution, which depends on the input: "This is atomic-code-golf. Your score is the total number of operations present in your code." \$\endgroup\$ – xnor Apr 7 '17 at 20:36
11
\$\begingroup\$

Rust, 14 12 operations (no loops)

Requires optimization (-O) or -C overflow-checks=no to enable the overflowing subtraction instead of panic.

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
}

(To clarify: !x is bitwise-NOT here, not logical-NOT)

Test cases:

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

Try it online!


The idea is to check if |x| is a power of 2 (using (y & (y - 1)) == 0 as usual). If x is a power of 2, then we further check (1) when x >= 0, it should also be an even power of 2, or (2) when x < 0, it should be an odd power of 2. We check this by &-ing the "bad_power_of_two" mask 0x…aaaa when x >= 0 (produces 0 only when it is an even power), or 0x…5555 when x < 0.

\$\endgroup\$
  • \$\begingroup\$ I stole your ~((r | -r) >> 63) trick to finish up fixing my answer. \$\endgroup\$ – orlp Apr 6 '17 at 20:38
6
\$\begingroup\$

Haskell, 2 3 operations

import Data.Bits (.&.)

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

Defines a recursive function f(n). Operations used are function call (f), division (div), and bitwise and (.&.).

Contains no loops because of the fact that Haskell has no loop statements :-)

\$\endgroup\$
  • 4
    \$\begingroup\$ Why am I not surprised that the Haskell solution using no loops is provided by someone named "Opportunist?" =) \$\endgroup\$ – Cort Ammon Apr 7 '17 at 0:31
  • 1
    \$\begingroup\$ I'm very hesitant about the f 0, f 1, f n ... here because they are essentially if's in disguise, although then again, I did allow while + break and early returns, so it seems fair. While it does seem to take advantage of my rule set being inadvertently left open to interpretation, it is a nice solution. \$\endgroup\$ – Jason C Apr 7 '17 at 0:39
  • 3
    \$\begingroup\$ In particular the |s are especially up in the air. That said, this does violate one particular rule in a less-debatable way: The comparison == is not allowed. Note, however, that if my interpretation of this code is correct, the usage of booleans here does appear acceptable as substituting arbitrary integer values in their place does not appear to change the results, and they are more of a final presentation form. \$\endgroup\$ – Jason C Apr 7 '17 at 0:43
  • \$\begingroup\$ @JasonC I'm only using == because there is no other way to cast from Int to Bool or "Truthy" in Haskell. Whether the pattern matching and guards are in violation of the "no ifs" rule is your call ;-) \$\endgroup\$ – Opportunist Apr 7 '17 at 0:54
  • 18
    \$\begingroup\$ With pattern matching, you could just hardcode the results for all 64-bit integers using 0 operations. \$\endgroup\$ – xnor Apr 7 '17 at 0:58
5
\$\begingroup\$

Python 3, 10 or 11 9 operations

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

Returns 5 for powers of -2, 0 otherwise

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Apr 7 '17 at 17:37
5
\$\begingroup\$

C, 5 operations

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 operations, without loops

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Oh man, that last one is just evil. Nice. \$\endgroup\$ – Jason C Apr 10 '17 at 22:10
4
\$\begingroup\$

Assembly, 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

Uses a huge lookup table to find whether the number is a power of 2. You can expand this to 64 bits, but finding a computer to store that much data is left as an exercise to the reader :-P

\$\endgroup\$
  • 1
    \$\begingroup\$ Indexing a table is not one of the allowed operations. \$\endgroup\$ – R.. Apr 9 '17 at 2:12
  • 1
    \$\begingroup\$ Also this is clearly not extensible to 64 bits. :-) \$\endgroup\$ – R.. Apr 9 '17 at 2:13
  • \$\begingroup\$ Indeed, indexing a table was not intended to be permitted under the current rules. I specified "you may declare variables" and "you may specify integer literals" with the intent of scalars, and semantically this is an array (and pedantically speaking I did not allow array types nor did I allow indexing of any sort as one of the operations although you could call it "addition" in the context of assembler), but being the Opportunist that you are... :) \$\endgroup\$ – Jason C Apr 9 '17 at 15:43
3
\$\begingroup\$

C, 31 operations

Live Demo

My idea is simple, if it's a power of two, then if its log is even then it has to be positive, otherwise its log has to be odd.

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) );
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You actually did better than you think. A function call only counts as 1, not as the number of operators in the function. So, if I've counted correctly (double check) you've got something like 6 for isPositive + 5 for isPowerOfTwo + 3 for log2 + 17 for isPowerOfNegativeTwo = 31. \$\endgroup\$ – Jason C Apr 6 '17 at 22:43
1
\$\begingroup\$

C, 7 operations

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

or:

C, 13 operations without loops-as-conditionals

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

Explanation:

  • n&-n yields the lowest set bit of n.
  • a is the negated absolute value of n/2, necessarily negative because /2 precludes overflow of negation.
  • a/x is zero only if a is an exact power of two; otherwise at least one other bit is set, and it's higher than x, the lowest bit, yielding a negative result.
  • ~(a/x >> 63) then yields a bitmask that's all-ones if n or -n is a power of two, otherwise all-zeros.
  • ^s is applied to the mask to check the sign of n to see if it's a power of -2.
\$\endgroup\$
1
\$\begingroup\$

PHP, 3 operations

ternary and if are disallowed; so let´s abuse 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: if number is 0 or 1, return number
  2. $n&1: if number is odd, return 0
  3. else test $n/-2 (+cast to int)
\$\endgroup\$
0
\$\begingroup\$

JavaScript ES6, 7 operations

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

Try it online!

Explanation

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

While x!=0 and x%2==0 4 ops
x/x is equal to 1 so long as x is not 0 (0/0 gives NaN which is evaluated as false)
& bitwise and
x&1^1 is equal to 1 if x is even (x and 1) xor 1

x/=-2;x=x|0

This is the form of division defined by the question 1 op

while(x&0xfffffffe)  

While x!=1 and x!=0 1 op
The condition needed to exit when x==0 or x==1 as those two are the return values and entering an infinite loop would not be productive. This could theoretically be extended for greater values by increasing the hexadecimal number. Currently works for up to ±2^32-1

x-=x

Set x to 0 1 op
While I could have used return 0 for 0 ops, I felt that any while loop which is broken by another statement feels too much like cheating.

return x

returns x (1 if power of -2, 0 otherwise)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.