logo标签列表

使用位运算检测负整数

c++cbinary
5

判断一个整数是否为负数的一种方法是（使用位运算）：

int num_bits = sizeof(int) * 8; //assuming 8 bits per byte!
int sign_bit = given_int & (1 << (num_bits-1)); //sign_bit is either 1 or 0
if ( sign_bit )
{
     cout << "given integer is negative"<<endl;
}
else
{
     cout << "given integer is positive"<<endl;
}

这种解决方案的问题在于每个字节的位数不能固定为8，可能是9、10、11甚至16或40位。字节并不一定意味着8位！无论如何，可以通过编写以下内容轻松解决此问题：
//CHAR_BIT is defined in limits.h
int num_bits = sizeof(int) * CHAR_BIT; //no assumption.

现在看起来没问题，但它真的没问题吗？这符合标准吗？如果负整数不是以2的补码表示怎么办？如果它在二进制计数系统中的表示方式不需要只有负整数才在最高位有1呢？
我们能写出既可移植又符合标准的代码吗？
相关主题：
原始数据类型的大小
为什么布尔值占用1个字节而不是1个比特？
16
given_int < 0 的问题在哪里？ - Chris Lutz
2
@Chris：没什么问题，只是我想“使用位运算”来完成它。 - Nawaz
2
@Nawaz - 如果你找到比“<”运算符更快的东西，我会很感兴趣。虽然我想大多数编译器都会将“<”运算符实现为你最终找到的任何东西。但是干杯。 - Chris Lutz
2
这是错误的。标准没有指定整数表示。因此，您假设最高位将有助于识别负数。附言：很高兴您找到了CHAR_BITS。 - Martin York
@Chris：我并不是在声称自己更快。我只是出于好奇想要“使用位运算”来完成它。- Nawaz 10小时前 - Nawaz
@Martin：没错，就是我的意思。标准没有规定整数的表示方式！ - Nawaz
4个回答
4

注意：C和C++是不同的语言。它们各自的标准有所发展，并且在数字表示上有不同的正式限制。

我们能否编写既具有可移植性又符合标准的代码？

假设您需要一种通用方法来识别和解释符号位，我认为您的问题的答案是否定的。

关于C ++：我认为标准没有明确要求存在符号位。即使每个实现都使用一个符号位，也不能保证它是您的代码所假定的第一个（高位）位。此外，该位可能具有与您所假定的相反的解释（符号位的“1”值可能意味着数字为正数）。

关于C99：该语言确实需要一个符号位，并且要求sign = 1表示负数（尽管它可能是“负零”）。但是，语言标准没有为您提供确定符号位位置的通用方法。

以下代码尝试以通用方式创建“sign_mask”，但不能绝对保证在C99或C ++中工作。失败的原因包括上述原因，但最有趣的是，它可能会引发“陷阱表示”（例如奇偶校验位错误）...

#ifdef __cplusplus
   #define INT_MAX std::numeric_limits<int>::max()
   #define UINT_MAX std::numeric_limits<unsigned int>::max() 
#endif

// assumes sign bit becomes high-order bit of unsigned
   int sign_mask = INT_MAX ^ UINT_MAX; 

// fallback in case unsigned type doesn't take advantage of the sign-bit
// This might invoke a "trap representation" on some platforms
   if (sign_mask==0) sign_mask = ~INT_MAX;

这篇维基百科文章讨论了有关二进制中表示带符号数字的不同方式：Signed number representations

这是一篇关于C99标准中带符号数字的信息性文章。

@nober：你怎么会说 ~std::numeric_limits<int>::max(); 必须返回 符号掩码? - Nawaz
结果将具有所有未用于表示无符号数字的位设置--换句话说，只有符号位将被设置。这假定最大值比2的幂少1，这通常是情况，但标准可能不能保证。 - Brent Bradburn
1
我不确定 given_int & sign_mask 是否因为填充而成为陷阱表示。 - AProgrammer
1
C 确实对存在符号位有显式要求。 - R.. GitHub STOP HELPING ICE
1
我不会说C++和C标准是独立发展的，因为它们之间有很强的相互影响。 - AProgrammer
显示剩余3条评论
2

