APL(NARS), 54 chars

{(1∧⍵),2⍟÷1∨⍵}∘{⍵=0:0⋄(⍵>0)∧⍵≤.5:2÷⍨∇⍵÷1-⍵⋄k-∇⍵-⍨k←⌈⍵}

I copied the algoritm from Anders Kaseorg answer to this question.

Test:

  f←{(1∧⍵),2⍟÷1∨⍵}∘{⍵=0:0⋄(⍵>0)∧⍵≤.5:2÷⍨∇⍵÷1-⍵⋄k-∇⍵-⍨k←⌈⍵}
  f ¯1r2
¯1 1 
  f 0r1
0 0 
  f 1r1
1 0 
  f 1r2
1 1 
  f 1r1
1 0 
  f ¯1r2
¯1 1 
  f 2r1
2 0 
  f 1r3
1 2 
  f 1r8
1 7 
  f 2r5
3 3 
  f 8r5
13 3 
  f 58r27
1033 9 
  f 30r73
399 10 
  f 144r89
853 9 
  f ¯17r77
¯767 13 
  f ¯17r99
¯133 12 
  f 355r113
12648447 22 
  f 16000r1
16000 0 

Scala 3, 238 186 bytes

Modified from @loopy walt's answer.

\$ \color{black}{\text{In scala, it's weird to mimic `%` `//` of python}} \$

/*
Python's % operator returns a result with the same sign as the divisor, and // rounds towards negative infinity.

In Scala, % and / don't behave the same way. The % operator returns a result with the same sign as the dividend, and / performs truncating division, rounding towards zero.
*/


def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b

def pythonDiv(a: Int, b: Int): Int = {
  if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b
  else if (a % b == 0) a / b
  else a / b - 1
}

Golfed version. Attempt this online!

Saved 52 bytes thanks to the comment of @ceilingcat

type T=Int;def f(n:T,d:T)={@annotation.tailrec def g(n:T,d:T,s:T,N:T,D:T):(T,T)=if(d!=0)g(d,n%d,-s,(N<<n/d)+s,D+n/d)else(N,D);val r=(n%d+d)%d;g(d-r,r,1,if(n*d>0|n%d==0)n/d else n/d-1,0)}

Ungolfed version. Attempt this online!

import scala.io.Source
object Main {
  def f(n: Int, d: Int) = {
    @annotation.tailrec
    def g(n: Int, d: Int, s: Int, N: Int, D: Int): (Int, Int) = {
      // println(s"$n $d $s $N $D")
      if (d != 0) g(d, n % d, -s, (N << (n / d)) + s, D + (n / d)) else (N, D);
    }
    def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b

    def pythonDiv(a: Int, b: Int): Int = {
      if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b
      else if (a % b == 0) a / b
      else a / b - 1
    }

    val q = pythonDiv(n, d);
    val r = pythonMod(n, d);
    g(d - r, r, 1, q, 0)
  }

  def main(args: Array[String]): Unit = {
    val lines = Source.stdin.getLines().toList

    for (line <- lines) {
      val Array(i, o) = line.split("->")
      val nums = i.split("/").map(_.trim.toInt)
      val result = f(nums(0), nums(1))
      println(s"${nums.mkString("/")}, $result, $o")
    }
  }
}

Pyth, 46 bytes

M?tH+/GHgH%GH]GJtstKgEE+*hK^2JaF_m^2-Jtsd._tKJ

Try it online!

Explanation

First we define g(G,H) to find the continued fraction of its input.

M                  # define g(G,H)
 ?tH               # if (H != 1):
    +/GH           #   prepend floor(G/H) to
        gH%GH      #   recurse on g(H, G%H)
                   # else:
             ]G    #   return [G]

Then we compute the function

    KgEE                           # assign K to g applied to two inputs
Jtst                               # assign J to sum(K[:-1]) - 1
                          ._tK     # all prefixes of K[:-1]
                  m                # map on lambda d
                   ^2              #   2 to the power of
                     -J            #   J minus
                       tsd         #   sum(d) - 1
               aF_                 # take the alternating sum
        +                          # add to this
            ^2J                    # 2 ^ j
         *hK                       # times K[0]
                              J    # print(J)

