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.

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!

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

Answer 5

Perl 5 -pl, 31 bytes

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

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.

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

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.

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)

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.

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.

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)

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), ⁵¹ 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!

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

Ｉ↨ＥＡ⎇κι±ι²

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

Answer 24

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.

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+¯2×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)