将整数转换为相应的无符号类型，然后您就不必担心使用的有符号表示。唯一剩下的问题是可能存在填充位。以下是一种解决方案，没有位移操作，并且因此不依赖于以位为单位的宽度与以位为单位的大小匹配：

#define IS_NEG(x) ((unsigned_type)x & (unsigned_type)-1-(unsigned_type)-1/2)
2
如果您在转换中使用 uintmax_t，则无需担心 x 的原始类型。 - Chris Lutz
@Chris：非常正确。希望优化器能够避免实际扩展到更多位，但我不确定… - R.. GitHub STOP HELPING ICE
1
将有符号类型转换为无符号类型被定义为对目标类型的最大值加一取模减少，也称为转换为二进制补码。这同样适用于常数“-1”，在减法后只返回最高位设置的结果。 - R.. GitHub STOP HELPING ICE
1
@R.. - 我以前不知道这一点，但我查了一下，标准确实说将带符号类型转换为无符号类型会转换为二补数表示法。那么这是否意味着我们可以这样做：const int x = -1; if((unsigned)x == *(unsigned *)&x) { /* 二补数 */ } else { /* 其他表示 */ } （忽略 *(unsigned *)&x 显然是未定义行为的部分）？ - Chris Lutz
3
无符号整数的范围可能与有符号整数相同，这种情况下宏将对 -1 和 INT_MAX 给出相同的结果。 - AProgrammer
显示剩余5条评论
0

使用类似于位包装的循环移位技术，这样你就可以在位串的开头获取最终的位，并且使用bool neg = n & 1;或其他方法进行操作。以下是一些位包装的代码：

template <typename T>
inline T rotate_left(T val, unsigned char shift=1)
{
    static const bits = sizeof(T) * CHAR_BIT;
    return (val >> (bits-shift)) | (val << shift);
}

template <typename T>
inline T rotate_right(T val, unsigned char shift=1)
{
    static const bits = sizeof(T) * CHAR_BIT;
    return (val << (bits-shift)) | (val >> shift);
}

// And now for some platform-dependant specializations...

#include <intrin.h>

template<>
inline unsigned char rotate_left(unsigned char val, unsigned char shift=1)
{
    return _rotl8(val, shift);
}

template<>
inline unsigned char rotate_right(unsigned char val, unsigned char shift=1)
{
    return _rotr8(val, shift);
}

template<>
inline unsigned int rotate_left(unsigned int val, unsigned char shift=1)
{
    return _rotl(val, shift);
}

template<>
inline unsigned int rotate_right(unsigned int val, unsigned char shift=1)
{
    return _rotr(val, shift);
}

template<>
inline unsigned long long rotate_left(unsigned long long val, unsigned char shift=1)
{
    return _rotl64(val, shift);
}

template<>
inline unsigned long long rotate_right(unsigned long long val, unsigned char shift=1)
{
    return _rotr64(val, shift);
}
我在你的回复中没有看到任何讨论。它是否符合标准并且可移植？ - Nawaz
似乎是可以的。我没有看到任何与此相关的问题。 - Chris Dennett
如何检测负整数？ - Nawaz
如上所述：rotate_left(n) 然后 boolean x = n & 1。如果 n == 1，则为负数。模板从给定值中推断类型，其默认移位为1。它适用于所有基本类型。 - Chris Dennett
右移有符号值是实现定义的。最常见的定义会使您对左旋转的定义无效，但这是可以修复的。不幸的是，为有符号数和幅度定义右移只涉及幅度是一种现有的做法，这将阻止修复您的方法。转换为无符号将不起作用（无符号可能仅具有与正整数相同的范围）。我还没有尝试思考整数内部填充的影响。 - AProgrammer
0

在R的方法基础上进行扩展：

template <typename T> is_negative(T v) {
    boost::make_unsigned<T>::type u(v);
    return (u & (1 << std::numeric_limits<T>::digits - 1));
}

如果您不喜欢使用boost（make_unsigned在type_traits中），只需使用您平台的最大无符号整型。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接