Обнаружение отрицательных целых чисел с использованием битовых операций

Question

Один из способов проверить, является ли данное целое число отрицательным или нет, может быть следующим: ( с использованием битовых операций )

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 бит размера?

Answer 1

ПРИМЕЧАНИЕ. C и C ++ - это разные языки.Их соответствующие стандарты развивались несколько независимо, и у них есть различные формальные ограничения на числовое представление.

---

Можем ли мы написать такой код, который будет и переносимым, и совместимым со стандартом?

Предполагая, что вам требуется общий метод идентификации и интерпретации знакового бита, я думаю, что ответ на ваш вопрос - нет.

Относительно C ++: я не думаю, что в стандарте есть явныйТребование о наличии знакового бита.Даже если каждая реализация использует знаковый бит, нет гарантии, что это первый (старший разряд) бит, как предполагает ваш код.Кроме того, бит может иметь противоположную интерпретацию от того, что вы предполагаете (значение «1» для знакового бита может означать, что число положительное).

Относительно C99: язык требует знаковый бит итребует, чтобы знак = 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;

В этой статье Википедии обсуждаются некоторые различные способы, которыми числа со знакомможет быть представлен в двоичном виде: Представление чисел со знаком

Вот информационный пост о числах со знаком в стандарте C99 .

Answer 2

Приведите целое число к соответствующему типу без знака, и тогда вам не нужно беспокоиться о том, какое подписанное представление используется. Единственная оставшаяся проблема заключается в том, что могут быть биты заполнения. Вот решение без сдвига битов и, следовательно, без зависимости от width в битах, соответствующих size в битах:

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

Answer 3

Расширение на метод Rs:

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), просто используйте самый большой тип unsigned int вашей платформы.

Answer 4

Используйте что-то вроде обтекания битов с использованием кругового сдвига, чтобы вы могли получить последний бит под большим пальцем в начале строки битов, а затем 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);
}