Two's complement
Two's complement is an important concept in representing negative numbers. To turn a positive integer negative, flip the bits and add one.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Show how to calculate the two's complement of an integer. (It doesn't necessarily need to be a 32 bit integer.)
6502 Assembly
8-Bit
<lang 6502asm>LDA #%01010101 EOR #255 CLC ADC #1 ;result: #%10101011</lang>
16-bit
<lang 6502asm>myVar equ $20
LDA #3 STA myVar LDA #0 STA myVar+1 ;equivalent C: uint16_t myVar = 3;
negate: LDA myVar+1 EOR #255 STA myVar+1
LDA myVar EOR #255 STA myVar CLC ADC #1 STA myVar
- this handles the case if we started with something where the low byte was zero.
LDA myVar+1 ADC #0 STA myVar+1</lang>
8086 Assembly
<lang asm>mov al,17 neg al ;8-bit mov bx,4C00h neg bx ;16-bit</lang>
ALGOL 68
Algol 68 uses whatever representation the hardware the program is running on uses, which is almost certainly two's complement. So, as in C and most other languages, -a
two's complements a
. Using Algol 68's bit manipulation facilities, we can explicitely two's complement a positive integer, as shown in this example.
Note: BIN a converts a to a BITS (bit-string) value, the NOT operator will flip the bits and the ABS operator will convert back to an integer, so 1 + ABS NOT BIN a
is a long-winded alternative to -a
. Note in Algol 68, the BIN operator cannot be applied to negative integers, so 1 + ABS NOT BIN -3
won't work.
<lang algol68>BEGIN
INT a := 3; print( ( -a, " ", 1 + ABS NOT BIN a, newline ) )
END</lang>
- Output:
-3 -3
ALGOL W
<lang algolw>begin
integer a; a := 3; write( i_w := 1, s_w := 1, -a, 1 + number( not bitstring( a ) ) )
end.</lang>
- Output:
-3 -3
C
<lang C>int a = 3; a = -a;</lang>
J
J uses twos complement natively: <lang J> -3 _3</lang>
We can see this by extracting bits representing the number. In this example, we limit ourselves to 8 bits:
<lang J> (8#2)#:3 0 0 0 0 0 0 1 1
(8#2)#:-3
1 1 1 1 1 1 0 1</lang>
Julia
In Julia as in C, if a number n is any integer type, then -n is the two's complement of n, with type preserved. This is true even if n is unsigned.
Phix
inline assembly
without js integer a = 0b000011, a2c #ilASM{ [32] mov eax,[a] neg eax mov [a2c],eax [64] mov rax,[a] neg rax mov [a2c],rax } printf(1,"%032b -> %032b\n",{a,a2c})
- Output:
00000000000000000000000000000011 -> 11111111111111111111111111111101
normal hll
with javascript_semantics integer a = 0b000011 printf(1,"%032b -> %032b\n",{a,-a})
Same output (naturally the rhs is twice as long under 64 bit, in both cases)
PL/M
... under CP/M (or an emulator)
Even though the original PL/M 8080 compiler only handles unsigned integers, -A
two's complements A
.
<lang pli>100H: /* TWO'S COMPLEMENT *?
/* CP/M BDOS SYSTEM CALL */ BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5;END; /* CONSOLE OUTPUT ROUTINES */ PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END; PR$HEX: PROCEDURE( B ); /* PRINTS B AS A 2 DIGIT HEX NUMBER */ DECLARE B BYTE; DECLARE D BYTE; IF ( D := SHR( B, 4 ) ) > 9 THEN CALL PR$CHAR( ( D - 10 ) + 'A' ); ELSE CALL PR$CHAR( D + '0' ); IF ( D := B AND 0FH ) > 9 THEN CALL PR$CHAR( ( D - 10 ) + 'A' ); ELSE CALL PR$CHAR( D + '0' ); END PR$HEX ;
DECLARE A BYTE;
A = 1; CALL PR$HEX( A ); CALL PR$CHAR( ' ' ); A = -A; CALL PR$HEX( A ); CALL PR$NL;
EOF</lang>
- Output:
01 FF
Raku
By default Rakus integers are arbitrary sized, theoretically of infinite length. You can't really take the twos complement of an infinitely long number; so, we need to specifically use fixed size integers.
There is a module available from the Raku ecosystem that provides fixed size integer support, named (appropriately enough.) FixedInt.
FixedInt supports fixed bit size integers, not only 8 bit, 16 bit, 32 bit or 64 bit, but ANY integer size. 22 bit, 35 bit, 191 bit, whatever.
Here we'll demonstrate twos complement on a 57 bit integer.
<lang perl6>use FixedInt;
- Instantiate a new 57(!) bit fixed size integer
my \fixedint = FixedInt.new: :57bits;
fixedint = (2³⁷ / 72 - 5¹⁷); # Set it to a large value
say fixedint; # Echo the value to the console in decimal format say fixedint.bin; # Echo the value to the console in binary format
fixedint.=C2; # Take the twos complement
say fixedint; # Echo the value to the console in decimal format say fixedint.bin; # Echo the value to the console in binary format</lang>
- Output:
144114427045277101 0b111111111111111110100111011001111000010101110110110101101 761030578771 0b000000000000000001011000100110000111101010001001001010011
Wren
Strictly speaking, Wren doesn't have integers. Instead all numbers are 'IEEE 754' 64 bit floating point values (their underlying C type being double) and negative numbers are therefore represented using the offset binary method rather than two's complement.
This is illustrated by running the following code: <lang ecmascript>var a = 0 a = -a System.print(a) // -0</lang> which produces 'negative zero' rather than just 'zero'.
However, when using the bitwise operators, Wren's VM emulates the corresponding operation in C by first converting the operands to unsigned 32 bit values, performing the operation and then converting the result back to a double.
We can therefore emulate how two's complement works on signed 32 bit integers by using the bitwise complement operator ~ to flip the bits as follows:
<lang ecmascript>var pow32 = 2.pow(32) var pow31 = 2.pow(31) var bs = [-pow31, -pow31+1, -2, -1, 0, 1, 2, pow31-2, pow31-1] for (b in bs) {
var b2 = ~b + 1 if (b2 > pow31) b2 = b2 - pow32 System.print("%(b) -> %(b2)")
}</lang>
- Output:
-2147483648 -> 2147483648 -2147483647 -> 2147483647 -2 -> 2 -1 -> 1 0 -> 0 1 -> -1 2 -> -2 2147483646 -> -2147483646 2147483647 -> -2147483647
Z80 Assembly
8-Bit
Zilog Z80
<lang z80>ld a,%00001111 neg ;returns %11110001 in a</lang>
Game Boy <lang z80>ld a,%00001111 cpl ;game boy doesn't have NEG but it has CPL which flips all the bits. inc a ;returns %11110001 in a</lang>
16 Bit
NEG
and CPL
only work on the accumulator A
.
The following can be written to work with BC
, DE
, HL
, IX
, or IY
.
<lang z80>xor a ;ld a,0
sub c
ld c,a
sbc a ;loads &FF into A if "sub c" set the carry (borrow) flag. Otherwise, a remains zero.
sub b
ld b,a</lang>