[Question]
  [
### Definition
The Alternating Power Fibonacci Sequence is formed as follows.
1. Start with the empty sequence and set **n** to **1**.
2. Compute **f**n, the **n**th non-negative [Fibonacci number](https://en.wikipedia.org/wiki/Fibonacci_number), with repetitions.  
**0** is the first, **1** is the second and the third, **2** is the fourth. All others are obtained by summing the two previous numbers in the sequence, so **3 = 1 + 2** is the fifth, **5 = 2 + 3** is the sixth, etc.
3. If **n** is odd, change the sign of **f**n.
4. Append **2n-1** copies of **f**n to the sequence.
5. Increment **n** and go back to step 2.
These are the first one hundred terms of the APF sequence.
```
 0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
```
### Task
Write a full program or a function that takes a positive integer **n** as input and prints or returns the **n**th term of the APF sequence.
If you prefer 0-based indexing, you can alternatively take a non-negative integer **n** and print or return the APF number at index **n**.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"); may the shortest code in bytes win!
### Test cases (1-based)
```
    1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610
```
### Test cases (0-based)
```
    0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610
```
  
[Answer]
# [Python 2](https://docs.python.org/2/), 30 bytes
```
f=lambda n:n<1or f(n/4)-f(n/2)
```
[Try it online!](https://tio.run/nexus/python2#FY1LCoAwDETXeorZaSFF6wdF1IuIC0UKgkaR3r8mbzGZPAKJfrq2ez828MCjez74nIvGWB2ViV5MwMlYHKEi1ISG0BF6gitLca1Eq01WTUW0IufKOqTJ@50cEAiZnTOSJ8HEHw "Python 2 – TIO Nexus")
One-indexed.
The sequence felt like a puzzle, something that Dennis generated by having a short way to express it. The power-of-two repetitions suggest recursing by bit-shifting (floor-dividing by 2). The alternating-sign Fibonacci recursion `f(n)=f(n-2)-f(n-1)` can be adapted to bitshift in place of decrementing. The base case works out nicely because everything funnels to `n=0`.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 5 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
BLCÆḞ
```
**[Try it online!](https://tio.run/nexus/jelly#@@/k43y47eGOef@P7jnc/qhpjfv//9GGOgpGOgrGOgomOgrmOgoWOgqGBgZAMVMgYQpiAbkgEgSAwiAAVA4CsQA "Jelly – TIO Nexus")**
### How?
Extending the Fibonacci series back into negative indexes such that the relation `f(i) = f(i-2) + f(i-1)` still holds:
```
  i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ...
```
Going back from `i=0` the numbers are those we need to repeat **2n-1** times, and Jelly's Fibonacci built-in, `ÆḞ`, will calculate these.
We can find the `-i` (a positive number) that we need by taking the bit-length of `n` and subtracting `1`.
Since we want `i` (a negative number) we can instead perform `1-bitLength` and Jelly has an atom for `1-x`, `C`, the complement monad.
```
BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21
```
[Answer]
# Mathematica, ~~43~~ ~~36~~ 24 bytes
```
Fibonacci@-Floor@Log2@#&
```
7 bytes saved thanks to @GregMartin, and a further 12 thanks to @JungHwanMin.
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~19~~ ~~17~~ ~~16~~ 11 bytes
```
lOiB"yy-]x&
```
Input is 1-based.
[Try it online!](https://tio.run/nexus/matl#@5/jn@mkVFmpHVvh7qQUH6v2/78xCAAA "MATL – TIO Nexus") Or [verify all test cases](https://tio.run/nexus/matl#S/if45/ppFRZqRtbofY/wqWsIuS/IZcRlzGXCZc5lwWXoYEBl5GpAZcpkAaygQQIcBmBAJcxCAAA).
### How it works
For 1-based input **n**, let **m** be the number of digits in the binary expansion of **n**. The **n**-th term in the output sequence is the **m**-th term in the Fibonacci sequence, possibly with its sign changed.
One idea would be to iterate **m** times to compute terms of the Fibonacci sequence. This is easy with a `for each` loop using the array of binary digits. If the Fibonacci sequence were initiallized with **0**, then **1** as usual, iterating **m** times would result in **m+2** terms on the stack, so the top two numbers would have to be deleted. Instead, we initiallize with **1**, then **0**. That way the next generated terms are **1**, **1**, **2**, ... and only *one* deletion is needed.
The sign could be dealt with by using another loop to change sign **m** times. But that's costly. It is better to integrate the two loops, which is done simply by *subtracting* instead of adding in the Fibonacci iteration.
```
l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack
```
[Answer]
## JavaScript (ES6), 33 bytes
```
f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p
```
1-indexed.
A port of [xnor's answer](https://codegolf.stackexchange.com/a/108814/42545) would be 23:
```
f=n=>n<1||f(n/4)-f(n/2)
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~83~~ ~~82~~ 79 bytes
```
def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)
```
[Try it online!](https://tio.run/nexus/python2#DcpBCoAgEAXQvaf4m8AphXQpeJKIUFIQhhGkzm@99Zt3qahaTIq7ydFRUOCYm2ihw4dTofaBC03AIf0jm7RlhVGedwjSajUX0UyL78M6mvMD "Python 2 – TIO Nexus")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
BLµ’ÆḞN⁸¡
```
Uses one-based indexing.
[Try it online!](https://tio.run/nexus/jelly#@@/kc2jro4aZh9se7pjn96hxx6GF/4/uOdz@qGmN@///hjoKRjoKxjoKJjoK5joKFjoKhgYGQDFTIGEKYgG5IBIEgMIgAFQOAgA "Jelly – TIO Nexus")
## Explanation
This method works if your Fibonacci function only supports non-negative arguments.
```
BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 6 bytes
```
Mg1-¢l
```
[Test it online!](http://ethproductions.github.io/japt/?v=1.4.4&code=TWcxLaJs&input=MTAw)
### How it works
As mentioned in other answers, the **n**th term in the alternating-sign Fibonacci series is the same as the **-n**th term in the regular series. **n** can be found by taking the bit-length of the input and subtracting one; negating this results in 1 minus the bit-length.
```
Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~11~~ 10 bytes
Uses 1-based indexing 
**05AB1E**'s Fibonacci function returns positive fib numbers less than *n*, meaning we'd have to generate more than necessary, get the correct one by index and then calculate the sign. So I doubt any method based around that will be shorter than calculating the numbers iteratively.
Uses the realisation that we can initialize the stack with `1, 0` reversed to handle the case when `n=1` as described in [Luis Mendo's MATL answer](https://codegolf.stackexchange.com/a/108813/47066).
```
XÎbgG‚D«`-
```
[Try it online!](https://tio.run/nexus/05ab1e#@x9xuC8p3f1RwyyXQ6sTdP//NwYBAA "05AB1E – TIO Nexus")
**Explanation**
```
X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements
```
[Answer]
# [Perl 6](http://perl6.org/), 53 bytes
```
{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}
```
Straightforward implementation of the sequence, the way it was described.  
Zero-based.
[Answer]
# [Julia 0.5](http://julialang.org/), 19 bytes
```
!n=n<1||!(n/=4)-!2n
```
[Try it online!](https://tio.run/nexus/julia5#FcZBCoMwFIThtZ7iRRASGGkSE3ShpQfpMhXcTEVceveYfIt/JiuuXNx9K83XGsygPPP2P4WyU7SDx4iACTOctfDRIpYtv6SCrzBWpm0@x7nz2nTXxyTDW/qQvuxAKJr2x5Qf "Julia 0.5 – TIO Nexus")
### How it works
This uses the same formula as [@xnor's Python answer](https://codegolf.stackexchange.com/a/108814/12012). The recurrence relation  
**g(n) = g(n-2) + g(n-1)** generates the negative terms of the Fibonacci sequence, which equal the positive terms with alternating signs. From anywhere in a run of **2**k repetitions of the same number, we can pick any repetition of the previous run of **2**k-1 numbers and the run of **2**k-2 numbers before those by dividing the index by **2** and **4**.
Rather than the straightforward
```
f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes
```
we can redefine an operator for our purposes. Also, **f** will work just as fine with floats, so we get
```
!n=n<1||!(n/4)-!(n/2)   # 21 bytes
```
Finally, if we update **n** with a division by **4**, wwe can write **n/2** as **2n** and omit a pair of parens, leading to the 19-byte function definition in this answer.
[Answer]
# [J](http://jsoftware.com/), 18 bytes
```
(%>:-*:)t.@<:@#@#:
```
Uses one-based indexing. Takes an input integer *n* > 0 and computes `floor(log2(n))` by finding the length of its binary representation and then decrements that value by one. It then finds the `floor(log2(n))-1`*th* coefficient of the generating function *x*/(1 + *x* - *x*2) which is the g.f for the negative-indexed Fibonacci values.
[Try it online!](https://tio.run/nexus/j#FcY7CoAwEIThPqcYDEIiGjYvlEUldxGDnY33j9mv@GdaxcEw48nLxPZzZeeii2al7ut5YWZXB7LwCIhIWLHBEyFkQu7bf49AEIiitR8 "J – TIO Nexus")
## Explanation
```
(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value
```
]