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.

• Joanis: Just to clarify a bit further, the input and output would have to be binary, right? I mean: character strings of 0s and 1s. Looks clear to me, but an answer makes me doubt lightly...
• Peter Olson: @M.Joanis The input is binary, the output is negabinary (which looks exactly the same as binary--a string of zeroes and ones--but the way the number is interpreted is different.)
• Jo King: The link appears to be down, which is a prime reason for why we require questions to be self-contained these days

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.

• Stefano Diem Benatti: The input isnt hard coded. The 0xAAAA isnt the input, its the mask thats gonna transform the input. 0xAAAA is equivalent to 1010101010101010, which is used in a XOR operation to convert binary into negabinary.. The input itself comes from the gets keyword, which fetches from STDIN.
• Stefano Diem Benatti: changed 0xAAAA to 43690 (which is the same number in decimal) to decrease character count by 1. Makes it harder to understand wtf is happening though.
• Riker: Ah, okay. I don't ruby good so I wasn't sure. Sorry about that.

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")

• Riker: Yes, you did! Welcome to the site! Hope you stick around!
• Laikoni: Welcome to PPCG! You can drop the parentheses around undigits 2 n, because the function application binds stronger than the +m. You can also save some bytes by binding m in a guard: c n|m<-0xAAAAAAAA= ....

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.

• user62131: I missed that. I'll put a note in the header.

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.

Examples of the program working.

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