Signed Integers are Asymmetrical
source link: https://borretti.me/article/signed-integers-asymmetrical
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Signed Integers are Asymmetrical
What’s wrong with this code?
int8_t absolute(int8_t x) {
if (x >= 0) {
return x;
} else {
return -x;
}
}
Seems straightforward enough. Let’s try it with some representative numbers:
#include <stdint.h>
#include <stdio.h>
int8_t absolute(int8_t x) {
if (x > 0) {
return x;
} else {
return -x;
}
}
int main() {
int8_t values[5] = {INT8_MIN, INT8_MIN + 1, 0, INT8_MAX - 1, INT8_MAX};
for (int i = 0; i < 5; i++) {
int8_t x = values[i];
printf("abs(%4i) = %4i\n", x, absolute(x));
}
return 0;
}
Running this code yields:
eudoxia@bullroarer $ gcc cabs.c
eudoxia@bullroarer $ ./a.out
abs(-128) = -128
abs(-127) = 127
abs( 0) = 0
abs( 126) = 126
abs( 127) = 127
The very first case is wrong. Why? Because signed integers are asymmetrical
around zero. Note how INT8_MAX is 127, while INT8_MIN is -128. You can think
of it in terms of a number line, with the negative side being larger by one:
More generally: if a signed two’s complement number has n bits, the largest number it can represent is 2(n - 1) - 1, while the most negative number it can represent is -2(n - 1)
You can think of unary negation as rotating a number around zero on the number
line. Evaluating -(-127) rotates the number and lands on 127:
Evaluating -(-128) rotates the number around zero, but it lands one step beyond
INT8_MAX. Because of overflow, it lands right back on INT8_MIN.
Note that compiling with -ftrapv doesn’t help. Neither GCC nor Clang catch
this. Ada does, though:
with Ada.Text_IO;
procedure AdaAbs is
type Signed_Byte is new Integer range -128 .. 127;
function Absolute(X: Signed_Byte) return Signed_Byte is
begin
if X >= 0 then
return X;
else
return -X;
end if;
end Absolute;
type Index is range 1 .. 5;
type Value_Array is array (Index) of Signed_Byte;
Values: Value_Array := (127, 126, 0, -127, -128);
package Signed_Byte_IO is new Ada.Text_IO.Integer_IO (Signed_Byte);
begin
for I in Index loop
declare
X: Signed_Byte := Values(I);
begin
Ada.Text_IO.Put("abs(");
Signed_Byte_IO.Put(X);
Ada.Text_IO.Put(") = ");
Signed_Byte_IO.Put(Absolute(X));
Ada.Text_IO.New_Line;
end;
end loop;
end AdaAbs;
Running this yields:
eudoxia@bullroarer $ gnatmake adaabs.adb
x86_64-linux-gnu-gnatbind-10 -x adaabs.ali
x86_64-linux-gnu-gnatlink-10 adaabs.ali
eudoxia@bullroarer $ ./adaabs
abs( 127) = 127
abs( 126) = 126
abs( 0) = 0
abs(-127) = 127
abs(-128) =
raised CONSTRAINT_ERROR : adaabs.adb:11 range check failed
I only became aware of this issue from an AdaCore case study, probably this, about using SPARK Ada to prove overflow-safety in an implementation of the absolute value function. Here is such an implementation.
This case was a big part of my motivation for having pervasive overflow checking in Austral: the fact that the trivial implementation of the absolute value function – which matches its mathematical definition exactly – is subtly wrong should be humbling, and prove the futility of having programmers mentally track every overflow possibility.
The takeaway: when working with fixed-width integers, test on extremal
values. And don’t trust -ftrapv.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK