26
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 shiftn
byk
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 equala
. So5 % -3
is2
, and-5 % 3
is-2
: 5 / 3
is1
,5 % 3
is2
, as 1 * 3 + 2 = 5.-5 / 3
is-1
,-5 % 3
is-2
, as -1 * 3 + -2 = -5.5 / -3
is-1
,5 % -3
is2
, as -1 * -3 + 2 = 5.-5 / -3
is1
,-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.
- Modulo of negative numbers uses the rules specified in C99:
- 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)
setsb
toa + 5
, then setsa
tob
, and counts as one operation. - Compound assignments may be used
a += b
meansa = 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 andreturn
s from any point are allowed. Thereturn
itself does not count as an operation. - You may declare variables at no cost.
- You may use
while
loops, but you may not useif
orfor
. Operators used in thewhile
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 usebreak
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.
Comments are not for extended discussion; this conversation has been moved to chat.
– Dennis – 2017-04-07T17:37:08.477@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. – Jason C – 2017-04-08T21:25:29.230How does it make sense to allow
while
andbreak
but notif
?if (x) { ... }
is equivalent towhile (x) { ... break; }
. – R.. GitHub STOP HELPING ICE – 2017-04-09T02:06:24.647@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! :) – Jason C – 2017-04-09T02:46:06.103@JasonC: See how I did it in my C answer just now. I might try the bonus version later. – R.. GitHub STOP HELPING ICE – 2017-04-09T03:12:26.370
1Why
if
andfor
are disallowed?int x=condition; while (x) { ... x=0; }
is free, just more code. Same thing with c-stylefor
. – Qwertiy – 2017-04-10T21:07:21.277@Qwertiy The more dubious part is
break
. Note by the way that in your example if you wanted to setx=0
conditionally based on something, you'd still have to come up with clever logic since you can't useif
. As forfor
loops, those aren't there simply because you can already accomplish what you need withwhile
, so there was no real need for me to clutter up the rule list with specifics about a redundantfor
;while
was easier to specify. Anyways, there's always the "bonus" version! :) – Jason C – 2017-04-10T22:05:07.277