# Convert from binary to negabinary

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.

• 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... Jan 7, 2012 at 5:21
• @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.) Jan 7, 2012 at 14:58
• The link appears to be down, which is a prime reason for why we require questions to be self-contained these days
– Jo King
Nov 28, 2019 at 23:00

# 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


# Ruby, 32 31 characters

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


Uses the negabinary calculation shortcut.

• 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. Mar 27, 2017 at 16:35
• 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. Mar 27, 2017 at 16:43
• Ah, okay. I don't ruby good so I wasn't sure. Sorry about that. Mar 27, 2017 at 17:41

## GolfScript, 3429 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.

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

• Yes, you did! Welcome to the site! Hope you stick around! Mar 23, 2017 at 3:43
• 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= .... Mar 23, 2017 at 7:12

## 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

## 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)  # 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. • I missed that. I'll put a note in the header. – user62131 Mar 22, 2017 at 15:38 # 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. # PHP, 69 Bytes for($i=bindec($argn);$i;$i+=$i%2&$c,$i>>=1,$c^=1)$r=($i%2).$r;echo$r;  Online Version # ES8, 54B b=>evalfor(r='',n=0b${b};r=(n&1)+r,n>>=1;n=-n);r


# 05AB1E, 4 bytes

C2(в


Try it online!

# 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