Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Маленькая задачка

Автор: nickless 22.1.2009, 00:31

Недавно наткнулся на такую задачку, возможно кому-нибудь тоже будет интересно.

Имеется C/C++ код:

Код


int foo(int x)
{
    return x != 0 && x == -x;
}

Вопрос: Может ли функция foo вернуть не 0, почему и от чего это зависит.

Если кто знает, не пишите сразу решение, пусть другие немного подумают smile

Автор: REZiaMIX 22.1.2009, 00:59

Придумал почему может , но это не то , что тут задумано))))

Автор: ISergeyN 22.1.2009, 03:05

здесь что-то с нулём связано так как

Код


int x = 0;
if( x == -x )
    cout<<"ok"<<endl;

Автор: Kallikanzarid 22.1.2009, 03:57

Это задача математическая (3й класс), а не на С++ smile

x = -x => 2x = 0 => x = 0
Эрго, foo всегда будет возвращать 0, если только программа не выполняется на машине, где 0 - булева истина smile

Автор: nickless 22.1.2009, 04:43

Люди, ну там же специально проверка стоит x != 0 smile

Автор: MastEdm 22.1.2009, 11:41

Может, если

Код


x = INT_MIN

потому что INT_MIN = –2,147,483,648, а INT_MAX = +2,147,483,647. Хотя зависит, наверное, от компилятора smile

Автор: Alek86 22.1.2009, 11:56

все банально
если x - расшарена между 2мя потоками на запись, то ф-я может вернуть и 1 smile

ЗЫ. все ж таки мы программисты, а не математики...

Добавлено через 9 минут и 19 секунд
хотя, если без приколов, то в стандарте вроде как не сказано, что INT_MIN не должен равняться INT_MAX...

Автор: vinter 22.1.2009, 12:25

Цитата(Alek86 @ 22.1.2009, 12:56

)

если x - расшарена между 2мя потоками на запись, то ф-я может вернуть и 1

каким образом? хочешь сказать поток может прервать выполнение другого потока во время проверки?

Автор: MAKCim 22.1.2009, 12:29

Цитата(Alek86 @ 22.1.2009, 11:56

)

если x - расшарена между 2мя потоками на запись

x передается через регистр или стек потока
race'а нет

Цитата(Alek86 @ 22.1.2009, 11:56

)

хотя, если без приколов, то в стандарте вроде как не сказано, что INT_MIN не должен равняться INT_MAX...

а где он равняется? smile

Автор: vinter 22.1.2009, 12:36

че то я не понял, почему INT_MIN == -INT_MIN?

Автор: Alek86 22.1.2009, 12:45

MAKCim, про гонки точно, протупил
вопрос не в том, где такое выполняется, а в том, запрещено ли это стандартом

а вообще лично у меня все "нормальные" аргументы в пользу положительного ответа закончились.
если INT_MIN == INT_MAX - неверно, то я выбираю ответ "нет, по стандарту C++ функция не может вернуть не 0" smile

Добавлено через 2 минуты и 21 секунду

Цитата(vinter @ 22.1.2009, 12:25

)

хочешь сказать поток может прервать выполнение другого потока во время проверки?

да, может, причем это не стандартизировано, то есть когда ОС захочет, тогда и прервет
но тут оно не прокатит :(

Автор: vinter 22.1.2009, 12:49

Alek86,

Цитата(Alek86 @ 22.1.2009, 13:45

)

если INT_MIN == INT_MAX - неверно, то я выбираю ответ "нет, по стандарту C++ функция не может вернуть не 0"

дело не в этом INT_MIN игнорит минус, оставаясь также в значении INT_MIN

Автор: GoldFinch 22.1.2009, 13:27

задачка про баги С++ %)

Автор: xvr 22.1.2009, 13:31

Цитата(GoldFinch @ 22.1.2009, 13:27)

задачка про баги С++ %)

Это не баги а фичи, и не С++ а представления чисел в двоичном дополнительном коде smile

Автор: vinter 22.1.2009, 13:54

xvr, а в чем прикол? знак же дожен изменится, - должен сбросить старший разряд

Автор: GoldFinch 22.1.2009, 14:00

а ведь действительно,
mov eax,0x80000000 / neg eax
возвращает 0x80000000

Автор: Fazil6 22.1.2009, 14:22

так а чего вы хотели?
-21474836478(это 0x8000) умножить на -1 получаем 21474836478 , а это опять же 0x8000, прочитываем правильно и получаем опять -21474836478

