[Question]
  [
[Fibonacci coding](https://en.wikipedia.org/wiki/Fibonacci_coding) is a universal code, which can encode positive integers of any size in an unambiguous stream of bits.
To encode an integer \$ n \$:
* Find the largest Fibonacci number less than or equal to \$ n \$; subtract this number from \$ n \$, keeping track of the remainder
* If the number subtracted was the \$ i \$th Fibonacci number \$ F(i) \$, put a \$ 1 \$ at index \$ i−2 \$ in the code word (counting the left most digit as index \$ 0 \$)
* Repeat the previous steps, substituting the remainder for \$ n \$, until a remainder of \$ 0 \$ is reached
* Append a final \$ 1 \$
Alternately explained:
* Find the [Zeckendorf representation](https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem) of \$ n \$ (the list of unique non-consecutive Fibonacci numbers which sum to it)
* For all the Fibonacci numbers up to and including \$ n \$, excluding \$ 0 \$ and the first \$ 1 \$, append a bit \$ 0 \$ or \$ 1 \$ according to whether or not they appear in \$ n \$'s Zeckendorf representation
* Strip any trailing \$ 0 \$s and append a final \$ 1 \$
Your task is to, given a positive integer, output the bits of its Fibonacci coding.
## Test Cases
```
Input    Output
-------------------------------------------
1        11
2        011
3        0011
4        1011
11       001011
12       101011
13       0000011
14       1000011
65       0100100011
610      000000000000011
8967     00001010101010010011
8039213  0010010010100010001001001000001011
```
(if your code cannot compute this high in reasonable time, that is fine)
## Rules
* Output should be as a string or array of \$ 1 \$s-and-\$ 0 \$s or booleans (but not just any truthy or falsey value)
* You may output the bits in reverse if that is more convenient (although this behaviour must be consistent)
* You may use [any sensible I/O format](https://codegolf.meta.stackexchange.com/q/2447)
* [Standard loopholes](https://codegolf.meta.stackexchange.com/q/1061) are forbidden
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins
  
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 13 bytes
```
@!X¤øB}iU
¤ÔÄ
```
Explanation:
```
@!X¤øB}iU 
@     }iU // Get the U-th (input) number
 !        // which doesn't have
    øB    // "11" in its
  X¤      // binary representation
¤ÔÄ
¤         // Take that number's binary representation,
 Ô        // reverse it
  Ä       // and add one to the end.
```
[Try it here.](https://ethproductions.github.io/japt/?v=1.4.6&code=QCFYpPhCfWlVCqTUxA==&input=NjU=)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~51~~ 50 bytes
```
k;f(n){for(k=0;n-=!(++k&k/2););n=log2(k);k+=2<<n;}
```
[Try it online!](https://tio.run/##XVHdboIwFL73Kc5IXIqUKJXfVHaz7CmmFwaLI2g1lGRkhlcf@1AkOpIW@v2dnkPm7rOs60qZM21f8lPFynQhtZu@MMcpX8u5sKUtdXo47QUrbVk6qVittGy747bQzJ5cJoSn0DXVytTmc9MfU7p4nASnJSefU8Ap5BRxijklnLwFFngPAg8KD5Kw1/REnIRRK8dQ1ZxVVqsdchG6vAbdfQI@AZ8A5iPaR3aAiAB8AD4BnqBqFIe9OIjwioUfBuFQIPvaVjPsKitVdatgrZsPsW6Sd6zA4vR4XlqDD2Mi1t@u0DvVwLaQw@eKTPGjTjm739ueD8BsRCQ5zlVt02149141km5DvNIb@cQasP1PekYV0HFG/23nCpKcWdMduW@EfWrWGk1pToaPfZs0VZshtp203W@WH7Z707mHY@d@/wE "C (gcc) – Try It Online")
Uses the formula from [Etheryte](https://codegolf.stackexchange.com/users/16484/etheryte)'s [Japt answer](https://codegolf.stackexchange.com/a/222687/9481).  
Returns the Fibonacci code word for input \$n\$ in reversed binary.
### Explanation
```
k;f(n){                           // function taking an integer n > 0
       for(k=0;             ;);   // loop over values of integer k
                                  // starting at 1 (because of the bump)  
               n                  // until n is zero
                -=!(       )      // subtracting 1 from n when...
                    ++            // (bump k at the start of each loop)
                      k&k/2       // ...there's no 2 consecutive 1 bits in k  
                                  // k is now the nth integer without   
                                  // any 2 consecutive 1 bits
       n=log2(k);                 // get the number of bits in k by
                                  // converting  its log2 to an int   
       k+=2<<n;                   // add a 1 bit just above k's most   
                                  // significant bit and return k   
}
```
[Answer]
# [Haskell](https://www.haskell.org/), 76 bytes
```
1#2
(u#v)x|x<v=["11"|x==u]|z<-u+v=map('0':)(v#z$x)++map("10"++)(z#(z+v)$x-u)
```
[Try it online!](https://tio.run/##FcrRCoIwFADQ9z7DCW7sGrubmYb7hL7AJIZkSSqSbQzx21v4ejgvs7wfwxA6fQtI5IFa4pjffOV0HSFGm9faNttapZY7PZqZJiK5MOrIGnvG@S4RiohzRldCV@5Y7FPLwmj6af/XO50//fQ9dqxGkKAgA0RACagAM8hPkKOAoszPUAhVSlRN@LXdYJ5LSNt5/gM "Haskell – Try It Online")
Outputs a string of `0`'s and `1`'s wrapped in a singleton list (e.g. `["001011"]`).
## How?
* `(u#v)x`: we want this function to return a list of all the possible Fibonacci encodings for `x` using only Fibonacci numbers greater or equal than `u`; we further assume that `u` and `v` are consecutive fibonacci numbers (with `u<v`). It is well known that, if such an encoding exists, than it is unique (this follows from the uniqueness of the Zeckendorff representation), so the length of the list `(u#v)x` will be at most 1. For instance, `(3#5)11==["1011"]`, since `11=3+8`.
* `|x<v=["11"|x==u]`: if `x<v` then the encoding only exists if `x==u`. If this is the case we return `["11"]`, otherwise we return the empty list.
* `|z<-u+v=`: otherwise, let `z=u+v` be the next Fibonacci number. We have two choices.
	+ `map('0':)(v#z$x)`: we try to encode `x` without using `u`. In this case, the encoding will be contained in `(v#z)x`, and we prepend a `'0'` to denote the fact that we didn't take `u`.
	+ `++map("10"++)(z#(z+v)$x-u)`: we try to encode `x` using `u`. In this case, `"10"` denotes that we take `u` and we don't take `v`. For this choice to be valid, we must also find an encoding of `x-u` using only Fibonacci numbers from `z` onwards (notice that `z+v` is the Fibonacci number after `z`).
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~21~~ 12 bytes
Using [Etheryte](https://codegolf.stackexchange.com/users/16484/etheryte)'s observation from their [Japt](https://codegolf.stackexchange.com/a/222687/53748) answer is much terser and more efficient to boot (it may be possible in even less, let's see...)
```
1BSƝỊẠƲ#ṪB1;
```
A monadic Link accepting a positive integer that yields a list of `1`s and `0`s (in reversed order as allowed in the rules).
**[Try it online!](https://tio.run/##ASEA3v9qZWxsef//MUJTxp3hu4rhuqDGsiPhuapCMTv///82MTA "Jelly – Try It Online")**
---
A faster 12 byter:
```
1Ḥ^:3ƲƑ#ṪB1;
```
[Try it online!](https://tio.run/##AR8A4P9qZWxsef//MeG4pF46M8ayxpEj4bmqQjE7////NjEw)
### How?
```
1Ḥ^:3ƲƑ#ṪB1; - Link: positive integer, n
1      #     - set k=1 and increment to collect the first n ks for which:
      Ƒ      -   (k) is invariant under?:
     Ʋ       -     last four links as a monad, f(k):
 Ḥ           -       double (k)
  ^          -       (2k) bitwise-XOR with k -> x
    3        -       three
   :         -       (x) integer divide (3)
        Ṫ    - tail
         B   - to binary
          1  - one
           ; - (1) concatenate with (the binary list)
```
---
Original 21:
This is (a) extremely inefficient and (b) almost certainly not the right way to get the tersest code, so I~~'ll~~ was planning to come back to it after work...
```
‘ÆḞ€ḊðŒPS⁼¥Ƈ⁹Ḣ⁸iⱮðṬ;1
```
A monadic Link accepting a positive integer that yields a list of `1`s and `0`s.
[Try it online!](https://tio.run/##ATsAxP9qZWxsef//4oCYw4bhuJ7igqzhuIrDsMWSUFPigbzCpcaH4oG54bii4oG4aeKxrsOw4bmsOzH///8xNA "Jelly – Try It Online")
[Answer]
# JavaScript (ES6), ~~46~~ 44 bytes
*Based on [@Etheryte's insight](https://codegolf.stackexchange.com/a/222687/58563).*
Returns a string of bits in reverse order.
```
f=(n,k)=>k&k/2||n--?f(n,-~k):1+k.toString(2)
```
[Try it online!](https://tio.run/##bc/BDoIwDAbgu0@xk9miY@tADyboQ/gEBBnBks3Awonw6lMPDM3WY7/@bfqspmqsh@7luLGPxntdUnNEVl5xj0LNs@H8pj8tviC7wAEzZ@9u6ExLFfO1NaPtm6y3LdUUCGGMCEEAdv@iVpER5YFiK8LC2AC2XELVlkxoHrIycRaKEE7x@RSe@d5OTYD82b8WgH8D "JavaScript (Node.js) – Try It Online")
### Commented
```
f = (             // f is a recursive function taking:
  n,              //   n = input
  k               //   k = counter, initially undefined (coerced
) =>              //       to 0 for bitwise operations)
  k & k / 2 ||    // yield a truthy value right away if there are
                  // at least 2 consecutive bits set in k
    n--           // otherwise, yield n and decrement it afterwards
  ?               // if either statement above is truthy:
    f(n, -~k)     //   do a recursive call with k + 1
  :               // else:
    1 +           //   stop and return a leading '1'
    k.toString(2) //   followed by the binary representation of k
```
---
# [JavaScript (Node.js)](https://nodejs.org), ~~109~~ 105 bytes
*Based on the challenge description.*
Expects a BigInt. Returns a string of bits in reverse order.
```
f=(n,k=m=0n)=>n?(g=(i,x=0n,y=1n)=>i?g(~-i,z=y,x+y):y)(k)>n?f(n-z,0n,m|=1n<<k-2n):f(n,-~k):1+m.toString(2)
```
[Try it online!](https://tio.run/##bZBBbsIwEEX3PUWWM8IGj0NpiXA5RE@AKIlMyBhBhAiquHpqUgpybXs2M//5@9vb1Wl1XB/svpXsvjZ9XxpgUZvGKEbzwUuoDFhx9q3oDN1mdlnBVVpxMZ04jzosOoQaPVoCy4vwYPPtycWilpqx8FMhrzUWNGrGrftsD5Yr0NivHR/dbjPeuQpKIM6GhZhNJhnRSyjrQFaRnod6DExD/xige4KHQwLRHHokkDx0UYkoNA1tUszsNfChW54URor/Xfe3IvZ9PnvjgKXHHio6oPK59g96/shvDUnUs79bUf8D "JavaScript (Node.js) – Try It Online")
[Answer]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 51 bytes
Another based on [Etheryte](https://codegolf.stackexchange.com/users/16484/etheryte)'s [Japt answer](https://codegolf.stackexchange.com/a/222687/53748)
```
f=lambda n,k=0:-n*f'1{k-1:b}'or f(n-(k&k//2<1),k+1)
```
**[Try it online!](https://tio.run/##PY9hboMwDIX/c4onTVpJF1bcboyicRjoQhMREpSYVdW0s7OwSbP0ZH227GfPd9beneo5rOvQ2m7qPzo4ObZlU7j9sKOvsaCm/975gCF3RT4@jofD8Z2EHJ9IrGaafWDEe8ySnqPioC5LiMY7aybDeU3nSgAPYG0iOmv9LYJV5LaiEuxx8dNsFSuJfuG/Tl2d33Az1iKq69AtlqFVUFCfyqU6a2hz1VDOLyn9G@LXMcuGdOu2B8YhJ4mjxEniRYISUCJKSImr1yQqRZMhxRyM43wblOnVLQux/gA "Python 3.8 (pre-release) – Try It Online")**
[Answer]
# Scala, 69 bytes
Based on [Etheryte's amazing answer](https://codegolf.stackexchange.com/a/222687/95792)
```
"1"+Stream.from(0).map(_.toBinaryString).filter(!_.contains("11"))(_)
```
[Try it online!](https://scastie.scala-lang.org/96OmivWtTEqg7FrcpfKpRw)
Outputs a String (reversed)
## Original answer, 123 bytes
```
n=>(f.takeWhile(n>=_):\(n,1::Nil)){case(x,n->c)=>if(x>n)(n,0::c)else(n-x,1::c)}._2
def f:Stream[Int]=1#::f.scanLeft(2)(_+_)
```
[Try it online!](https://scastie.scala-lang.org/gewTQsoiTVGaI1vrTKLfMg)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 14 bytes
```
∞ʒb11å>}s<èb1ì
```
[Try it online!](https://tio.run/##yy9OTMpM/f//Uce8U5OSDA0PL7WrLbY5vCLJ8PCa///NDA0A "05AB1E – Try It Online")
```
∞ʒb11å>}s<èb1ì  # full program
         <è     # push the...
        s       # implicit input...
         <è     # -th...
∞               # natural number...
 ʒ     }        # which...
      >         # does not...
     å          # contain...
   11           # literal...
  b             # in binary...
           b    # converted to binary...
            1   # with literal...
             ì  # prepended
                # implicit output
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 16 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
âî}g♥▼«zΩ╥;QbB]╔
```
[Run and debug it](https://staxlang.xyz/#p=838c7d67031fae7aead23b5162425dc9&i=1%0A2%0A3%0A4%0A11%0A12%0A13%0A14%0A65%0A610%0A8967%0A8039213%0A&m=2)
Based on Etheryte's observation, which shaved a off a ton of bytes. [Check out their answer!](https://codegolf.stackexchange.com/a/222687/80214)
## Explanation
```
Z{|B.11#!}{ge|B'1s+
Z                   push 0 under the input(counter)
           ge       generator: find the first n elements, return the last
          {         empty block: get the next element by incrementing
 {       }          filter:
  |B                base2 string
    .11#!           has 0 occurrences of "11"?
               '1s+ prepend a 1 to it(r'1+ also works for valid output)
```
# [Stax](https://github.com/tomtheisen/stax), 29 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
é½Æ½┼≥╦◘½}○└╩►à«ôæ→¢ûU«½*≈ø»▀
```
[Run and debug it](https://staxlang.xyz/#p=82ab92abc5f2cb08ab7d09c0ca1085ae93911a9b9655aeab2af700afdf&i=1%0A2%0A3%0A4%0A11%0A12%0A13%0A14%0A65%0A610%0A8967%0A8039213%0A&m=2)
Pretty big.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 43 bytes
```
n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)
```
[Try it online!](https://tio.run/##jU49b8IwEN39K7xUOTdg4oTSIupsHTp1YAQkotSkQcE2iWEp/e3pJYBB6tKzZb2Pu3feZsesyevSuqE2n6rdyFbLFAppZapf7ekUPxZgw/1gLy0LQaegHxAxBnspWOuopGvyru3BUayPg0NEhv8vIuilhCDxFUdIEk86NvZtHRPi5vU8vrk9T7wf9eNi7BvOwuTJr@oyzpqI7qauhcbLdPLsDeFPf9GNkmncbYyu2jkwuvHLnCBr7upyB4w3tiodBEsdIK7KXEHM@C6zUFGZ0gqhy79gtJyHo4KxGXF8Y@q3DDVYlAOqVqzr@yaU5kY3plK8MgWEaG3wZdyZOW7SBcYO6IJz/kde8VodVd0o/M3WlBqCADMlVbjth83aXw "JavaScript (Node.js) – Try It Online")
It returns an integer whose binary form is reversed Fibonacci Encoding.
```
// I have a code for base 2 convention
n=>(g=p=>n<p  2*g(       )+(n>(n%=p)))(   )
// I have a code for Fibonacci sequence
n=>(g=p=>       g(p+q,q=p)           )(q=1)
// Boom, Fibonacci base convention
n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 12 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Based off Etheryte's solution, posted with permission.
```
_øB ªU´}f¤ÔÄ
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=X/hCIKpVtH1mpNTE&input=NjU)
[Answer]
# [jq](https://stedolan.github.io/jq/) (74 bytes)
Since shortness is the goal ...
```
def f:def i:.,(i|[0]+.,[1]+.);nth(.-1;[1]|i|select(index([1,1])|not))+[1];
```
Example:
```
65|f #=> [0,1,0,0,1,0,0,0,1,1]
```
[Try it online](https://jqplay.org/s/q8bwV3z8nOW)
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 127 bytes
```
(f@n_:=(k=1;While[(F=Fibonacci)[++k]<=n];k-1);s=Table[0,f[t=#]];(s[[#]]=1)&/@(f/@NestWhileList[#-F@f@#&,t,#>0&]);RotateLeft@s)&
```
[Try it online!](https://tio.run/##Hcy9CsIwFEDhVxEKJcEr7W21/sRIpk4iIoJDCBJLoqFawdxNfPYoTmf5OA9LN/ewFDqbrjIxr4bzSrJeojjdwt1p1so2XJ6D7brA9Xjcm7UcjOgnyEWUR3v5mRK8JpkZI1jU@leJPC8U84XauUj/0TZE0tmkVV5lORBkmzI3XByeZMltnScVeZ72rzDQqFDXQr0RKqhhCoiAFWANOIVmBg2WsFg2c1iU9bLC@pPSFw "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Haskell (GHC)](https://www.haskell.org), ~~118~~ 104 bytes
```
x@(_:v)=1:scanl(+)1x
f n=snd(foldr(\v(x,l)->if v<=x then(x-v,1:l)else(x,0:l))(n,[])$fst$span(<=n)v)++[1]
```
[Try it online!](https://tio.run/##RVFba4MwFH73VxxCoQmNYNqtW6WRwZ4Kuzz0aVgpwcZVlsbSZM5/76JRm@Thu5zvBM45C/MjlWrb5gUf45pwFptcaIUXhDVBAZobfcJFpU43fKhxQxUJk7KAessbsGepcRPWlMWKSGWk8yMHCdY0zcisMHZmrkLjLdekJotFyrLWSmNfhZEG4hhSvNOWwt7eSv1NsuBucucxihhDhOIlRZFHK4cG@ODcATLWyyNb9s7I@kg0plgfm@j6sWvdZSeFRUNgPF5/3qyfvMGm2z/vRqvN0n81yL5ldOdD1JVnQXARpe4GsPsETDzjcBHX9yPgAy4pVATCBJS0UM2dVUAJScLBnKs/cMXXX@uG9qZhBnmlc2EhdVvpSjlU/WIAfQGCbiuAPgC5jnPqBOd3OCMwzbr9Bw)
## Original:
Outputs a list of reversed bits.
```
import Data.List
x@(_:v)=1:scanl(+)1x
f n=1:snd(mapAccumL(\a b->if b<=a then(a-b,1)else(a,0))n$reverse$fst$span(<=n)v)
```
[Try it online!](https://tio.run/##RVFbT8IwGH3frzhZltDGYlZQlIUtGn0hQX3wyQAhZXayuHXLWpB/P7sLo@vDufR8S853EPpXZlldp3lZVAavwojbVaqNc34iu@BEQx7oWKiM3FB@dhKoRlDfJBflcxwf8xXZCOzHUZpgvwgFzEEqIsZ7xqnMtCSC@ZQqr5InWWnpJdp4uhSKLEJFT7Q2UpsXoaVGEGBNlsowfJoqVT9061zN0HqcuZy7lJEJc/0OTS3q4Z11e8h5K1/YpHUurI34lxRvYwOd3Tejm@ygcL8PXE6nP85nD53Bh6@9netP55PuV73cjfSvvI/a51vHyUWqmgKWHyC0YyFsw287kA1JGQqKcYRMGhQja/VtgiRIKaIohD4Uf7Cx8mhsfSsFD3GhYmGwtptpQiGKdjlwv@Ci2Q3cd7h29ohZwfoN3lIMrdf/)
[Answer]
# [Red](http://www.red-lang.org), ~~135~~ 124 bytes
```
func[n][i: k: 0 until[i: i + 1 unless find do
b:[enbase/base to#{01}i 2]"11"[k: k + 1]n = k]reverse
rejoin["1"find do b"1"]]
```
[Try it online!](https://tio.run/##LYyxDoJAEET7@4oJlhayqKgk/oTtZgvw9uKJWcyBNsZvxyNxism84k1SP1/Us7jQzOFlVzbh2KBvUOJlU3wsFLEGZXzoOCJE8/CD6xpW69pRN0thGlafkr4RlRREBeeHftHEcEYvSd@aRnVJ70M0Lqj4/6DLW2QOQ9L2eoOBCRW22IEIVIG2oB3qPWoqcTzVB2GHnGeKNvGz9VnZI8DEyfwD "Red – Try It Online")
Uses [@Etheryte's method](https://codegolf.stackexchange.com/a/222687/75681)
### As an excercise - the step by step method:
## [Red](http://www.red-lang.org), 153 bytes
```
func[n][c: charset 1 until[k: 0 a: 0 b: 1 until[k: k + 1
t: a a: b b: t + b b > n]c/(k - 2): 1 0 = n: n - a]replace
enbase/base to#{01}c 2[any"0"end]"1"]
```
[Try it online!](https://tio.run/##TY7BasMwEETv@orBvbSUEq2cOo4g@YhehQ6yvCbBYWMU5RBCvt2Rbt3DMLzhwSYe1z8enVeTXae7RCfeRYt4CunGGYS75PPFzRYaocZg/8MZ3yCVLUJdh7rmgkrBEeLj5nPGD8xXlTQOEAspIPjEyyVEVixDuPGmBvL146npFWFckEejG5bRN9T4dbomDvFUXEcwaLEFEciAWtAW3S860uj33Q69bveGWu8Uyi3pLNktYSxqj6m8pPz6Bg "Red – Try It Online")
More readable:
```
f: func[n][
    c: charset 1
    until [
        k: 0
        set [a b] [0 1]
        until [ 
            k: k + 1
            set [a b] reduce [b a + b] 
            b > n
        ]
        c/(k - 2): 1
        0 = n: n - a
    ]
    replace enbase/base to binary! c 2 [any "0" end] "1"
]
```
`charset` is short for `make bitset!`
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~14~~ 12 bytes
*Edit: -2 bytes thanks to Leo*
```
↔:1!fo¬V&mḋN
```
[Try it online!](https://tio.run/##yygtzv7//1HbFCtDxbT8Q2vC1HIf7uj2@///v5kpAA "Husk – Try It Online")
Based on [Etheryte's approach](https://codegolf.stackexchange.com/a/222687/95126): upvote that!
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 63 bytes
```
.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
+`^(.*).(.*¶)(\1.)¶
$3$2
¶
1
```
[Try it online!](https://tio.run/##FYkxDsIwEAT7/QaOdHYky3sXTNKQMp@wUCgoaCgQZd6VB@RjxmlmpJnv6/f@PGsny1pjDxcgZeEm873o7KXQ@0C4C11IPHb060Ni8LHh2M8ffavOnKKZtRIKwwASVNDAAfmKzIRxyjeMySal/QE "Retina 0.8.2 – Try It Online") Link includes test cases. Explanation:
```
.+
$*
```
Convert to unary.
```
(\G1|(?>\2?)(\1))*1
```
Use a tweaked version of @MartinEnder's answer to [Am I a Fibonacci Number?](https://codegolf.stackexchange.com/questions/126373) to match Fibonacci numbers that sum to the input.
```
$#1$*01¶
```
For each match, generate the bit in the appropriate column.
```
+`^(.*).(.*¶)(\1.)¶
$3$2
```
Fold all of the bits together.
```
¶
1
```
Replace the final delimiter with a final 1 bit.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 38 bytes
```
ＮθＦ²⊞υ⊕ιＷ‹⌈υθ⊞υΣ…⮌υ²←1ＦΦ⮌υκ«←Ｉ¬›ιθ≧﹪ιθ
```
[Try it online!](https://tio.run/##VY7LCsIwEEXX9iuCqwnUhS58rqSgFKyIfkGsUxNMkzYPH4jfHtuCqNvhnHMn58zkmskQUlV5t/XlEQ3UdBEV2hAYUbLzloOPSapygyUqhycQtAFuXEgksEFrIWN3UfoSPI1JTb/Sobklj1xiwnUFe7yisdhRI9o2dkYoB/MNFi4m/WH/s7sS0jV//AqXJvuMen9GwqyDrXawNshaQXTzbbmXsWpprTirvThzB5k@ealj0hGL6BXCdDaehMFVvgE "Charcoal – Try It Online") Link is to verbose version of code. Explanation: Outputs digits in reverse order, but this is the least of Charcoal's problems because it can simply print them backwards.
```
Ｎθ
```
Input `n`.
```
Ｆ²⊞υ⊕ι
```
Start with `1` and `2` from the Fibonacci sequence.
```
Ｗ‹⌈υθ⊞υΣ…⮌υ²
```
Keep pushing terms until one exceeds `n`.
```
←1
```
Print the final `1`.
```
ＦΦ⮌υκ«
```
Loop through all the terms except the last in reverse order.
```
←Ｉ¬›ιθ
```
Print `0` or `1` depending on whether this term is larger than `n`.
```
≧﹪ιθ
```
Subtract the term from `n` if it is smaller.
[Answer]
# [Mini-Flak (BrainHack)](https://github.com/Flakheads/BrainHack), 104 bytes
```
([{}]((()))){({}(())({{}[()](({}({}))){(()[{}]){(({}{}[()]))}}{}}{}(())){[({})]({}[()](()[()]))}{}{})}{}
```
[Try it online!](https://tio.run/##NYs5DoBADAO/Yxe0HG9ZbbHQgBAUtFbeHhKOFNEkHs9X2861Lbs7iqwCYIwgS4JkBYx33LInAVNMkL0paUH2VqiSZsXf5Kekndvdu8PHqR9u "Brain-Flak (BrainHack) – Try It Online")
Starts at `11` and iteratively computes the encoding of the next number `n-1` times.
```
# Create 11 while computing 1-n.
([{}]((())))
# Repeat
{
  # Add 1 to counter (going up to zero) and allow loop to start
  ({}(())
    # Eventually push number of iterations to reach 00 or 11
    (
      {
        # Remove 1 from stack
        {}[()]
        # Compute sum of two digits, keeping second, and push twice
        (({}({})))
        # If not 00:
        {
          # Subtract value from 1; this makes iteration evaluate to 1
          (()[{}])
          # If top of stack still isn't zero (i.e., digits were 11):
          {
            # Push two zeros: one to exit loop and the other to exit conditional
            (({}{}[()]))
        }}{}
      # Repeat until 00 or 11 found
      }{}
      # Push 1 at position
      (())
    # Push number of leading zeroes to use, plus one
    )
    # That many times:
    {
      # Compute -k: this will make each iteration evaluate to -1
      [({})]
      # Subtract 1 from k...
      ({}[()]
        # while pushing 0 below it
        (()[()])
      )
    }{}
    # Since the push evaluates to a number of iterations, and
    # those iterations all evaluate to -1, this main part of the main
    # loop evaluates to zero.
    # Remove extraneous zero: this is shorter than subtracting 1 earlier
    {}
# Repeat until counter reaches zero, and pop zero
)}{}
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 14 bytes
```
λbṅ11c¬;ȯtbṘ1J
```
[Try it Online!](https://lyxal.pythonanywhere.com?flags=&code=%CE%BBb%E1%B9%8511c%C2%AC%3B%C8%AFtb%E1%B9%981J&inputs=65&header=&footer=)
Port of Ethertyte's answer.
```
λ      ;ȯt     # Nth integer where...
 bṅ            # Binary
   11c¬        # Doesn't contain 11
          bṘ   # Get the binary of that, reversed
            1J # Append a 1
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 50 bytes
Based on [tsh's JavaScript answer](https://codegolf.stackexchange.com/a/222719/9288).
-4 bytes thanks to [@att](https://codegolf.stackexchange.com/users/81203/att).
```
n1~If[#>n,k=n;1,2#0[+##,#]+If[k<#,0,k-=#;1]]&~1
```
[Try it online!](https://tio.run/##DctBCsIwFATQq3z44Ka/mEm0WmqKW3fuQxZBLJbSLKQ7sYfwBp7QI8S/mIE3MHNaHvc5LeMtlcGX/Pt8sV6GwH2WyecOYtmEilk4VrpPJxYjU@25Q4ybFeX6HPMSmOqe9KYbbc/0gpAVckI7ISigghLqZq@BETq2zUHbuNbCvcsf "Wolfram Language (Mathematica) – Try It Online")
]