Bit bit shifting e scartare bit

Question

Consideriamo la funzione (una delle possibili implementazioni di esso) che azzererebbe correttamente N bit di un valore corto senza segno (o qualsiasi altro tipo integrale senza segno). Il possibile implementazione potrebbe apparire come segue:

template<unsigned int shift> 
unsigned short zero_right(unsigned short arg) { 
    using type = unsigned short; 

    constexpr type mask = ~(type(0)); 
    constexpr type right_zeros = mask << shift; // <-- error here 
    return arg & right_zeros; 
} 

int check() { 
    return zero_right<4>(16); 
} 

Con questo codice, tutti i compilatori ho accesso a lamentarsi, in un modo o nell'altro, su possibili troppo pieno. Clang è il più esplicito, con seguente messaggio chiaro:

error: implicit conversion from 'int' to 'const type' (aka 'const unsigned short') changes value from 1048560 to 65520 [-Werror,-Wconstant-conversion]

Questo codice è ben definito e chiaro come il sole per me, ma quando 3 compilatori si lamentano, sto diventando molto nervoso. Mi sto perdendo qualcosa qui? C'è davvero una possibilità che qualcosa di strano stia succedendo?

P.S. Mentre le implementazioni alternative di zeriong out X bits a sinistra potrebbero essere benvenute e interessanti, l'obiettivo principale di questa domanda è la validità del codice come postata.

Answer 1

Il messaggio sembra piuttosto semplice:

error: implicit conversion from 'int' to 'const type' (aka 'const unsigned short') changes value from 1048560 to 65520 [-Werror,-Wconstant-conversion]

mask << shift ha valore 1048560 (derivante da 65535 << 4), e assegnarlo a unsigned short, che è definito per regolare il valore mod 65536, dando 65520.

Quest'ultima conversione è ben definita. Il messaggio di errore è perché hai passato i flag del compilatore -Werror,-Wconstant-conversion richiedendo comunque di ricevere un messaggio di errore in questa situazione. Se non vuoi questo errore, allora non passare quelle bandiere.

---

Sebbene questo uso particolare è ben definito, ci potrebbe essere un comportamento indefinito per alcuni input (cioè, shift essendo 16 o maggiore, se in un sistema int 32-bit). Quindi dovresti correggere la funzione.

Per risolvere la funzione è necessario essere più attenti nel caso unsigned short, a causa della regola estremamente fastidiosa sulla promozione di interi di unsigned short to signed int.

Ecco un'unica soluzione un po 'diversa dalle altre offerte .. evitare il problema del cambio del tutto, funziona per qualsiasi dimensione turno:

template<unsigned int shift, typename T> 
constexpr T zero_right(T arg) 
{ 
    T mask = -1; 
    for (int s = shift; s--;) mask *= 2u; 
    return mask & arg; 
} 

// Demo 
auto f() { return zero_right<15>((unsigned short)65535); } // mov eax, 32768 

Answer 2

Dalla C++ 11 standard:

5.8 Shift operators [expr.shift]

1 ...

The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand.

L'espressione

mask << shift; 

viene valutata dopo promozione integrale viene applicata a mask. Quindi, valuta 1048560 se sizeof(unsigned short) è 2, il che spiega il messaggio da clang.

Un modo per evitare il problema di trabocco è spostare a destra prima di eseguire uno spostamento a sinistra e spostarlo in una funzione a sé stante.

template <typename T, unsigned int shift> 
constexpr T right_zero_bits() 
{ 
    // ~(T(0)) performs integral promotion, if needed 
    // T(~(T(0))) truncates the number to T, if needed. 
    return (T(~(T(0))) >> shift) << shift; 
} 

template<unsigned int shift> 
unsigned short zero_right(unsigned short arg) { 
    return arg & right_zero_bits<unsigned short, shift>(); 
} 

Answer 3

Non so se questo è esattamente ciò che si vuole, ma si compila:

template<unsigned int shift> 
unsigned short zero_right(unsigned short arg) { 
    using type = unsigned short; 

    //constexpr type mask = ~(type(0)); 
    type right_zeros = ~(type(0)); 
    right_zeros <<= shift; 
    return arg & right_zeros; 
} 

int check() { 
    return zero_right<4>(16); 
} 

---

UPDATE:

Seems like you simply hushed the compiler by making sure it has no idea what is going on with the types.

No

Fi per prima cosa ottieni right_zeros con il valore FFFF (da ~0). Normalmente, ~0 è FFFFFFFFFFFFFF... ma poiché si utilizza u16, si ottiene FFFF.

Poi, spostamento da 4 produce FFFF0 [calcolo è esteso a 32 bit], ma se conservato indietro, solo più a destra 16 bit rimangono, quindi il valore è FFF0

Questo è perfettamente comportamento legale e definito e sto approfittando del troncamento. Il compilatore è non "essere ingannato". In realtà, funziona bene con o senza troncamento.

Si potrebbe fare right_zeros in U32 o U64, se si voleva, ma poi si sarebbe necessario aggiungere right_zeros &= 0xFFFF

If there is an undefined behavior (the very essence of my question!) you simply made it undetectable.

Non v'è alcun UB in base alla totalità del codice, non importa quale sia il dice il compilatore.

In realtà, Tavian ha capito. Utilizzare un cast esplicito:

constexpr type right_zeros = (type) (mask << shift); // now clean 

Questo sta dicendo il compilatore, tra le altre cose, che si desidera il troncamento a 16 bit.

Se ci fosse UB, il compilatore dovrebbe comunque lamentarsi.

Answer 4

Sì, come sospetti, anche dopo aver soppresso la diagnostica del compilatore, il tuo codice non è del tutto portabile a causa della promozione da breve intinta a non firmata, l'aritmetica dei bit viene eseguita in int con segno e quindi con firma int convertita di nuovo a breve non firmato. Sei riuscito a evitare un comportamento indefinito (credo, dopo un rapido sguardo), ma il risultato non è garantito per quello che speri. (type)~(type)0 non è richiesto per corrispondere a "tutti i bit uno" nel tipo type; è già incerto prima del turno.

Per ottenere qualcosa di completamente portatile, è sufficiente assicurarsi di eseguire tutte le operazioni aritmetiche in almeno unsigned int (tipi più ampi se necessario, ma mai più ristretti). Quindi non ci saranno promozioni a tipi firmati di cui preoccuparsi.

template<unsigned int shift> 
unsigned short zero_right(unsigned short arg) { 
    using type = unsigned short; 

    constexpr auto mask = ~(type(0) + 0U); 
    constexpr auto right_zeros = mask << shift; 
    return arg & right_zeros; 
} 

int check() { 
    return zero_right<4>(16); 
}