27
\$\begingroup\$

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.

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

12 Answers 12

3
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
15
\$\begingroup\$

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.

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

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)]
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ @ETHproductions Sure, but I golfed it down to 36. \$\endgroup\$ – Neil Sep 10 '16 at 14:08
  • \$\begingroup\$ My bad, I thought that the 36-byte version didn't work for the 17 billion test case. \$\endgroup\$ – ETHproductions Sep 10 '16 at 17:39
  • \$\begingroup\$ @ETHproductions It doesn't, but then neither did your port, as I recall (comment since deleted, sigh), since it used bitwise operations. \$\endgroup\$ – Neil Sep 10 '16 at 18:24
  • \$\begingroup\$ 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). \$\endgroup\$ – ETHproductions Sep 10 '16 at 18:27
  • \$\begingroup\$ @ETHproductions Aha, so more accurately they work when the second result is 30 or less. \$\endgroup\$ – Neil Sep 10 '16 at 18:53
6
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ It looks like this challenge was made for the language :D \$\endgroup\$ – Conor O'Brien Sep 10 '16 at 14:24
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – Jonathan Allan Sep 10 '16 at 13:38
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Numberknot Sep 10 '16 at 14:09
  • \$\begingroup\$ Can´t you use a literal 1 instead of declaring a variable for it? \$\endgroup\$ – Titus Sep 10 '16 at 15:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Numberknot Sep 10 '16 at 15:13
  • 1
    \$\begingroup\$ You can declare j together with i: for(int i=-1,j;[...] \$\endgroup\$ – Frozn Sep 10 '16 at 15:36
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – LegionMammal978 Sep 10 '16 at 21:40
  • \$\begingroup\$ Nice observation, I get it! "All*" was a footnote, but it's clearer now. \$\endgroup\$ – Greg Martin Sep 11 '16 at 0:18
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Jörg Hülsermann Sep 10 '16 at 17:08
  • \$\begingroup\$ @JörgHülsermann: 67 has no solution; behaviour for no solution is undefined; so it does not matter what it prints for 67. \$\endgroup\$ – Titus Sep 10 '16 at 17:33
0
\$\begingroup\$

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.

| improve this answer | |
\$\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.