Wyzwanie, jeśli zdecydujesz się je zaakceptować, polega na K >= 1znalezieniu liczb całkowitych nieujemnych Ai B spełnieniu co najmniej jednego z dwóch następujących warunków:

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

Jeśli takiego nie ma, Aa BTwój program może zachowywać się w dowolny sposób. (Wyjaśnienie Ai Bmoże być równe.)

Przypadki testowe

Często istnieje wiele rozwiązań wielu, ale oto kilka:

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 

Ostatni przypadek testowy, 17179867136, należy uruchomić w niecałe 10 sekund na każdym stosunkowo nowoczesną maszynę. To jest golf golfowy, więc wygrywa najkrótszy program w bajtach. Możesz użyć pełnego programu lub funkcji.

Galaretka , 11 10 bajtów

;0+N&$BL€’

Zastosowanie sztuczki polegającej na kręceniu bitów z odpowiedzi Pythona autorstwa @xnor

Przetestuj w TryItOnline
Wszystkie przypadki testowe znajdują się również w TryItOnline

W jaki sposób?

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

Python 2, 43 bajty

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

Powiedz to n==2^a ± 2^bz a>b. Zatem największym współczynnikiem potęgi 2 njest 2^bi możemy go znaleźć za pomocą sztuczki bitowej 2^b = n&-n. To pozwala nam obliczyć 2^b + n, która jest równa albo 2^a + 2 * 2^balbo tylko 2^a. Każdy z nich ma tę samą długość bitów co a*. Tak więc, wyprowadzamy długości bitów n&-ni (n&-n)+nobliczone na podstawie długości ich reprezentacji binarnych. Python 3 jest o jeden bajt dłuższy dla parens w for k in(n,0)].

* Tyle że 2^a + 2^bz a==b+1ma jedną dłuższą długość bitów, ale to dobrze, ponieważ możemy to interpretować jako 2^(a+1)-2^b.

JavaScript (ES6), 73 bajty

(n,[s,f,z]=/^1+(.*1)?(0*)$/.exec(n.toString(2)))=>[s.length-!!f,z.length]

W przypadku odejmowania pierwsza liczba to liczba cyfr w reprezentacji binarnej, a druga liczba to liczba zer końcowych. W przypadku dodawania odejmujemy 1 od pierwszej liczby. Jeśli reprezentacją binarną są wszystkie 1, po których następują 0, to zakłada się przypadek dodania, w przeciwnym razie przyjmuje się przypadek odejmowania. 36-bajtowy port wersji @ xnor, który działa tylko dla B≤30 w JavaScript:

n=>[(l=Math.log2)(n+(n&=-n))|0,l(n)]

Perl, 52 49 32 bajty

Stare rozwiązanie (49 bajtów)

Obejmuje +1 dla -p

Podaj dane wejściowe STDIN:

pow2.pl <<< 17179867136

pow2.pl

#!/usr/bin/perl -p
$_=reverse sprintf"%b",$_;/()1(?:1+|0*)/;$_="@+"

Jednak użycie algorytmu xnor i dodanie skrętu daje 32 bajty:

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

Tylko kod:

say 13/9*log|0for$;=$_&-$_,$_+$

Cierpi na tym poważny błąd zaokrąglania, ponieważ 13/9 = 1.444...jest nieco powyżej 1/log 2 = 1.44269...( logsam również ma błąd zaokrąglania, ale jest o tyle mniejszy, że możemy go zawrzeć w analizie 13/9). Ale ponieważ każdy 2**big - 2** smallzostanie poprawiony 2** bigprzed dziennikiem, nie ma to znaczenia, a obliczenia dla 2**big + 2 * 2**smallskrócenia zostają zmniejszone, więc jest również bezpieczny. A po drugiej stronie zakresu 2**n+2**(n-1)nie zwiększa się wystarczająco w zakresie [0,64](nie mogę poprawnie i tak obsługuje więcej niż zakres liczb całkowitych ze względu na użycie &), aby doprowadzić do błędnego wyniku (multiplikator 1.5byłby jednak zbyt daleki dla dużych liczb).

Brachylog , 23 bajty

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

Wypróbuj online!

Jest to znacznie szybsze niż wymagane, np . W TIO jest to nadal poniżej 10 sekund .

Wyjaśnienie

Jest to w zasadzie bezpośrednia transkrypcja formuły bez optymalizacji:

,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

Python, 69 bajtów

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

Testy są na ideone

Ponieważ nieprawidłowe dane wejściowe mogą zrobić wszystko, wiemy, że jeśli dane wejściowe mają ustawione dokładnie 2 bity, jest to suma tych 2 mocy 2, a w przeciwnym razie (jeśli jest poprawna) będzie to ciąg pewnej liczby bitów (w tym możliwość tylko 1 bit) i będzie różnicą między następną najwyższą mocą 2 niż zestaw MSB i zestaw LSB.

JAVA 7,142 ,140, 134 BYTES

To jest mój pierwszy post na PPCG! Naprawdę byłbym wdzięczny za opinie na temat wskazówek golfowych
Dzięki zamrożeniu za oszczędność 2 bajtów

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

Mathematica, 57 54 bajtów

Zaoszczędzono 3 bajty dzięki LegionMammal978!

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

Właściwie drukuje wszystkie ¹ odpowiednie pary {a, b}. 2Log@#+1jest górną granicą największej, aktóra może pojawić się podczas reprezentowania danych wejściowych #(ścisła górna granica to Log [2 #] / Log [2] = 1,44 ... Log [#] + 1). Działa niemal natychmiast na wejściu testowym, aw mniej niż kwadrans (na moim nowym, ale gotowym komputerze) na wejściach 100-cyfrowych.

¹ Letting apoczątek w domyślnej wartości 1 zamiast 0 zapisuje dwa bajty; powoduje, że wyjście {0,0} jest pomijane, gdy wejście ma wartość 2, ale w takim przypadku znajduje wyjście {2,1}, co jest wystarczająco dobre.

MATL , 23 22 bajtów

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

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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

Perl 6 , 41 bajtów

{.base(2).flip~~/1[1+|0*]/;$/.to,$/.from}

(Algorytm bezwstydnie skopiowany z odpowiedzi Perla 5 )

Wyjaśnienie:

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

Stosowanie:

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

PHP, 73 bajty

Mogłem skopiować rozwiązanie Pyhton 2 Jonathana dla 54 bajtów (+13 narzutu),
ale chciałem wymyślić coś innego.

zapisz do pliku, a następnie uruchom za pomocą phplub php-cgi.

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

drukuje ai boddzielone znakiem podkreślenia, wszystko bez rozwiązania.

charakterystyczne rozwiązanie, 96 bajtów

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

odbitki ai boddzielone znakiem podkreślenia; jedyny znak podkreślający brak rozwiązania.

Mówi nawet o operacji dla 11 kolejnych bajtów:
wystarczy wymienić pierwszy znak podkreślenia w kodzie na '-+'[!$m[2]].

PHP, 117 bajtów

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

Rozszerzona wersja 4 walizki

$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";

krótka wersja połączenia Case 1 i 3 i robi różnicę w stosunku do Case 3, aw obu wersjach Case 4 nie daje wyników.