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... – Joanis Jan 7 '12 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.) – Peter Olson Jan 7 '12 at 14:58

10 Answers 10

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

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.

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! – Picard Mar 23 '17 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= .... – Laikoni Mar 23 '17 at 7:12

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

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.

  • Isn't this non-competing? This challenge is from '11... – NoOneIsHere Mar 22 '17 at 15:36
  • I missed that. I'll put a note in the header. – user62131 Mar 22 '17 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.

Examples of the program working.

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=>eval`for(r='',n=0b${b};r=(n&1)+r,n>>=1;n=-n);r`

Iff languages postdating question is allowed...

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.