Przesunięcie bitów w lewo i odrzucenie bitów

Question

Rozważmy funkcję (jedną z możliwych implementacji), która wyzeruje prawe N bitów niepodpisanej krótkiej wartości (lub dowolnego innego typu bez znaku). Ewentualna realizacja może wyglądać jak następuje:

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

Z tym kodem, wszystkie kompilatory Mam dostęp do skarżą się, w taki czy inny sposób, o możliwym przepełnienia. Clang jest najbardziej wyraźny jeden z następujących jasny komunikat:

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

Ten kod wygląda dobrze określone i jasne jak dzień do mnie, gdy jeszcze 3 kompilatory skarżą się, staję się bardzo nerwowy. Czy coś mi umyka? Czy jest naprawdę szansa, że ​​dzieje się coś podejrzanego?

P.S. Podczas gdy alternatywne implementacje zerowania lewych bitów X mogą być mile widziane i interesujące, głównym celem tego pytania jest ważność opublikowanego kodu.

Answer 1

Przesłanie wydaje się dość prosty:

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

mask << shift ma wartość 1048560 (z tytułu 65535 << 4) i przypisać go do unsigned short, który jest zdefiniowany w celu dostosowania wartości mod 65536, dając 65520.

Ta ostatnia konwersja jest dobrze zdefiniowana. Komunikat o błędzie jest spowodowany tym, że mimo to przekazałeś flagi kompilatora -Werror,-Wconstant-conversion, prosząc o otrzymanie komunikatu o błędzie w tej sytuacji. Jeśli nie chcesz tego błędu, nie przekazuj tych flag.

---

Chociaż szczególności wykorzystanie został dobrze zdefiniowany, nie może być niezdefiniowana zachowanie niektórych wejść (czyli shift będących 16 lub większa, jeśli jesteś na 32-bitowym systemie int). Powinieneś więc naprawić funkcję.

Aby naprawić tę funkcję, musisz być ostrożniejszy w przypadku unsigned short ze względu na wyjątkowo irytującą regułę dotyczącą promocji całkowitej niepodpisanej krótkiej do podpisanej int.

Oto jedno rozwiązanie nieco różni się od innych ofert .. uniknąć problemu shift całkowicie działa dla każdej wielkości przesunięcia:

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

Z 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.

Wyrażenie

mask << shift; 

ocenia po integralną promocja jest stosowana do mask. W związku z tym ocenia się na 1048560, jeśli sizeof(unsigned short) wynosi 2, co wyjaśnia komunikat z klang.

Jednym ze sposobów uniknięcia problemu z przepełnieniem jest przesunięcie w prawo najpierw przed wykonaniem przesunięcia w lewo i przeniesienie go do własnej funkcji.

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

Nie wiem, czy to jest dokładnie to, co chcesz, ale kompiluje:

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.

Nie

Fi najpierw otrzymujesz right_zeros o wartości FFFF (od ~0). Zwykle ~0 jest FFFFFFFFFFFFFF..., ale ponieważ używasz u16, otrzymujesz FFFF.

Następnie przejście przez 4 produkuje FFFF0 [kalkulacja jest przedłużony do 32 bitów], ale gdy jest przechowywany z powrotem, tylko skrajnie prawe 16 bitów pozostają, więc wartość jest FFF0

Jest doskonale zachowanie prawny i zdefiniowane i "korzystając z obcięcia. Kompilator jest "nie oszukuje". W rzeczywistości działa dobrze z obcięciem lub bez niego.

Można zrobić right_zeros do u32 u64 lub jeśli chce, ale wtedy trzeba by dodać right_zeros &= 0xFFFF

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

Jest nie UB w oparciu o całość kodu, bez względu na kompilator mówi.

Właściwie Tavian to dostał. Użyj wyraźnej Obsada:

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

To mówi kompilatorowi, między innymi, że chcesz skrócenie do 16 bitów.

Jeśli był UB, kompilator nadal powinien narzekać.

Answer 4

Tak, jak podejrzewasz, nawet po wyłączeniu diagnostyki kompilatora, Twój kod jest ściśle mówiąc nie w pełni przenośny z powodu awansu z niepodpisanego krótkiego do podpisanego int, arytmetyczna liczba bitowa jest wykonywana w podpisanym int, a następnie podpisana int jest konwertowana powrót do niepodpisanego skrótu. Udało ci się uniknąć niezdefiniowanych zachowań (myślę, że po szybkim spojrzeniu), ale wynik nie jest gwarantowany, aby być tym, na co masz nadzieję. (type)~(type)0 nie musi odpowiadać "wszystkim bitom jeden" w typie type; już przed zmianą jest już niepewnie.

Aby uzyskać coś w pełni przenośnego, po prostu upewnij się, że wykonujesz wszystkie operacje arytmetyczne w co najmniej unsigned int (w razie potrzeby szersze typy, ale nigdy węższe). Wtedy nie będzie żadnych obaw o podpisane typy.

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