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