Two's complement using overflow

Question

On Stack Overflow, some people have already answered the question of converting an integer in binary notation to two's complement. Anyway, I did not find any of the answers I saw satisfactory because they do not consider the number of bits being predetermined. Also, the code I found on Stack Overflow crashes the terminal or gives strange errors with large numbers.

For these reasons, I have rewritten the following Bash function from scratch, which seems to accomplish the task I wish to give it correctly. I have commented on the code for clarity.

As you can see, I intentionally generate an overflow, in the line: x=$((2**($bits-1)-$x));

My question is whether this code is always reliable in Bash since, in other languages, the overflow is an error condition; here, however, I use it to get the desired result.

# Given a decimal number, prints its two's complement with the number of bits used by Bash
twos() {
    x=$1; # input number in base 10
    msb="0"; # the "most significant bit" is 0 for positive integers, 1 for negative integers
    bits=$(getconf LONG_BIT); # detect the machine architecture, 32bit or 64bit
    if [ "$x" -lt 0 ]; then
        # the input number $x is negative
        x=$((2**($bits-1)-$x)); # 2^(bits-1)-1 is the max integer number, -$x is positive, so it's an overflow
        msb="1"; # "most significant bit" of negative numbers
    fi
    out=$(echo "obase=2;$x" | bc | tr -dc '0-9'); # conversion of $x to binary base, any sign is removed
    n=$(($bits-1-${#out})); # number of zeros to add
    if [ "$n" -gt 0 ]; then
        zeros=$(printf '%0.s0' $(seq 1 $n)); # string consisting only of zeros
    else
        zeros=""; # deletes the variable that may be left in memory from a previous function call
    fi
    echo $msb$zeros$out; # prints the two's complement
}

Some examples:

$ twos 0
0000000000000000000000000000000000000000000000000000000000000000
$ twos 1
0000000000000000000000000000000000000000000000000000000000000001
$ twos 2
0000000000000000000000000000000000000000000000000000000000000010
$ twos 100
0000000000000000000000000000000000000000000000000000000001100100
$ twos -1
1111111111111111111111111111111111111111111111111111111111111111
$ twos -2
1111111111111111111111111111111111111111111111111111111111111110
$ twos -100
1111111111111111111111111111111111111111111111111111111110011100
$ twos 9223372036854775807
0111111111111111111111111111111111111111111111111111111111111111
$ twos -9223372036854775808
1000000000000000000000000000000000000000000000000000000000000000

Renaud Pacalet · Accepted Answer · 2022-06-20 14:18:47Z

2

A bit simpler:

twos() {
  n=$(getconf LONG_BIT)
  printf 'obase=2; 2^%d+%d\n' "$n" "$1" | bc | sed -E "s/.*(.{$n})$/\1/"
}

twos 100
0000000000000000000000000000000000000000000000000000000001100100

This simply uses bc to add 2^n (where n is 32 or 64), print in base 2 and keeps only the n least significant bits.

Note that technically the two's complement of a number is its opposite. So what you are looking for is more the binary representation of a number in two's complement.

edited Jun 20, 2022 at 14:18

answered Jun 20, 2022 at 13:09

Renaud Pacalet

30.7k3 gold badges42 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Francesco Galgani Over a year ago

First of all, thank you for your great simplification of my code. The "the binary representation of a number in two's complement" is exactly what I'm looking for. More specifically, I want to see the bits on which Bash's bitwise operators act. As far as I know, the two's complement is not just the inversion of all bits, but the inversion of all bits plus the sum of 1.

Renaud Pacalet Over a year ago

In 2's complement (2C), different from Sign and Magnitude (SM), the most significant bit is not just a sign. It contributes the value but with a negative weight. So, on 4 bits and 2C, 1010 represents -8+2=-6. While in SM 1010 represents -2. Computing the opposite in SM is super easy: you just flip the sign bit. The opposite of 1010 (-2) is 0010 (2). In 2C it is a bit more complex: you must flip all bits and add 1. The opposite of 1010 (-6) is 0101+1 = 0110 (6). More complex but additions and subtractions are easier, reason why 2C is more frequently used.

Francesco Galgani Over a year ago

I tried to create a function that is the inverse of yours, but I failed. I posted it in a sepate question: stackoverflow.com/questions/72691181/…

Collectives™ on Stack Overflow

Two's complement using overflow

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related