Sum or difference of two powers of two

Your challenge, should you choose to accept it, is, given an integer K >= 1, find non-negative integers A and B such that at least one of the two conditions following hold:

1. K = 2^A + 2^B
2. K = 2^A - 2^B

If there does not exist such A and B, your program may behave in any fashion. (To clarify, A and B can be equal.)

Test cases

There are often multiple solutions to a number, but here are a few:

K => A, B
1 => 1, 0
15 => 4, 0                      ; 16 - 1 = 15
16 => 5, 4                      ; 32 - 16 = 16; also 3, 3: 8 + 8 = 16
40 => 5, 3                      ; 2^5 + 2^3 = 40
264 => 8, 3
17179867136 => 34, 11           ; 17179869184 - 2048 = 17179867136


The last test case, 17179867136, must run in under 10 seconds on any relatively modern machine. This is a code golf, so the shortest program in bytes wins. You may use a full program or a function.

• Can A equal B? Sep 10 '16 at 2:06
• @Dennis I don't see why not. Sep 10 '16 at 2:36
• ... and for 16, both 5,4 and 3,3 are valid. Sep 10 '16 at 10:54
• Actually now that I think about it, can A, B be negative? (e.g. -1, -1 for 1) Sep 10 '16 at 14:53
• @Sp3000 No, good point. Sep 10 '16 at 15:05

Python 2, 43 bytes

lambda n:[len(bin((n&-n)+k))-3for k in n,0]


Say that n==2^a ± 2^b with a>b. Then, the greatest power-of-2 factor of n is 2^b, and we can find it using the bit-trick 2^b = n&-n. That lets us compute 2^b + n, which equals either 2^a + 2 * 2^b or just 2^a. Either one has the same-length bit-length as a*. So, we output the bit-lengths of n&-n and (n&-n)+n, computed from the lengths of their binary representations. Python 3 is one byte longer for parens in for k in(n,0)].

*Except that 2^a + 2^b with a==b+1 has one longer bit-length, but that's fine because we can interpret that as 2^(a+1)-2^b.

• Wonderful - I looked for a bit fiddle, but couldn't work it out, just ported to Jelly. Sep 10 '16 at 9:21
• Try n=4 or 8 or 16 please. Sep 10 '16 at 11:36
• @Titus f(2**n) returns (n+1,n) and 2**(n+1)-2**n=2**n so there is no problem. Sep 10 '16 at 13:07
• ah ... What´s the format of bin() in Python? Sep 10 '16 at 14:11
• @Titus it's a string with a leading 0b, hence the -3. Sep 10 '16 at 14:39

