Convert from variable-width Two's Complement to Integer

Question

Take an input, and convert it from Two's Complement notation (binary where the first bit is negated, but the rest are taken as normal) into an integer (in a somewhat standard output form). Input can be as a string, a list of digits, a number, or pretty much any other format which is recognizably Two's Complement. Leading zeroes must function properly. Both returning and outputting the value are fine.

Examples:

0 -> 0
1 -> -1
111 -> -1
011 -> 3
100 -> -4
1001 -> -7
0001 -> 1

Example conversion: Say our input is 1101. We can see that the first bit is in position 4, so has a positional value of 2^3. Therefore, since it's a 1, we add -8 to our total. Then, the rest of the bits are converted just the same as regular binary (with 101 being the same as 5), so the result is -3.

Example implementation (Mathematica, 40 characters): Rest@#~FromDigits~2 - 2^Length@#/2*#[[1]] & This implementation takes input as a list of digits.

Code-golf, so shortest solution wins.

• Seggan: I suggest you add an explanation of how to convert from 2's Complement
• Peter Cordes: Most of the answers here produce a native integer as the result. There's nothing "decimal" about that; most languages use binary integers. Is it intended that a valid output format is "a number", like a C int rather than an array of decimal digits? If so, along with the input being allowed as a number, doesn't that mean we can do int f(x){return x;} because x is already a 2's complement int when compiled for a 2's complement machine? Or if you need variable-width, take the width as an arg and (x<<(32-n)) >> (32-n) to sign-extend the low n bits? Where do you draw the line?
• Peter Cordes: Without invalidating the existing answers, I think the best option would be to retitle it as "convert or sign-extend from variable-width 2's complement to integer". (I think "to integer" would be ok, despite Javascript numbers being floating-point, only using integers as an optimization or converting to them when doing bitwise operations.)
• LorenDB: Shouldn't 111 produce -3 instead of -1?
• DLosc: @LorenDB No? 111 is -1*(2^2) + 1*(2^1) + 1*(2^0) = -4 + 2 + 1 = -1.

Answer 1

JavaScript (ES6), 31 bytes

Expects a binary string.

s=>(q=1<<s.length-1,'0b'+s^q)-q

Try it online!

Uses the classic sign extension formula:

sign_extended = (value XOR mask) - mask

where only the sign bit is set in mask (e.g. 0x80 for a byte).

---

JavaScript (ES6), 26 bytes

Expects an array of bits.

f=a=>1/a?-a:a.pop()+2*f(a)

Try it online!

Answer 2

Jelly, 4 bytes

N1¦Ḅ

A monadic link that accepts a list of 1s and 0s and yields an integer.

Try it online! Or see the test-suite.

How?

N1¦Ḅ - Link: list of 1s and 0s, A
 ¦ - sparse application to A...
 1 - ...indices: 1
N - ...action: negate
 Ḅ - convert from binary (conversion from base functions allow non-base digits)

Answer 3

JavaScript (Node.js), 26 bytes

s=>'0b'+s-s[0]*2**s.length

Try it online!

• l4m2: 25

Answer 4

Python 3.8 (pre-release), 33 bytes

lambda n:2*int(n,2)-int(n[0]+n,2)

Try it online!

This is essentially 2 x n - n' where n is the input and n' is the input with its highest bit repeated. It can be rewritten 2 x n - 2 x h - n = n - 2 x h where h is the highest bit of n

Python 3.8 (pre-release), (削除) 34 (削除ここまで), 33 bytes (@GB)

lambda n:eval(f"0b{n[1:]}0-0b"+n)

Try it online!

This boils down to 2 x n' - n where n is the input and n' is the input with the highest bit cleared. This can be rewritten as 2 x n - 2 x h - n = n - 2 x h where h is the highest bit of n (in position).

• friddo: nice! didn't even think of this.
• G B: Merging the two: n:int(n[1:],2)-int(n,2)
• loopy walt: @GB the first term needs a factor 2. Also, int doesn't accept empty string.
• G B: You are right, plan B: you can make the second one shorter by using +n at the end of the string instead of {n} inside the string

Answer 5

Perl 5 -pl, 31 bytes

s/.//;$_=-$&*2**y///c+oct"0b$_"

Try it online!

• Sisyphus: 27: Try it online!
• Kjetil S: 29: Try it online!

Answer 6

