Convert to a non-adjacent form

Question

Consider a form of binary where digits can be any of \$1\$, \$0\$ and \$-1\$. We'll still call this "binary" because we convert the digits from base two. For example,

$$\begin{align} [1, 0, -1, 1]_2 & = 1 \times 2^3 + 0 \times 2^2 + -1 \times 2^1 + 1 \times 2^0 \\ & = 8 - 2 + 1 \\ & = 7 \end{align}$$

We'll call a representation of a number in this format a "non-adjacent form" if no non-zero digits are adjacent. \$[1, 0, -1, 1]_2\$ is not a non-adjacent form of \$7\$, as the last two digits are adjacent and non-zero. However, \$[1,0,0,-1]_2\$ is a non-adjacent form of \$7\$.

You should take a positive integer and convert it to a non-adjacent form. As every number has an infinite number of these forms (but only by prepending leading zeroes), you should output the form with no leading zeros. If the standard binary format of the input is a non-adjacent form (e.g. \$5 = 101_2\$), you should output that. You can output a list of integers, or a single string, or any other format the clearly shows the output. You may optionally choose to use any three distinct characters in place of 1, 0 and -1.

This is code-golf, so the shortest code in bytes wins.

Answer 1

K (ngn/k), ¹⁹ 12 bytes

-/'2\-2!3 1*

Try it online!

Uses Prodinger's algorithm on Wikipedia:

Input   x
Output  np, nm
xh = x >> 1;
x3 = x + xh;
c = xh ^ x3;
np = x3 & c;
nm = xh & c;

And then the last three steps are not used because the & c part of np and nm erases the 1 bits where both are 1, but we're doing -/' so it doesn't matter. (Observation thanks to @m90)

How it translates to K:

-2!3 1*    given x, create (3x,x) and floor-divide both by 2
           which gives (x3,xh)
2\         convert to base 2, which gives a two-column matrix
           with lsb being the last row
           1st column is np, 2nd column is nm, but both-1 bits not handled
-/'        evaluate np - nm to get a vector of -1, 0, 1s

Answer 2

Jelly, ¹³ 9 bytes

;0+HBU_/U

Try it online!

-4 bytes (^/&$ removed) thanks to @m90's observation that we don't need to clear shared 1 bits.

Look ma, no Unicode!

Literal translation of Prodinger's algorithm. x3 goes before xh, and U is used twice to align the binary representations of the two.

Answer 3

JavaScript, 35 bytes

f=n=>n?f(n+n%4/3>>1)+'OPON'[n%4]:''

Try it online!

Output O for 0, P for 1, N for -1.

-2 bytes by Arnauld.

---

Alternatively, as suggested by Arnauld, using 1 for 1, 2 for 0, 0 for 0, and, 3 for -1:

JavaScript, 31 bytes

f=n=>n?f(n+n%4/3>>1)+n%2*n%4:''

Try it online!

Answer 4

05AB1E, 21 15 bytes

0‚¬2÷+2вí`(0ζRO

-6 bytes thanks to @m90, thanks to his observation that & c only changes [1,1] to [0,0], which doesn't matter when we're subtracting them.

Try it online or verify some more test cases.

Explanation:

0‚        # Pair the (implicit) input with 0
  ¬       # Get the first item of this pair (the input) without popping
   2÷     # Integer-divide it by 2
     +    # Add it to both the input and 0 in the pair
          # (we now have the pair [input+input//2, input//2])
      2в  # Convert both inner values to a binary-list
í         # Reverse each inner list
 `        # Pop and push both lists separated to the stack
  (       # Negate all values in the top list
   0ζ     # Zip the two lists together with 0 as filler
     R    # Reverse the list of pairs back again
      O   # Sum each inner pair together
          # (after which the resulting list is output implicitly)

Answer 5

---

Python 3, 176 103 bytes

Literal translation of Prodinger's algorithm. By no means the shortest python 3 answer that should be attainable. it's been a while on here so looking forward to getting back into it!

x=int(input())
h=x>>1
t=h+x
c=h^t
p=bin(t&c)
m=bin(h&c)
n=[]
j=len(p)-2
k=len(m)-2
for i in range(j):n.append(int(p[i+2]))
for i in range(k):n[j-k+i]=-int(m[i+2])*(m[i+2]==0)or 1
print(n)

If anyone can help shorten it I'd appreciate it, there must be an easier way to concatenate the two positive and negative value lists.

Using m90's answer it can be shortened vastly predominately by using zip!

enter code x=int(input())
print([*[int(x)-int(y)for x,y in zip(*[f".{x//2+z:0{len(bin(x*3))-3}b}"for z in[x,0]])]])

Answer 6

C (clang), ^{103 \$\cdots\$ 96} 94 bytes

m;i;f(n){int r[n];for(i=!n,n+=*r=m=n/2;n;n/=2,m/=2)r[i++]=n%2-m%2;for(;i--;)putchar(r[i]+49);}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Inputs positive integer \$n\$.
Outputs \$n\$ converted to its non-adjacent form using \$2\$ for \$1\$s, \$1\$ for \$0\$s, and \$0\$ for \$-1\$s.

Answer 7

Ruby, 41 40 bytes

f=->n{n>0?f[(n-w=n%2*(2-n%4))/2]+[w]:[]}

Try it online!

Answer 8

Python 3, 51 bytes

f=lambda x,s="":x and f(round(x/2))+".+.-"[x%4]or""

Try it online! Outputs using . for 0, + for 1 and - for -1. Explanation: Port of @tsh's JavaScript solution, except that Python has Banker's rounding which saves a byte in Python 3. Or I could have just use Python 2 I guess.

Answer 9

Charcoal, 23 bytes

ＮθＷθ«←§.+.-θ≔÷⁺¬﹪⊕θ⁴θ²θ

Try it online! Link is to verbose version of code. Outputs using . for 0, + for 1 and - for -1. Explanation: Another port of @tsh's JavaScript solution.

Ｎθ

Input the number to convert.

Ｗθ«

Repeat until it is zero.

←§.+.-θ

Output the previous digit using cyclic indexing. The digits are output right-to-left so that the final output is in the correct order.

≔÷⁺¬﹪⊕θ⁴θ²θ

Divide by two, rounding to even.