# Convert from variable-width Two's Complement to Integer

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*#[] & This implementation takes input as a list of digits.

Code-golf, so shortest solution wins.

• I suggest you add an explanation of how to convert from 2's Complement Mar 23, 2022 at 18:09
• 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? Mar 27, 2022 at 1:47
• 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.) Mar 27, 2022 at 2:57
• Shouldn't 111 produce -3 instead of -1? Mar 27, 2022 at 12:30
• @LorenDB No? 111 is -1*(2^2) + 1*(2^1) + 1*(2^0) = -4 + 2 + 1 = -1. Mar 28, 2022 at 15:03

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

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


# JavaScript (Node.js), 26 bytes

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


Try it online!

• 25
– l4m2
Mar 24, 2022 at 4:24

# Python 3.8 (pre-release), 33 bytes

lambda n:2*int(n,2)-int(n+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).

• nice! didn't even think of this. Mar 24, 2022 at 12:48
• Merging the two: n:int(n[1:],2)-int(n,2)
– G B
Mar 24, 2022 at 13:29
• @GB the first term needs a factor 2. Also, int doesn't accept empty string. Mar 24, 2022 at 13:38
• 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
– G B
Mar 24, 2022 at 15:06

s/.//;$_=-$&*2**y///c+oct"0b$_"  Try it online! • Mar 24, 2022 at 4:34 • Mar 24, 2022 at 12:44 # Python 3.8 (pre-release), 38 bytes lambda n:(a:=int(n,2))-(a*2&2**len(n))  Try it online! # Wolfram Language (Mathematica), 20 bytes Fold[#+##&,-#,!##2]&  Try it online! Input [digits...]. Negates the first bit, and takes the rest as normal. # 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. • 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". Mar 27, 2022 at 1:48 • @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. Mar 27, 2022 at 2:01 • Working on a quick answer myself, I think it's as easy as the asm sequence in my comment posted, for a function. Mar 27, 2022 at 2:02 • @petercordes awesome! Can't wait to see it! Mar 27, 2022 at 2:15 • Yup, 7 bytes for those instructions in 32 or 64-bit mode. Most of the time went into writing the text. Mar 27, 2022 at 2:27 # 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. • 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. Mar 27, 2022 at 1:58 # 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!

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
N   # Negate
|  # Otherwise...
B # Convert to decimal


# R, 42403937 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.

• 40 bytes using x[-1]^0 because of course 0^0==1 in R. Mar 23, 2022 at 17:29
• @Giuseppe Ah, that's neat. Thanks! Mar 23, 2022 at 17:37
• 35 bytes porting mine
– att
Mar 23, 2022 at 18:09
• @att I think you should post it as a separate answer. Mar 23, 2022 at 18:43
• 34 bytes now posted... Mar 24, 2022 at 9:07

# 05AB1E, 5 bytes

ć(š2β


Input as a list of bits.

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

Explanation:

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

• congrats on 100k rep! :-) Mar 24, 2022 at 15:41

# R, 34 bytes

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

Attempt This Online!

Test setup borrowed from pajonk's R answer.

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

• 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. Mar 27, 2022 at 15:12
• 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. Mar 28, 2022 at 13:00
• @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. Mar 28, 2022 at 20:03

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

• 46 bytes
– att
Mar 23, 2022 at 21:17
• @att Nice one - thanks! :D Mar 23, 2022 at 21:25
• 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.) Mar 27, 2022 at 1:59

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

# MathGolf, 8 bytes

å∞l├∞▌å-


Input as a string.

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)


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


Try it online!

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.

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
example: [1,0,0,1] ->  -1 (initial -h) * 2 + 1 = -1
[0,0,1]   -> -1 * 2 + 0 = -2
[0,1]     -> -2 * 2 + 0 = -4
       -> -4 * 2 + 1 = -7 (output)

• As you're already dissecting the input's head and tail, feeding -h directly into the initial value of foldl gives 27. Mar 25, 2022 at 5:50

# Pari/GP, 29 bytes

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

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


Try it online!

# JavaScript (Node.js), 51 49 bytes

s=>2**s.length/2*-s+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!

• Fails on test case with 111. Output should be -1, but your output is -3 Mar 23, 2022 at 18:18
• @ophact oops, apparently I forgot how twos complement works. Fixed at the cost of 11 bytes Mar 23, 2022 at 19:16
• save 1 byte by using s.slice() instead of s.substr() Mar 30, 2022 at 21:47

# 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


# Charcoal, 10 bytes

Ｉ↨ＥＡ⎇κι±ι²


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

   Ａ        Input array
Ｅ         Map over elements
κ      Current index
⎇       If nonzero then
ι     Current bit else
ι   Current bit
±    Negated
↨       ²  Convert from base 2
Ｉ           Cast to string
Implicitly print


# Retina 0.8.2, 46 bytes

^1
-
1
01
+(-|1)0
0$1$1
+-1|0

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


Try it online! Link includes test cases. Explanation:

^1
-


Change a leading 1 to a -.

1
01
+(-|1)0
0$1$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.

# Ruby, 28 bytes

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


Try it online!

# APL+WIN, 27 bytes

Prompts for two's compliment as vector of integers

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


Try it online! Thanks to Dyalog APL Classic

# Desmos, 52 bytes

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


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

Try It On Desmos!

Try It On Desmos! - Prettified

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

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

# 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) • 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? Apr 6, 2022 at 14:10
• @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. Apr 7, 2022 at 0:30