Jelly, 28 bytes

Ḋ;%/ƊẠпṖ:/€ḢW+Ṭ€NÐeFƊƲL’ṭḄƲ

A monadic Link that accepts a pair of integers, [numerator, denominator], and yields a pair of integers, [numerator, denominator's exponent].

Try it online!

How?

Ḋ;%/ƊẠпṖ:/€ḢW+Ṭ€NÐeFƊƲL’ṭḄƲ - Link: pair of integers = [N, D]
      п                     - collect while...
     Ạ                       - ...condition: all truthy - i.e. while no zero present
    Ɗ                        - ...do: last three links as a monad - f(current=[n, d]):
Ḋ                            -          dequeue -> [d]
   /                         -          reduce ([n, d]) by:
  %                          -            modulo -> n%d
 ;                           -          concatenate -> [d, n%d]
        Ṗ                    - pop - remove the final result (with a zero in)
          /€                 - reduce each by:
         :                   -   integer division -> continued fraction part list
                      Ʋ      - last four links as a monad - f(Parts=that):
            Ḣ                -   head -> remove and yield the integer part
             W               -   wrap (the integer part) in a list
                     Ɗ       -   last three links as a monad - f(remaining parts):
               Ṭ€            -     untruth each (e.g. 4 -> [0,0,0,1])
                 NÐe         -     negate those at even indices (the 2nd, 4th, ...)
                    F        -     flatten
              +              -   ([integer part]) add (that) (vectorises) - adds the integer
                                     part to the first one. If none just gets [integer part]
                           Ʋ - last four links as a monad - f(A=that):
                       L     -   length (A)
                        ’    -   decrement -> the denominator's exponent
                          Ḅ  -   convert (A) from base two -> the numerator
                         ṭ   -   tack -> [numerator, denominator's exponent]

julia, 111 bytes

Expects a single argument of type Rational{Int64}

This approach traverses the Stern-Brocot tree for \$\mathrm{mod}(p,1)\$, adding \$1/2^k\$ at the \$k\$-th recursion whenever we take a right branch in the tree.

The case where \$p \notin (0, 1]\$ is handled in the default arguments.

m(p,L=[0,1],U=[1,0],q=mod1(p,1),r=p-q,s=0,M=//(L+U...),g=q>=M,l=r+g)=q==M ? (l,s) : m(0,L+g*U,U+L-g*L,q,2l,s+1)

Attempt This Online!

PARI/GP, 67 bytes

x->s=0;[(x\1+2*sum(i=2,#r=contfrac(x),(-1)^i/2^s+=r[i]))<<s-=!!s,s]

Attempt This Online!

JavaScript (ES6), 88 bytes

Expects (p)(q) for \$x=p/q\$. Returns [a,b].

This is heavily based on loopy walt's answer.

p=>g=(q,s=p<(b=0)?p/(p=-p):1,a=p/q,d=p%=q,n=q-p)=>d?g(b+=n/d|0,-s,s+=a<<n/d,n%d,d):[a,b]

Try it online!

Python, 95 bytes

lambda n,d:g(d-n%d,n%d,1,n//d,0)
g=lambda n,d,s,N,D:d and g(d,n%d,-s,(N<<n//d)+s,D+n//d)or(N,D)

Attempt This Online!

Rather verbose implementation. Essentially calculates the cf (by Euclidean algo) and converts the terms on the fly.

Python 3.8, 95 bytes

q=lambda x,y,k=0:y>=2*x>0and q(x,y-x,k+1)or(x and-(-x//y<<(r:=q(-x%y,y))[1])-r[0],x and r[1]+k)

Try it online!

How it works

Uses the recurrence

\begin{align*} ?(0) &= 0, \\ ?(x) &= \frac{?{\left(\frac{x}{1 - x}\right)}}{2} \quad\text{if }0 < x ≤ \frac12, \\ ?(x) &= ⌈x⌉ - {?(⌈x⌉ - x)}. \end{align*}

Factor + koszul math.continued-fractions, 156 154 bytes

[ dup sgn swap abs 1vector [ dup last ratio? ] [ dup next-approx ] while
unclip -rot cum-sum vneg [ -1^ 2 rot 1 + ^ * ] map-index sum * + >fraction log2 ]

Try it online!

                      ! -17/99
dup                   ! -17/99 -17/99
sgn                   ! -17/99 -1
swap                  ! -1 -17/99
abs                   ! -1 17/99
1vector               ! -1 V{ 17/99 }
[ dup last ratio? ]   ! -1 V{ 17/99 } [ dup last ratio? ]
[ dup next-approx ]   ! -1 V{ 17/99 } [ dup last ratio? ] [ dup next-approx ]
while                 ! -1 V{ 0 5 1 4 1 2 }
unclip                ! -1 V{ 5 1 4 1 2 } 0
-rot                  ! 0 -1 V{ 5 1 4 1 2 }
cum-sum               ! 0 -1 V{ 5 6 10 11 13 }
vneg                  ! 0 -1 V{ -5 -6 -10 -11 -13 }
[ -1^ 2 rot 1 + ^ * ] ! 0 -1 V{ -5 -6 -10 -11 -13 } [ -1^ 2 rot 1 + ^ * ]
map-index             ! 0 -1 { 1/16 -1/32 1/512 -1/1024 1/4096 }
sum                   ! 0 -1 133/4096
*                     ! 0 -133/4096
+                     ! -133/4096
>fraction             ! -133 4096
log2                  ! -133 12

Charcoal, 63 bytes

ＮθＮη≔÷θηζＷ﹪θη«≔ηθ≔ιη⊞υ⁻÷θη¬υ»Ｆ﹪Ｌυ²⊞⊞Ｏυ⊖⊟υ¹Ｉ⟦⁺×ζＸ²Συ⍘⭆υ×Ｉ﹪κ²ι²Συ

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input the numerator and denominator.

≔÷θηζ

Calculate the integer part of the fraction.

Ｗ﹪θη«≔ηθ≔ιη⊞υ⁻÷θη¬υ»

Calculate the rest of the continued fraction, except decrement the first value.

Ｆ﹪Ｌυ²⊞⊞Ｏυ⊖⊟υ¹

If the fraction has odd length then decrement the last value and append a 1.

Ｉ⟦⁺×ζＸ²Συ⍘⭆υ×Ｉ﹪κ²ι²Συ

Transform the fraction into run-length-encoded binary and convert from binary to decimal, adding on the original integer part with an appropriate shift, which is also the second output value.

Python3, 217 bytes:

C=lambda n,d:[n//d]+C(d,n-d*(n//d))if d else[]
def f(N,d):n=abs(N);c=C(n,d);k=[(c[0],0)]+[(pow(-1,i+1),sum(c[1:i+1])-1)for i in range(1,len(c))];b=max(B for _,B in k);return([1,-1][N<0]*sum(2**(b-B)*N for N,B in k),b)

Try it online!

Wolfram Language (Mathematica), 77 or 124 bytes

(s=Sign@#;{s Numerator@#,Log[2,Denominator@#]}&@MinkowskiQuestionMark@Abs@#)&

Try it online!

Or without overkill builtin:

(s=Sign@#;c=ContinuedFraction@Abs@#;{s Numerator@#, Log[2,Denominator@#]}&@(r=c[[1]];t=-1;Do[t=-t/2^e;r+=2t,{e,Rest@c}];r))&

Try it online!

Haskell, 186 bytes

import Data.Ratio
c r=let f=floor r;d=r-f%1 in if d==0 then[f]else f:c(1/d)
m(a:b)=a%1-2*sum[(-1)^i/2^sum(take i b)|i<-[1..length b]]
p x=(numerator x,until((denominator x==).(2^))(1+)0)

Try it online!