Автор: vinter 22.1.2009, 14:24

блин, точно. Прикольно smile

Автор: xvr 22.1.2009, 14:27

Цитата(vinter @ 22.1.2009, 13:54)

xvr, а в чем прикол? знак же дожен изменится, - должен сбросить старший разряд

Изменение знака - это не только изменение старшего разряда. В двоично дополнительном коде изменение знака производится так: (~x)+1, т.е.

Код


0x8000 -(инверсия)-> 0x7FFF -(+1)-> 0x8000

Автор: GSasha 22.1.2009, 16:32

Интересно...

Автор: GSasha 22.1.2009, 17:17

Для избежания граблей, так будет правильнее

Код


int foo(int x)
{
    __int64 _x = x;
    return ( _x != 0 ) && ( _x == -_x );
}

Автор: vinter 22.1.2009, 18:11

Цитата(GSasha @ 22.1.2009, 18:17

)

Для избежания граблей, так будет правильнее

с чего бы это?

Автор: GSasha 22.1.2009, 19:21

Цитата(vinter @ 22.1.2009, 18:11

)

с чего бы это?

Функция не возвратит 1 в случае передачи INT_MIN smile

Автор: vinter 22.1.2009, 19:42

GSasha, такое условие не может быть нигде применено, так что исправлять его не надо smile

Автор: baldina 22.1.2009, 19:49

GSasha, а если sizeof (int) == sizeof (__int64) smile

Автор: GSasha 22.1.2009, 19:50

vinter, 100% чего то увлекся увлекательной задачкой, что отошел от реальности smile

Автор: baldina 22.1.2009, 19:51

Цитата(vinter @ 22.1.2009, 19:42)

GSasha, такое условие не может быть нигде применено, так что исправлять его не надо smile

Автор: nickless 22.1.2009, 19:54

Цитата(xvr @ 22.1.2009, 13:27

)

В двоично дополнительном коде изменение знака производится так: (~x)+1

Вот оно

При передаче INT_MIN происходит знаковый overflow, т.к. (32bit)

Код


-INT_MIN == ~0x80000000 + 1 == 0x7fffffff + 1 == INT_MAX + 1 == 0x80000000 == INT_MIN

А вот тут начинаются подвохи smile

Во-первых, если при компиляции включить проверку на overflow, этот код может вызвать ошибку исполнения.
В gcc:

Код


       -ftrapv
           This option generates traps for signed overflow on addition, subtraction, multiplication operations.

Код


% gcc foo.c -o foo -ftrapv
% ./foo
zsh: abort      ./foo

Потом вот что пишет стандарт на счет overflow (C++, C лень искать было):

Код


3.9.1 Fundamental types
4 Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2 n where n is the number of bits in the value representation of that particular size of integer. 41)

footnote 41)
This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.

5 Expressions
5 If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined, unless such an expression is a constant expression (5.19), in which case the program is ill-formed.
[Note: most existing implementations of C++ ignore integer overflows. Treatment of division by zero, forming a remainder using a zero divisor, and all floating point exceptions vary among machines, and is usually adjustable by a library function. ]

Т.е. если бы это был unsigned integer, то overflow должен работать как положено, а с signed integer - это UB, архитектурно- и компиляторозависимо.
Насколько я знаю, на маках с powerpc процессором, эта функция всегда возвращает 0 (если у кого есть, попробуйте плиз).

Автор: GSasha 22.1.2009, 19:55

и еще разок smile

Автор: nickless 22.1.2009, 20:00

Цитата(vinter @ 22.1.2009, 18:42

)

такое условие не может быть нигде применено, так что исправлять его не надо

Видел что это было использовано для проверки на overflow в сорцах питона (видел в багтрекере gcc баг по этому поводу, были проблемы как раз с powerpc, в итоге пофиксили питон).

Добавлено через 4 минуты и 20 секунд
http://mail.python.org/pipermail/python-bugs-list/2006-August/034982.html

Автор: baldina 22.1.2009, 22:23

Цитата

в сорцах питона

Цитата

This conflicts with x<0, which means that the compiler may assume
that
x<0 && x==-x
always yields false

там исходник на С. в С++ вероятно проще, быстрей и понятней проверить так:

Код


#include <limits>

template <typename T>
bool is_smallest (T x)
{
   return numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min();
}