Python 3.8 (pre-release), 38 bytes

lambda n:(a:=int(n,2))-(a*2&2**len(n))

Try it online!

Answer 7

Wolfram Language (Mathematica), 20 bytes

Fold[#+##&,-#,!##2]&

Try it online!

Input [digits...].

Negates the first bit, and takes the rest as normal.

Answer 8

x86-16 machine code, 25 bytes

Binary:

00000000: 33c0 9903 f1f9 4e13 d2f6 0401 7402 0bc2 3.....N.....t...
00000010: e2f4 7404 33c2 2bc2 c3 ..t.3.+..

Listing:

33 C0 XOR AX, AX ; AX = 0 (working sum) 
99 CWD ; DX = 0 (mask bit)
03 F1 ADD SI, CX ; SI = end of input string 
F9 STC ; set CF so DX = 1 on first loop
 TC_LOOP: 
4E DEC SI ; get next significant bit 
13 D2 ADC DX, DX ; shift left with CF to least sig bit
F6 04 01 TEST BYTE PTR[SI], 1 ; this bit a '1'? 
74 02 JZ NEXT_BIT ; if not, go to next
0B C2 OR AX, DX ; flip bit on working sum, CF = 0 
 NEXT_BIT: 
E2 F4 LOOP TC_LOOP ; loop until end of input string 
74 04 JZ TC_DONE ; was most sig bit a 1? 
33 C2 XOR AX, DX ; if so, sign extend 
2B C2 SUB AX, DX 
 TC_DONE: 
C3 RET ; return to caller

Callable function. Input string at DS:[SI], length in CX. Output to AX.

enter image description here

• Peter Cordes: Huh? This converts an ASCII string of base-2 digits into a binary integer in a register, and sign-extends it out to 16 bits. No decimal representation of the value is ever involved. If this is allowed, I'd suggest taking the binary input already in a register, along with a bit-length in another register, reducing the problem to just sign-extension with no conversion from or to ASCII (neg cl / shl eax, cl / sar eax, cl / ret. Narrower shifts still mask the count &31 so would shift out all the bits; 8086 doesn't mask). The question does mention that input options include "a number".
• 640KB: @petercordes yeah, it did occur to me after that the spec saying "pretty much any other format which is recognizably Two's Complement" is pretty loose and what you are saying could absolutely work. The challenge being "zero extend an arbitrary sized value to a machine sized value", doesn't need input to be a string for sure. I'll give this some thought when I get a few minutes.
• Peter Cordes: Working on a quick answer myself, I think it's as easy as the asm sequence in my comment posted, for a function.
• 640KB: @petercordes awesome! Can't wait to see it!
• Peter Cordes: Yup, 7 bytes for those instructions in 32 or 64-bit mode. Most of the time went into writing the text.

Answer 9

C (GCC), 88 bytes

n;main(i,v)char**v;{char*s=*++v;for(;*s;)n=n*2|(*s++-=48);printf("%d\n",n-(**v<<s-*v));}

Attempt This Online!

Indented code:

n;
main(i,v)char**v;{
 char*s=*++v;
 for(;*s;)
 n=n*2|(*s++-=48);
 printf("%d\n",n-(**v<<s-*v));
}

The input is passed through argv[1].

• Peter Cordes: Possibly n+=n-48+*s++? (n+=n left shifts like n*=2). Update: Noodle9's answer uses a similar trick. I don't think you need to modify the input string, so *s++ - 48 is the low bit. Actually *s++&1 should get the ASCII '0' / '1' as an integer if operator precedence works without parens. But anyway, +1 for actually using printf to produce decimal output instead of returning a number (a binary integer in C), satisfying the requirement of the question that many other answers ignore.

Answer 10

Vyxal, 5 bytes

ḣ$NpB

Try it Online!

When you steal ideas from Jelly

ḣ$NpB # Expects a list of digits
ḣ # Push the first item and then the rest
 $ # Swap
 N # Negate the first item
 p # Prepend the result to the rest of the list
 B # Binary to decimal

Vyxal, 8 bytes

