Convert from binary to negabinary

Question

Given a binary integer inclusively between 0 and 1111111111111111 (i.e. a 16-bit unsigned integer) as input, output the same integer in negabinary.

The input can be in whatever format is most convenient for your language; for example, if it is easier for the program to handle input with 16 digits, like 0000000000000101, rather than simply 101, you can write the program to only accept input that way.

Sample I/O

> 1
1
> 10
110
> 1010
11110
> 110111001111000
11011001110001000
> 1001001
1011001

Here is a sample program I wrote that does base conversions, including negative and non-integer bases. You can use it to check your work.

Answer 1

APL, 21 characters

'01'[-(16/¯2)⊤-2⊥⍎¨⍞]

I used Dyalog APL for this, with ⎕IO set to 0, allowing us to index arrays starting at 0 rather than 1.

Explanation, from right to left:

• ⍞ gives us the user's input as a character vector.
• ⍎¨ applies the execute function (⍎) to each (¨) of the aforementioned characters, resulting in a vector of integer 1's and 0's.
• 2⊥ decodes the vector from base 2 into decimal.
• - negates the resulting decimal integer.
• (16/¯2)⊤ encodes the decimal integer into base ¯2 (negative 2). (16/¯2 replicates ¯2, 16 times, yielding 16 digits in our negabinary number.)
• - negates each element of our newly encoded number (before this, it consists of -1's and 0's), so that we can use it to index our character vector.
• '01'[ ... ] indexes the character array ('01') using the 0's and 1's of the negated negabinary vector. This is so we get a prettier output.

Example:

      '01'[-(16/¯2)⊤-2⊥⍎¨⍞]
10111010001
0001101011010001

Answer 2

Ruby, 32 31 characters

m=43690
'%b'%(gets.to_i(2)+m^m)

Uses the negabinary calculation shortcut.

Answer 3

GolfScript, 34 29 27 characters

n*~]2base{.2%\(-2/.}do;]-1%

A plain straigt-forward approach. It is quite interesting that the shortest version is the one which first converts to number and then back to base -2 (at least the shortest version I could find up to now). But the nice thing about this one is, that it contains almost 15% %.

Edit 1: For base 2 we can save one modulo operation and also join both loops.

Edit 2: I found an even shorter code to convert binary string to integer.

Answer 4

Haskell, 86 83 Bytes

import Data.Bits
import Data.Digits
c n|m<-0xAAAAAAAA=digits 2$xor(unDigits 2 n+m)m

Call using c and then an integer array for digits, e.g.

c [1,1]

PS: I'm new, did I submit this correctly?

EDIT: Saved some bytes thanks to Laikoni and also fixed some typos

EDIT2: Alternatively, c :: String -> String:

import Data.Bits
import Data.Digits
c n|m<-0xAAAAAAAA=concatMap show.digits 2$xor(unDigits 2(map(read.(:[]))n)+m)m

For 114 bytes (but you call it with a string: c "11")

Answer 5

Python (2.x), 77 characters

(not as short as the other solutions due to the need to manually switch base...) Should satisfy the requirements.

i=input();d=""
while i:i,r=i//-2,i%-2;i+=r<0;d+=`r+[0,2][r<0]`
print d[::-1]

Suggestions for further improvements are welcome!

Feed it with starting values like this: 0b1001001

Answer 6

JavaScript, 68 bytes

function(b){for(r='',n=parseInt(b,2);r=(n&1)+r,n>>=1;n=-n);return r}

Would be 52 bytes in ES6, but that post-dates the challenge:

b=>eval(`for(r='',n=0b${b};r=(n&1)+r,n>>=1;n=-n);r`)

Answer 7

Jelly, 4 bytes, language postdates challenge

Ḅb-2

Try it online!

Takes input, and produces output, as a list of digits.

Explanation

Ḅb-2
Ḅ     Convert binary to integer
 b-2  Convert integer to base -2

This is pretty much just a direct translation of the specification.

Answer 8

k, 17 bytes _noncompeting

Some of the features used probably postdate the challenge.

1_|2!{_.5+x%-2}\2/

Input is a list of 1's and 0's, and output is also a list of 1's and 0's.

Answer 9

PHP, 69 Bytes

for($i=bindec($argn);$i;$i+=$i%2&$c,$i>>=1,$c^=1)$r=($i%2).$r;echo$r;

Online Version

Answer 10

ES8, 54B

b=>eval`for(r='',n=0b${b};r=(n&1)+r,n>>=1;n=-n);r`

Answer 11

05AB1E, 4 bytes

C2(в

Try it online!

Answer 12

Japt, 4 bytes

Input as a binary string, output as a negabinary digit array.

Íì2n

Try it

Or, taking input as a binary digit array:

ì2JÉ

Try it