Detection of negative integers using bit operations

Question

One approach to check if a given integer is negative or not, could be this: (using bit operations)

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;
}

The problem with this solution is that number of bits per byte couldn't be 8, it could be 9,10, 11 even 16 or 40 bits per byte. Byte doesn't necessarily mean 8 bits! Anyway, this problem can be easily fixed by writing,

//CHAR_BIT is defined in limits.h
int num_bits = sizeof(int) * CHAR_BIT; //no assumption. 

It seems fine now. But is it really? Is this Standard conformant? What if the negative integer is not represented as 2's complement? What if it's representation in a binary numeration system that doesn't necessitate only negative integers to have 1 in it's most significant bit?

Can we write such code that will be both portable and standard conformant?

---

Related topics:
Size of Primitive data types
Why is a boolean 1 byte and not 1 bit of size?

Answer 1

NOTE: C and C++ are different languages. Their respective standards have evolved somewhat independently and they have differing formal restrictions on numeric representation.

---

Can we write such code that will be both portable and standard conformant?

Assuming that you require a general method of identifying and interpreting a sign bit, I think the answer to your question is No.

Regarding C++: I don't think that the standard has an explicit requirement for the existence of a sign bit. Even if every implementation uses a sign bit, there is no guarantee that it is the first (high-order) bit as your code assumes. Also, the bit could have the opposite interpretation from what you are assuming (a "1" value for the sign bit could mean that the number is positive).

Regarding C99: The language does require a sign bit and requires that sign=1 indicates a negative number (although it might be "negative zero"). However, the language standard does not give you a general way of determining where the sign bit is.

The following code attempts to create a "sign_mask" in a generic way, but it is not absolutely guaranteed to work in C99 or C++. Reasons for failure include those mentioned above, but most interestingly, it could invoke a "trap representation" (such as a parity bit error)...

#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;

This Wikipedia article discusses some different ways that signed numbers can be represented in binary: Signed number representations

Here's an informative post about signed numbers in the C99 standard.

Answer 2

Cast the integer to the corresponding unsigned type and then you don't have to worry about what signed representation is in use. The only remaining issue is that there may be padding bits. Here's a solution with no bit shifting and thus no dependence on width in bits matching the size in bits:

#define IS_NEG(x) ((unsigned_type)x & (unsigned_type)-1-(unsigned_type)-1/2)

Answer 3

Use something like bit wrapping using circular shift so you can get the final bit under your thumb at the start of the bit string, and then bool neg = n & 1; it or something. Here's some code for bit wrapping:

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);
}

Answer 4

Expanding on R.s method:

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

If you don't like the usage of boost (make_unsigned is in type_traits), just use your platform's biggest unsigned int type.