Доброе утро/день/вечер, Codeforces.
*Предыдущий пост: http://codeforces.me/blog/entry/3853 *
Следуя совету al13n (http://codeforces.me/blog/entry/3853#comment-79329 ), для новой тонкости я создал новый пост, чтобы не возникало путаницы с комментариями.
20.02.12 Источник: от кого-то когда-то слышал, сейчас проверил, оказалось интересно
Оператор >> для знаковых типов сохраняет знак. То есть если вы сдвинете вправо отрицательное число, то слева будут дописаны 1, а если положительное — то 0. При сдвиге влево всегда дописывается 0. Меня это как-то не коснулось, потому что в задачах с битовыми масками размера больше 30 я всегда использовал unsigned long long.
Вот код, которым я это проверял:
#include <cstdio>
using namespace std;
inline void printBits(unsigned a){
for(int i = 31; i >= 0; --i)
printf(((a >> i) & 1) ? "1" : "0");
puts("");
}
template<class X> void testShift(X a){
printf("Before:\n");
printBits(a);
a = (a << 1);
printf("After:\n");
printBits(a);
puts("");
}
int main(){
printf("Signed 15\n");
testShift(15);
printf("Signed -15\n");
testShift(-15);
printf("Unsigned 15\n");
testShift(unsigned(15));
printf("Unsigned -15\n");
testShift(unsigned(-15));
return 0;
}
Продолжение следует...
Возможно, этим постом Вы уберегли не одну пару ног программистов на C++ от огнестрельного ранения. А вообще получается, что для отрицательных чисел деление на 2 через сдвиг тоже работает.
UPD: похоже, в случае с оператором<<знак также сохраняется.Вроде не сохраняется: http://ideone.com/99557
хм... я проверял так:
вывод:
Ну -100500 в битовом представлении 11111111111111100111011101101100. При сдвиге на 1 получаем 11111111111111001110111011011000 < 0. Но если ты сдвинешь на 15, то получишь 00111011101101100000000000000000 > 0.
А в Java есть оператор
>>, который сохраняет знак, и оператор>>>, который ставит слева 0.Это потому что у них нет беззнаковых типов, а битовые маски использовать хочется.
Теперь посмотрим, что написано в стандарте
5.8/2 The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5.8/3 The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined
Думаю, выводы сделаете сами.
С оператором >> ещё связана тонкость, что не стоит сдвигать больше, чем на разрядность типа. Помнится, на каком-то из opencup'ов из-за этого получали не ОК.
если не ошибаюсь, то правое число берётся по модулю 32 (даже если отрицательное), а потом сдвигается на него. поэтому, например, ошибочно считать 63>>100 нулём. p.s. этот пример запускать без -O2.
5.8/1 ...The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.
В Java кажется это прописано, а вот в сях undefined behavior.
и в Java, и в Delphi и по крайней мере в g++ я это наблюдал...
undefined означает что оно то есть то нет :)
На самом деле это может даже всегда быть так, но значить, что если кому-то это захочется исправить это исправят)
Дело тут не столько в C++, сколько в том, что в процессорах Intel давным-давно было принято такое решение: SHL на >31 работает неожиданно — берёт аргумент по модулю 32. Мотивы этого мне неизвестны — может быть, это бывает полезно при оптимизации.