在C++中将带符号的整数值转换为可排序的无符号的标准兼容方法是什么？

Question

我有一个用例,我需要将签名值转换为unsigned,以使值可排序.我需要这个char,short,int,long,和long long

通过排序,我的意思是对于signed类型X,如果(a < b)然后转换为无符号的converted(a) < converted(b).请注意,在许多情况下,从负值signed直接转换为unsigned值将使值大于0并打破此约束(二进制补码实现)

最简单的想法char是:

unsigned char convert(char x)
{
       return (unsigned char)(x ^ 0x80);  // flip sign to make it sortable
}

但这似乎是undefined behavior.

虽然有可能转换为更大的类型,添加类型MIN值,并转换为unsigned类型,我不确定这是否更合规,并且不能用于long long

如何在没有任何undefined behavior类型的情况下完成这项工作？

使用转换似乎是安全的memcpy,但不清楚如何以兼容的方式维护排序顺序.

(注意,这类似于:没有兼容的方式来转换相同大小的有符号/无符号,除了我需要保持排序顺序的结果)

Answer 1

你做错了,因为实际上没有定义有符号值的翻转符号位.

我们使用两位类型:

          00    01 10  11  Order for unsigned               0     1  2  3
10  11    00    01         Order for 2s complement -2 -1    0     1
    11 (10  00) 01         Order for sign-magnitude   -1 (-0 +0)  1
    10 (11  00) 01         Order for 1s-complement    -1 (-0 +0)  1

你想要做的是转换为无符号(它总是被定义为保值,带环绕),然后添加偏差,使得最负数变为0:

int x = whatever;
unsigned r = (unsigned)x - (unsigned)INT_MIN;

注意:未定义有符号溢出,因此我们避免使用签名类型.

当然,如果无符号类型的值少于有符号类型,则无效,这通常是允许的,但不是char.
如果你想将负0保持为负数,你需要特别小心.

Answer 2

如果您想保持完全便携,这是不可能的.

范围unsigned int仅指定为至少覆盖非负值int.该标准允许实现UINT_MAX == INT_MAX.这同样适用于所有其他非固定宽度整数类型.

鉴于范围unsigned int可能小于,范围int原则适用:您无法将所有值重新分配int到相应但不同的值,unsigned int除非unsigned int可以存储至少与其不同的值int.

引用N4140(大致是C++ 14):

3.9.1基本类型[basic.fundamental]

1 [...]对于窄字符类型,对象表示的所有位都参与值表示.对于无符号窄字符类型,值表示的所有可能位模式表示数字.这些要求不适用于其他类型.[...]

3对于每个标准有符号整数类型,存在相应的(但不同的)标准无符号整数类型:" unsigned char"," unsigned short int"," unsigned int"," unsigned long int"和" unsigned long long int",每个类型占用相同的存储量并具有与对应的有符号整数类型⁴⁷相同的对齐要求(3.11); 也就是说,每个有符号整数类型具有与其对应的无符号整数类型相同的对象表示.[...]有符号整数类型的非负值范围是相应无符号整数类型的子范围,每个对应的有符号/无符号类型的值表示应相同.[...]

这可以保证您没有问题unsigned char.没有unsigned char任何填充位的可能性.unsigned char有填充位是没有意义的:给定unsigned char c;,你将如何访问这些填充位？reinterpret_cast<unsigned char &>(c)？这显然只是给你c.唯一类似于填充位的unsigned char东西是对程序完全透明的东西,例如当使用ECC内存时.

对于所有其他非固定宽度整数类型,从shortto到long long"subrange"的标准含义允许相等的范围.

我想我模糊地回忆一下,可能有一些古老的CPU没有提供任何原生的无符号操作.这将使实现正确实现无符号除法变得非常棘手,除非它们声明无符号类型的将要符号位将被视为填充位.这样,他们可以简单地将CPU的带符号除法指令用于有符号或无符号类型.