h[†B›N|B

Try it Online!

My original pre-Jelly answer

h[†B›N|B # Takes input as a list of binary digits
h[ # If the first bit is 1...
 † # Vectorized not
 B # Convert to decimal
 › # Add one
 N # Negate
 | # Otherwise...
 B # Convert to decimal

Answer 11

R, (削除) 42 (削除ここまで) (削除) 40 (削除ここまで) (削除) 39 (削除ここまで) (削除) 37 (削除ここまで) 36 bytes

Edit: -2 bytes thanks to @Giuseppe and -2 bytes thanks to @Dominic van Essen.

\(x)2^rev(a<-seq(x)-1)%*%(x*(-1)^!a)

Attempt This Online!

Takes input as a list of digits.

• Giuseppe: 40 bytes using x[-1]^0 because of course 0^0==1 in R.
• pajonk: @Giuseppe Ah, that's neat. Thanks!
• att: 35 bytes porting mine
• pajonk: @att I think you should post it as a separate answer.
• Dominic van Essen: 34 bytes now posted...

Answer 12

05AB1E, 5 bytes

ć(š2β

Input as a list of bits.

Same approach as @JonathanAllan's Jelly answer, but found independently.

Try it online or verify all test cases.

Explanation:

ć # Extract head of the (implicit) input-list; push remainder-list and first
 # item separated to the stack
 ( # Negate this head
 š # Prepend it back to the list
 2β # Convert it from a base-2 list to an integer
 # (after which the result is output implicitly)

• Giuseppe: congrats on 100k rep! :-)

Answer 13

R, 34 bytes

\(x)sum(a<-x*2^rev(seq(x)))/2-a[1]

Attempt This Online!

Test setup borrowed from pajonk's R answer.

Answer 14

x86 machine code, 7 bytes

Function that works in 32 or 64-bit mode, with inputs:

• length n of the bitstring, in ECX (really just CL)
• ​bit-pattern in the low n bits of EAX. (bits in "a number" is an allowed input format)

Output: Signed integer in the full width of EAX.
In binary 2's complement format, as standard for x86.

Apparently a "number" is a valid output, with no need to convert it ourselves to something having anything to do with decimal, judging by other existing answers, except for a C answer that actually calls printf after sign-extending to fill an int. (And languages that implicitly print numeric output as a decimal string, but most of the non-golf-language answers are functions that return a number.)

NASM listing: address, machine-code bytes, source

 sign_extend_nbits:
00 F7D9 neg ecx ; 32-n = -n after masking to &31
02 D3E0 shl eax, cl ; x86 shifts implicitly mask the count &31
04 D3F8 sar eax, cl
06 C3 ret

Try it online!

Algorithm: Left shift so the MSB of the narrow input is at the top of the full register (count = 32-n), then arithmetic right-shift back to where it was, leaving the upper bits filled with copies of the MSB. x86 is a 2's complement machine; its arithmetic right shift does 2's complement sign extension.

This problem reduces to 2's complement sign-extension, with no need to read an ASCII string of base 2 digits, as stated by the question's input formats. (But this output format intentionally violates the stated "decimal" output requirement of the question the same way many other answers do. We could div in a loop, or maybe fild / fbstp to make BCD in about twice as many bytes.)

x86 shifts mask their count with &31 (for 8, 16, and 32-bit operand-size), so the -n = CHAR_BIT*sizeof(int)-n trick only works for 32 or 64-bit shifts, not 8 or 16. 8086 didn't mask shift counts at all, and I think when they introduced masking for performance reasons in 186 and 286, they wanted to still allow shifting out all the bits of a 16-bit register. But when 32-bit regs were new, masking was already a thing so they could choose whatever semantics they wanted.

---

This "protest" answer is intended to show how trivial the problem is with the stated allowed input formats, if we follow the precedent of other answers ignoring the "decimal" output requirement.

Computers, and most computer languages, use binary integers. In most of those languages, operators like bitwise n & 1 being the same as % 2 (for positive numbers), and x<<1 being the same as x*2, prove that numbers are binary. Converting an integer to an array or ASCII string of decimal digits takes extra work, as in https://stackoverflow.com/questions/13166064/how-do-i-print-an-integer-in-assembly-level-programming-without-printf-from-the/46301894#46301894 (Or perhaps use x86 fild / fbstp to store the float as packed BCD. Yes this instruction exists, and yes it's microcoded and very slow)

If you don't want to require that, don't say "decimal", just say "integer".

But don't maybe don't allow input formats that are already 2's complement integers? A C answer of f(x){return x;} is arguably valid if we say that the 2's complement input number must already be in an int, which is a fixed-width type and thus requires 2's complement sign-extension for valid integers. I decided to support variable widths by taking a value + length instead of just writing a 1-byte C3 ret as a full protest answer, to stick to the spirit of what seemed to be the challenge, 2's complement sign extension without any actual conversion necessary.

• 640KB: The challenge is really "convert an arbitrary-sized integer value to another arbitrary-sized integer value with sign extension". Since your platform's destination data size (16, 32, 64 or arbitrary precision) is unspecified and up to the submitter, it's also arbitrary. Suppose there's nothing that requires that the destination size is larger than the source so it could be truncation too.
• Romanp: I'm still deciding, but I would say that forcing output in some form that can either be read as a base-10 integer (by a human) or is in the "standard form" for a language's output of numbers seems right.
• Peter Cordes: @Romanp: Your edit to the question title looks good, then. The question body still says "decimal". Note that answers that are functions or lambdas just return a value, not output it in any form intended for human consumption directly. (If you looked at the value with a debugger, it's the debugger that would convert a binary integer to a string of ASCII hex or decimal digits). Perhaps you were thinking in terms of golf languages or whole programs when you wrote it, where "output" is something that actually gets printed on a screen, often implicitly by golf languages.

Answer 15

C (gcc), ^{(削除) 63 (削除ここまで) (削除) 57 (削除ここまで)} 46 bytes

b;f(char*n){for(b=48-*n;*++n;)b+=b+*n-48;n=b;}

Try it online!

Saved 11 bytes thanks to att!

Inputs a string of two's complement \1ドル\$s and \0ドル\$s.
Returns its int value.

• att: 46 bytes
• Noodle9: @att Nice one - thanks! :D
• Peter Cordes: This returns int. C requires that int is a binary integer type, either two's complement, one's complement, or sign/magnitude. That's why n<<=1 multiplies by 2, not 10. There's nothing decimal about this. (This seems to be a problem with an under-specified question that isn't explicit about what it means to convert to decimal, since most other answers make this assumption. It probably needs to be retitled to match the answers.)

Answer 16

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}5 bytes ^SBCS

Takes input as a vector of digits.

2⊥-@1

Try it on APLgolf!

Port of att's answer. Negate the first (most significant) bit and convert from base 2.

Answer 17

MathGolf, 8 bytes

å∞l├∞▌å-

Input as a string.

Port of @loopyWalt's top Python answer

Try it online.

Explanation:

å # Convert the (implicit) input-string from binary to an integer
 ∞ # Double it
l # Push the input-string again
 ├ # Pop and push its first character
 ∞ # Double it to two of those characters
 ▌ # Prepend it back
 å # Convert it from a binary-string to an integer
- # Subtract the two integers from each other
 # (after which the entire stack is output implicitly as result)

Answer 18

Haskell, 21 bytes

(0-).foldl1((-).(2*))

Try it online!

A modification of Aiden Chow's answer to avoid head-tail dissection.

Given that (+).(2*) is a shorthand for \x y -> 2*x+y, we can replace + with - to get \x y -> 2*x-y. When used with foldl1, the modification has the effect of negating every single number of input list l, except the first. Then it suffices to negate back the entire result to get the intended answer.

Answer 19

Haskell, (削除) 38 (削除ここまで) (削除) 32 (削除ここまで) (削除) 29 (削除ここまで) 27 bytes

Thanks @Unrelated String and @Bubbler for helping me golf this in TNB chatroom.

Thanks @Bubbler for another -2 bytes by directly setting -h as the initial value of foldl

f(h:t)=foldl((+).(2*))(-h)t

Try it online!

Explanation

f(h:t)=foldl((+).(2*))(-h)t
f(h:t)= list input, with the list's head being h and tail being t
 example: [1,0,0,1]
 foldl( .... )(-h) starting with initial value -h...
 (+).(2*) t iteratively apply the function (+).(2*) == \x y->2*x+y
 across the list t from left to right
 this converts from a binary list to decimal, with the
 head of the list negated
 example: [1,0,0,1] -> -1 (initial -h) * 2 + 1 = -1
 [0,0,1] -> -1 * 2 + 0 = -2
 [0,1] -> -2 * 2 + 0 = -4
 [1] -> -4 * 2 + 1 = -7 (output)

• Bubbler: As you're already dissecting the input's head and tail, feeding -h directly into the initial value of foldl gives 27.

Answer 20

Pari/GP, 29 bytes

I don't think this should work but it does.

f(v)=v[1]*=-1;fromdigits(v,2)

Try it online!

Answer 21

JavaScript (Node.js), ^{(削除) 51 (削除ここまで)} 49 bytes

s=>2**s.length/2*-s[0]+parseInt(s.slice(1)||0,2)

-2 bytes because dividing by 2 is golfier than subtracting 1 from length
-1 byte thanks to Matthew Jensen's suggestion to use slice over substr

Try it online!

• ophact: Fails on test case with 111. Output should be -1, but your output is -3
• Mayube: @ophact oops, apparently I forgot how twos complement works. Fixed at the cost of 11 bytes
• Matthew Jensen: save 1 byte by using s.slice() instead of s.substr()

Answer 22

Pip, 8 bytes

-:@ggFD2

Takes input as a list of bits, given as separate command-line arguments. Attempt This Online!

Explanation

Same approach as Jonathan Allen's Jelly answer:

-:@ggFD2
 g List of cmdline args
 @ First element
-: Negate in place
 g Updated list
 FD Convert from a list of digits
 2 In base 2

Answer 23

Charcoal, 10 bytes

I↨EA⎇κι±ι2

Try it online! Link is to verbose version of code. Explanation:

 A Input array
 E Map over elements
 κ Current index
 ⎇ If nonzero then
 ι Current bit else
 ι Current bit
 ± Negated
 ↨ 2 Convert from base `2`
I Cast to string
 Implicitly print

Answer 24

Retina 0.8.2, 46 bytes

^1
-
1
01
+`(-|1)0
01ドル1ドル
+`-1|0
^(-?).*
1ドル$.&

Try it online! Link includes test cases. Explanation:

^1
-

Change a leading 1 to a -.

1
01
+`(-|1)0
01ドル1ドル

Perform binary to unary conversion, counting - as a digit, which causes it to be raised to the appropriate power of 2.

+`-1|0

Subtract the value of the lower order bits from that power of 2.

^(-?).*
1ドル$.&

Convert to decimal, keeping the leading sign if the number is negative.

Answer 25

Ruby, 28 bytes

->n{eval"0b#{n}0-0b"+n[0]+n}

Try it online!

Answer 26

APL+WIN, 27 bytes

Prompts for two's compliment as vector of integers

(1+ ×ばつn)×ばつn+2⊥1↓2|(n←↑b)+b←⎕

Try it online! Thanks to Dyalog APL Classic

Answer 27

Desmos, 52 bytes

L=l.length-2
f(l)=total(2^{[L...0]}l[2...])-2^Ll[1]2

\$f(l)\$ takes in a list of bits and outputs the corresponding decimal form.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 28

TI-Basic, (削除) 35 (削除ここまで) 29 bytes

sum(Ansseq(2^(dim(Ans)-I)(1-2(I=1)),I,1,dim(Ans

Takes input as a list of digits in Ans. Output is as an integer in Ans and is displayed.

Answer 29

Javascript (ES2020), 33 chars

s=>BigInt.asIntN(s.length,"0b"+s)

Test:

f=s=>BigInt.asIntN(s.length,"0b"+s)
console.log(`0 -> 0
1 -> -1
111 -> -1
011 -> 3
100 -> -4
1001 -> -7
0001 -> 1`.split`
`.map(x=>x.match(/^(\S+) -> (\S+)$/))
.every(([,s,key])=>f(s)==key))

Answer 30

Piet + ascii-piet, 46 bytes

tlrdveccsittttttbbbuebV???? vuikuemmaiitdem vV

Input the binary as a string space separated bits, with 2 being the sentinel value (2 is a valid sentinel value because the input only contains 0's and 1's). For example, 1001 is inputted as 1 0 0 1 2.

Try It Online!

Image format (46 codels)

Enlarged for clarity (codel size = 50)

• Romanp: Do you use this input format because it's easier to find the position of the "2" than to find the length of the whole thing?
• Aiden Chow: @Romanp I chose this input format because in Piet, it is hard to check when all the input has been read. The code does not find the position of the 2 per se, but instead the 2 is used to indicate to the program that it should terminate after reading that input (each bit is read one at a time, with the 2 being read last). You are also correct in saying that it would be hard to find the length of the input, because of reasons listed above, and also because Piet does not have a code instruction to return the length of the stack, which would be helpful in determining the length of the input.