Is this number an exact power of -2: (Very) Hard Mode

Question

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 atomic-code-golf. 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.

Answer 1

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
}

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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)

Answer 10

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.

Answer 11

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)