Rilevazione degli interi negativi usando operazioni bit

Question

Un approccio per controllare se un dato intero è negativo o non, potrebbe essere questo: (usando operazioni bit)

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

Il problema di questa soluzione è che il numero di i bit per byte non potevano essere 8, poteva essere 9,10, 11 anche 16 o 40 bit per byte. Byte non significa necessariamente 8 bit! Ad ogni modo, questo problema può essere risolto facilmente scrivendo,

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

Adesso sembra a posto. Ma è davvero? Questo standard è conforme? Cosa succede se il numero intero negativo non viene rappresentato come complemento a 2? Che cosa succede se è la rappresentazione in un sistema di numerazione binaria che non richiede e richiede solo gli interi negativi per avere 1 nel suo bit più significativo?

Possiamo scrivere un codice che sia compatibile e conforme allo standard?

---

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

Answer 1

Fusioni il numero intero del tipo senza segno corrispondente e quindi non devi preoccuparti di ciò che ha firmato la rappresentazione è in uso. L'unico problema rimasto è che potrebbero esserci dei bit di riempimento. Ecco una soluzione con nessun bit spostamento e quindi non dipendenza da larghezza in bit corrispondenti alla dimensionein bit:

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

Answer 2

usare qualcosa di simile po involucro utilizzando spostamento circolare in modo da poter ottenere il bit finale sotto il pollice all'inizio della stringa di bit, quindi bool neg = n & 1; o qualcosa del genere. Ecco alcuni codice per bit di confezionamento:

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 3

NOTA: C e C++ sono linguaggi diversi. I rispettivi standard si sono evoluti in modo un po 'indipendente e hanno diverse restrizioni formali sulla rappresentazione numerica.

---

Possiamo scrivere tale codice, che sarà sia conforme portatile e di serie?

Supponendo che avete bisogno di un metodo generale di individuare e interpretare un bit di segno, credo che la risposta alla tua domanda è No.

Per quanto riguarda C++: non credo che lo standard ha un requisito esplicito per l'esistenza di un bit di segno. Anche se ogni implementazione utilizza un bit di segno, non vi è alcuna garanzia che sia il primo bit (di ordine elevato) come presuppone il codice. Inoltre, il bit potrebbe avere l'interpretazione opposta da ciò che si assume (un valore "1" per il bit del segno potrebbe significare che il numero è positivo).

Riguardo a C99: il linguaggio richiede un bit di segno e richiede che il segno = 1 indichi un numero negativo (anche se potrebbe essere "zero negativo"). Tuttavia, lo standard della lingua non ti dà un modo generale per determinare dove si trova il bit del segno.

Il seguente codice tenta di creare una "firma di segno" in modo generico, ma non è assolutamente garantito il funzionamento in C99 o C++. Le ragioni del fallimento sono quelli di cui sopra, ma più interessante, si potrebbe invocare una "rappresentazione trappola" (come ad esempio un errore di bit di parità) ...

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

questo articolo di Wikipedia discute alcuni modi diversi che hanno firmato i numeri possono essere rappresentato in binario: Signed number representations

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

Answer 4

Ampliando metodo R.s:

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

Se non vi piace l'uso di spinta (make_unsigned è in type_traits), basta usare il più grande tipo unsigned int della vostra piattaforma.