Sum or difference of two powers of two

Question

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.

Answer 1

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.

Answer 2

JavaScript (ES6), 73 bytes

(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)]

Answer 3

Perl, 52 49 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).

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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 all¹ 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.

¹ 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.

Answer 8

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]

Answer 9

MATL, 23 22 bytes

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

Try it online! Or verify all test cases.

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

Answer 10

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
  $/.from
}

Usage:

# give it a lexical name for clarity
my &bin-sum-diff = {.base(2).flip~~/1[1+|0*]/;$/.to,$/.from}

say bin-sum-diff 15; # (4 0)
say bin-sum-diff 16; # (5 4)

say bin-sum-diff 20; # (4 2)
# 2**4==16, 2**2==4; 16+4 == 20

say bin-sum-diff 40; # (5 3)
say bin-sum-diff 264; # (8 3)
say bin-sum-diff 17179867136; # (34 11)

Answer 11

PHP, 73 bytes

I could have copied Jonathan´s Pyhton 2 solution for 54 bytes (+13 overhead),
but wanted to come up with something different.

save to file, then execute with php or php-cgi.

<?=strlen($n=decbin($argv[1]))-!!strpos($n,'01')._.strpos(strrev($n),49);

prints a and b separated by an underscore, anything for no solution.

distinctive solution, 96 bytes

<?=preg_match('#^(10*1|(1+))(0*)$#',decbin($argv[1]),$m)?strlen($m[0])-!$m[2]._.strlen($m[3]):_;

prints a and b separated by an underscore; a sole underscore for no solution.

It even tells you the operation for 11 more bytes:
Just replace the first underscore in the code with '-+'[!$m[2]].

Answer 12

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.