(n,[s,f,z]=/^1+(.*1)?(0*)$/.exec(n.toString(2)))=>[s.length-!!f,z.length]  For the subtraction case, the first number is the number of digits in the binary representation and the second number is the number of trailing zeroes. For the addition case, we subtract 1 from the first number. If the binary representation is all 1s followed by some 0s then the addition case is assumed otherwise the subtraction case is assumed. 36-byte port of @xnor's version that only works for B≤30 in JavaScript: n=>[(l=Math.log2)(n+(n&=-n))|0,l(n)]  • @ETHproductions Sure, but I golfed it down to 36. – Neil Sep 10 '16 at 14:08 • My bad, I thought that the 36-byte version didn't work for the 17 billion test case. Sep 10 '16 at 17:39 • @ETHproductions It doesn't, but then neither did your port, as I recall (comment since deleted, sigh), since it used bitwise operations. – Neil Sep 10 '16 at 18:24 • Sorry, here it is again: n=>[n,0].map(k=>((n&-n)+k).toString(2).length-1) And both versions return [34,11] on the last test case (I'm using FF 48). Sep 10 '16 at 18:27 • @ETHproductions Aha, so more accurately they work when the second result is 30 or less. – Neil Sep 10 '16 at 18:53 Perl, 5249 32 bytes Old solution (49 bytes) Includes +1 for -p Give input on STDIN: pow2.pl <<< 17179867136  pow2.pl #!/usr/bin/perl -p$_=reverse sprintf"%b",$_;/()1(?:1+|0*)/;$_="@+"


However, using xnor's algorithm and adding a twist gives 32 bytes:

perl -nE 'say 13/9*log|0for$;=$_&-$_,$_+$'  Just the code: say 13/9*log|0for$;=$_&-$_,$_+$


This suffers from severe rounding error because 13/9 = 1.444... is quite a bit above 1/log 2 = 1.44269... (log itself also has a rounding error but that is so much smaller that we can wrap it up in the analysis of 13/9). But since any 2**big - 2** small gets corrected to 2** big before the log this doesn't mater and the calculation for 2**big + 2 * 2**small gets truncated down so is also safe.. And at the other side of the range 2**n+2**(n-1) doesn't get increased enough in the range [0,64] (I can't properly support more than the integer range anyways due to the use of &) to lead to a wrong result (multiplicator 1.5 however would be too far off for large numbers).

Brachylog, 23 bytes

,A:B#+.:2rz:^a{+|-}?,.=


Try it online!

This is much faster than required, e.g. this is still under 10 seconds on TIO.

Explanation

This is basically a direct transcription of the formula with no optimization:

,A:B     The list [A, B]
#+       Both A and B are greater than or equal to 0
.        Output = [A, B]
:2rz     The list [[2, A], [2, B]]
:^a      The list [2^A, 2^B]
{+|-}?   2^A + 2^B = Input OR 2^A - 2^B = Input
,.=      Assign a value to A and B which satisfy those constraints

• It looks like this challenge was made for the language :D Sep 10 '16 at 14:24

Python, 69 bytes

def f(k):b=bin(k)[::-1];return len(b)-2-(b.count('1')==2),b.find('1')


Tests are on ideone

Since non-valid input can do anything, we know that if the input has exactly 2 bits set it is the sum of those 2 powers of 2, and otherwise (if valid) it will be be a run of some number of bits (including the possibility of just 1 bit) and will be the difference between the next highest power of 2 than the MSB and the LSB set.

JAVA 7 ,142 ,140, 134 BYTES

This is my first post on PPCG!I would really appreciate for feedback on golfing tips
Thanks to frozen for saving 2 bytes

void f(long n){for(int i=-1,j;i++<31;)for(j=0;j++<34;){long a=1,x=a<<i,y=a<<j;if(x+y==n|y-x==n){System.out.println(j+" "+i);return;}}}


UNGOLF

void f(long n){
for(int i=-1,j;i++<31;)
for(j=0;j++<34;){
long a=1,x=a<<i,y=a<<j;
if(x+y==n|y-x==n){
System.out.println(j+" "+i);
return;
}
}
}


ideone

• Hi numberknot! Another wanderer from puzzling I see. It does not seem to work for 40=2**3+2**5, for example. Looking at it, I can't see why not, maybe I made a transcription error... Sep 10 '16 at 13:38
• @JonathanAllan Now it works fine.Actually the brackets were missing in this line if((a<<i)+(a<<j)==n|(a<<j)-(a<<i)==n) and thanks. Sep 10 '16 at 14:09
• Can´t you use a literal 1 instead of declaring a variable for it? Sep 10 '16 at 15:03
• @TItus if I use literal 1 then this testcase(17179867136 ) would not be possible because if you use literal 1 then java automatically assigned it an INT memory space. Sep 10 '16 at 15:13
• You can declare j together with i: for(int i=-1,j;[...] Sep 10 '16 at 15:36

Mathematica, 57 54 bytes

Saved 3 bytes thanks to LegionMammal978!

Do[Abs[2^a-#]==2^b&&Print@{a,b},{a,2Log@#+1},{b,0,a}]&


Actually prints out all1 appropriate pairs {a,b}. 2Log@#+1 is an upper bound for the largest a that can possibly appear when representing the input # (the tight upper bound is Log[2#]/Log[2] = 1.44... Log[#] + 1). Runs almost instantaneously on the test input, and in less than a quarter second (on my new but off-the-shelf computer) on 100-digit inputs.

1 Letting a start at the default value of 1 instead of 0 saves two bytes; it causes the output {0,0} to be missed when the input is 2, but finds the output {2,1} in that case, which is good enough.

• All* appropriate pairs? (Also, If[Abs[2^a-#]==2^b,Print@{a,b}] can be replaced with Abs[2^a-#]==2^b&&Print@{a,b} to save 3 bytes.) Sep 10 '16 at 21:40
• Nice observation, I get it! "All*" was a footnote, but it's clearer now. Sep 11 '16 at 0:18

MATL, 23 22 bytes

BnQ:qWtG-|ym)1)tG-|hZl


Explanation

B      % Implicit input. Convert to binary. Gives n digits
nQ:q   % Range [1 ... n+1]
W      % 2 raised to that, element-wise: gives [1 2 4 ... 2^(n+1)] (*)
tG-|   % Duplicate. Absolute difference with input, element-wise (**)
y      % Push a copy of (*)
m      % True for elements of (**) that are members of (*)
)      % Use as logical index to select elements from (*)
1)     % Take the first element. Gives power of the first result
tG-|   % Duplicate. Absolute difference with input. Gives power of the second result
hZl    % Concatenate. Take binary logarithm. Implicit display


Jelly, 11 10 bytes

;0+N&$BL€’  Applying the bit twiddling trick from the Python answer by @xnor Test it at TryItOnline All test cases are also at TryItOnline How? ;0+N&$BL€’ - main link takes an argument, k, e.g 15
;0         - concatenate k with 0, e.g. [15, 0]
$- last two links as a monad N - negate, e.g. -15 & - bitwise and, e.g. -15&15=1 since these two are called as a monad (one input) + - add, vectorises, e.g. [16,1] B - convert to binary, vectorises, e.g. [[1,0,0,0,0],[1]] L€ - length for each, e.g. [5,1] ’ - decrement, vectorises, e.g. [4,0]  Perl 6, 41 bytes {.base(2).flip~~/1[1+|0*]/;$/.to,$/.from}  ( Algorithm shamelessly copied from the Perl 5 answer ) Explanation: # bare block lambda with implicit parameter ｢$_｣
{
# turn into binary
# ( implicit method call on ｢$_｣ ) .base(2) # flip the binary representation .flip ~~ # smartmatch that against: / 1 # a ｢1｣ [ | 1+ # at least one ｢1｣ | 0* # or any number of ｢0｣ ] /; # returns a list comprised of # the position of the end of the match (larger of the two)$/.to,
# the position of the beginning of the match

• If I try 67 in echo strlen($n=decbin($argv[1]))-!!strpos($n,'01').'-+'[!$n[2]].strpos(strrev($n),49); it gives me back 6+0 which is 65 Sep 10 '16 at 17:08 • @JörgHülsermann: 67 has no solution; behaviour for no solution is undefined; so it does not matter what it prints for 67. Sep 10 '16 at 17:33 PHP ,117 Bytes if(preg_match("#^(1+|(10*1))0*$#",$b=decbin($k=$argv[1]),$t))echo($l=strlen($b))-($t[2]?1:0).",",$l+~strrpos($b,"1");  Extended version 4 Cases $l=strlen($b=decbin($k=$argv[1])); // Case 1: n=2(n-1)=n+n or n=n*(2-1)=2n-n if(preg_match('#^100*$#',$b))echo($l-2).'a+'.($l-2).':'.$l.'a-'.($l-1); // Case 2: n-m elseif(preg_match('#^1+0*$#',$b)){echo$l.'b-',strpos($b,"0")?$l-strpos($b,"0"):0;} // Case 3: n+m elseif(preg_match('#^10*10*$#',$b))echo ($l-1).'c+',$l-strrpos($b,"1")-1;
else echo "Nothing";


the short version union Case 1 and 3 and makes a Difference to Case 3 and in both versions Case 4 gives no output.