Перейти к содержимому


Фотография
- - - - -

Оригинальное задание


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 67

#1 -=Silent=-

-=Silent=-

    Продвинутый

  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 16 Май 2006 - 18:01

Уже надоели примитивные вопросыРешил уже от нечего делать задать вопрос, отвте на который сам давно уже знаю.Вопрос не привязан ни к какому языку и просто заставляет немного задуматься.Имеется массив размерности n (допустим , состоящий из переменный тип интежер - на самом деле это не столь важно).Необходимо осуществить сортировку массива без использования дополнительной памятиПримечание: под дополнительной памяться подразумеваеются:дополнительные переменные, стэк , куча и прочееВаши предложения :welcome:
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#2 hse.John

hse.John

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 1 тем
  • Регистрация:10 Мар 2006

Отправлено 16 Май 2006 - 18:08

а чем "пузырек" не подходит ?
  • 0

#3 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 16 Май 2006 - 18:14

Я думаю, что бы отсортировать массив надо обязательно обменивать значения переменных или хотя бы указателей на них. А обмен возможен только с использование доп. переменной. Так что одна доп. переменная, но понадобиться.Хотя возможно на ассемблере можно будет что нибудь придумать.
  • 0

#4 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 16 Май 2006 - 18:19

а чем "пузырек" не подходит ?

Думаю, что нет...Но ты хоть опиши, а то может я не так понимаю пузырьковый метод?

Я думаю, что бы отсортировать массив надо обязательно обменивать значения переменных или хотя бы указателей на них. А обмен возможен только с использование доп. переменной. Так что одна доп. переменная, но понадобиться.

Дану... :blush: Ты не прав.

Хотя возможно на ассемблере можно будет что нибудь придумать.

А чем потвоему ассемблер оличается, от С++ или ПаскаляНу даТам конечно можно произвести обмен через регистры, но это сравнимо с использование дополнительной переменной в языке высокого уровня
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#5 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 16 Май 2006 - 18:33

А обмен возможен только с использование доп. переменной.

int a, ba=5b=7a=a+bb=a-ba=a-b
  • 0
Старший Брат смотрит на тебя!

#6 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 16 Май 2006 - 18:37

int a, ba=5b=7a=a+bb=a-ba=a-b

угу :yes:
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#7 hse.John

hse.John

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 1 тем
  • Регистрация:10 Мар 2006

Отправлено 16 Май 2006 - 18:41

int a, ba=5b=7a=a+bb=a-ba=a-b

во-во
  • 0

#8 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 16 Май 2006 - 21:48

во-во

ага, а если это не простейший int, а что-нибудь типа string или какой-нибудь сложный объект?И еще у меня есть подозрение, что вычисленное значение a+b сохраняется прежде где-то в памяти, а уже потом присваивается.

Сообщение отредактировал anchar2k: 16 Май 2006 - 21:54

  • 0

#9 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 16 Май 2006 - 22:00

ага, а если это не простейший int, а что-нибудь типа string или какой-нибудь сложный объект?И еще у меня есть подозрение, что вычисленное значение a+b сохраняется прежде где-то в памяти, а уже потом присваивается.

Дело даже не в реализацииДело в логике.При тестировании на работу программиста, в нормальную программерскую контору дают именно такие задания, так как им чаще всего более важно не насколько человек много знает функций, а их больше интересует умение решать нестандартные заданичи

Сообщение отредактировал -=Silent=-: 16 Май 2006 - 22:01

  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#10 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 16 Май 2006 - 22:24

Честно, не понял про какие функции идет речь, я не упомянул ни одной. А обмен int сложением и вычитанием - может быть, только не пойму где это может пригодиться :confuse: , и стоит помнить что + и - процессор делает медленнее чем присваивание, а с плав. точкой ситуация еще хуже.
  • 0

#11 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 16 Май 2006 - 22:24

Блин, продублировал здесь свой предыдущий пост :)

Сообщение отредактировал anchar2k: 16 Май 2006 - 22:26

  • 0

#12 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 16 Май 2006 - 23:18

Честно, не понял про какие функции идет речь, я не упомянул ни одной. А обмен int сложением и вычитанием - может быть, только не пойму где это может пригодиться :confuse: , и стоит помнить что + и - процессор делает медленнее чем присваивание, а с плав. точкой ситуация еще хуже.

Да ты не понял меняЗдесь не важно, что быстрей , а что медленнее...Здесь важно бошкой пошевелитьПисать стандартые алгоритмы и решать тривиальные задачи может каждый более-менее нормальный программист, а вот бошкой пошевелить над нестандартной задачей - не все :(
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#13 FlashXL

FlashXL

    Продвинутый

  • Новичок
  • PipPipPip
  • 241 сообщений
  • 3 тем
  • Регистрация:28 Апр 2006
  • Город:Shit-city

Отправлено 17 Май 2006 - 11:08

ну вроде сортировка подсчетом может работать и без доп.переменных
  • 0

#14 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 17 Май 2006 - 12:15

Все равно на уровне asm результат a+b сохраняется где-то в дополнительной переменной (или в стеке, не знаю) , и то что ты на языке высокого уровня не создал доп переменную ничего не говорит. А она есть! Память под нее выделена!

Так что те же яйца, только сбоку.

FlashXL:

ну вроде сортировка подсчетом может работать и без доп.переменных

Если я правильно помню, то там нужен второй такой же массив размерности n

Сообщение отредактировал anchar2k: 17 Май 2006 - 12:19

  • 0

#15 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 17 Май 2006 - 12:39

Все равно на уровне asm результат a+b сохраняется где-то в дополнительной переменной (или в стеке, не знаю) , и то что ты на языке высокого уровня не создал доп переменную ничего не говорит. А она есть! Память под нее выделена!Так что те же яйца, только сбоку.

ровно там-же, где и буфер для перекидывания память-память. в (e)ax.
  • 0

#16 FlashXL

FlashXL

    Продвинутый

  • Новичок
  • PipPipPip
  • 241 сообщений
  • 3 тем
  • Регистрация:28 Апр 2006
  • Город:Shit-city

Отправлено 17 Май 2006 - 17:42

Все равно на уровне asm результат a+b сохраняется где-то в дополнительной переменной (или в стеке, не знаю) , и то что ты на языке высокого уровня не создал доп переменную ничего не говорит. А она есть! Память под нее выделена!

Так что те же яйца, только сбоку.

FlashXL:

Если я правильно помню, то там нужен второй такой же массив размерности n

можно обойтись без него

для a+b результат хранится в регистре - стыдно не знать)))
  • 0

#17 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 17 Май 2006 - 20:04

Все равно на уровне asm результат a+b сохраняется где-то в дополнительной переменной (или в стеке, не знаю) , и то что ты на языке высокого уровня не создал доп переменную ничего не говорит. А она есть! Память под нее выделена!

Так что те же яйца, только сбоку.

FlashXL:

Если я правильно помню, то там нужен второй такой же массив размерности n

Я еще раз повторяю.
Задача была на логику, а не на способность обмануть компилятор и заставить его неиспользовать дополнительной памяти. Поэтому и не было укрона на конкретный язык.

Понятное дело, что сложение двух чисел требует дополнительной памяти, а вернее использования регистров, что как не странно, тоже можно назвать памятью, хоть они и не входят ни в озу , ни в пзу,а в самом процессоре
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#18 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 17 Май 2006 - 21:30

Ладно я понял "задача была на логику", только не понял, где именно эту логику можно применить :) А насчет регистров:a=(b+a)*(c-d)+(e-f)/(g+h)... - никаких регистров не хватит

Сообщение отредактировал anchar2k: 17 Май 2006 - 21:31

  • 0

#19 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 18 Май 2006 - 09:35

int a, ba=5b=7a=a+bb=a-ba=a-b

Так тоже годитсяint a, ba=a^b;b=a^b;a=a^b;
  • 0
ЮРОДИВЫЙ

#20 -=Silent=-

-=Silent=-

    Продвинутый

    Топикстартер
  • Новичок
  • PipPipPip
  • 186 сообщений
  • 6 тем
  • Регистрация:16 Июл 2005

Отправлено 18 Май 2006 - 20:39

Так тоже годитсяint a, ba=a^b;b=a^b;a=a^b;

напомните мне что такое карата то паскаль забылся уже давнопомоему здесь ошибкаможно на числах примера если даже такое и работает, то это намного дольше чем сложение
  • 0
Между первой и второй промежуток 2Пn ...[COLOR=red]

#21 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 18 Май 2006 - 21:07

Возведение в степень вроде, и мне тоже кажется что здесь ошибка
  • 0

#22 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 18 Май 2006 - 23:26

А в С это по моему поразрядное логическое исключающее или. В ассемблере - операция XOR.
  • 0
ЮРОДИВЫЙ

#23 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 18 Май 2006 - 23:53

можно на числах примера если даже такое и работает, то это намного дольше чем сложение

a db 7b db 5... MOV AX, a ;в регистре АХ - а MOV BX, b ;в регистре BX - b XOR AX, BX ;в регистре АХ - 2 XOR BX, AX ;в регистре BX - 7 XOR AX, BX ;в регистре АХ - 5...логические операции говорят, выполняются быстрее арифметических
  • 0
ЮРОДИВЫЙ

#24 FlashXL

FlashXL

    Продвинутый

  • Новичок
  • PipPipPip
  • 241 сообщений
  • 3 тем
  • Регистрация:28 Апр 2006
  • Город:Shit-city

Отправлено 19 Май 2006 - 06:32

ребят, не об этом сейчас разговор)))
  • 0

#25 hse.John

hse.John

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 1 тем
  • Регистрация:10 Мар 2006

Отправлено 23 Май 2006 - 22:21

Продолжая тему:Даны 2 целых чила. Необходимо найти наименьшее из них без использования условных и циклических опрераторов.
  • 0

#26 zz7

zz7

    Двуликий Янус

  • Новичок
  • PipPipPipPipPipPip
  • 849 сообщений
  • 52 тем
  • Регистрация:14 Май 2004
  • Город:Колыбель космонавтики

Отправлено 23 Май 2006 - 23:57

min=(a+b-ABS( a-b ))/2

Сообщение отредактировал zz7: 23 Май 2006 - 23:57

  • 0
Старший Брат смотрит на тебя!

#27 hse.John

hse.John

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 1 тем
  • Регистрация:10 Мар 2006

Отправлено 24 Май 2006 - 00:08

min=(a+b-ABS( a-b ))/2

гут
  • 0

#28 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 24 Май 2006 - 02:32

Продолжая тему:Даны 2 целых чила. Необходимо найти наименьшее из них без использования условных и циклических опрераторов.

Кстати, а ?: считается условным оператором?a < b ? a:b
  • 0
Мир спасут красота и ковровые бомбардировки

#29 FlashXL

FlashXL

    Продвинутый

  • Новичок
  • PipPipPip
  • 241 сообщений
  • 3 тем
  • Регистрация:28 Апр 2006
  • Город:Shit-city

Отправлено 24 Май 2006 - 13:31

Кстати, а ?: считается условным оператором?a < b ? a:b

это есть краткая форма записи условного оператора)))
  • 0

#30 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 26 Май 2006 - 13:56

min=(a+b-ABS( a-b ))/2

Все вроде правильно, один только вопрос. Как работает функция нахождения модуля? (ABS)
  • 0
ЮРОДИВЫЙ

#31 anchar2k

anchar2k

    Продвинутый

  • Новичок
  • PipPipPip
  • 165 сообщений
  • 13 тем
  • Регистрация:01 Фев 2006

Отправлено 26 Май 2006 - 14:07

Все вроде правильно, один только вопрос. Как работает функция нахождения модуля? (ABS)

Мне кажется, что здесь больше обсуждают математику, чем программирование, поэтому как работает функция не важно.
  • 0

#32 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 26 Май 2006 - 20:44

Все вроде правильно, один только вопрос. Как работает функция нахождения модуля? (ABS)

int ABS(int a) {return a & MAX_INT;}
  • 0
Мир спасут красота и ковровые бомбардировки

#33 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 26 Май 2006 - 23:30

int ABS(int a) {return a & MAX_INT;}

:ugh: однако это будет работать для обратного кода, но не для дополнительного. Валенок уж должен знать..., наверное проверят на вшивость здешних обывателей :) а для дополнительного ... кхм... без ветвления тяжко...во, придумал! :consored: однако может продолжить интригу и дать возможность Ares'у самому придумать?по теме: если я правильно понял обсуждение, использование даже регистров попадает под запрет использования дополнительной памяти - то решение возможно только с помощью черной магии :lol:

Сообщение отредактировал mefody: 26 Май 2006 - 23:48

  • 0

#34 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 27 Май 2006 - 00:03

Мне кажется, что здесь больше обсуждают математику, чем программирование, поэтому как работает функция не важно.

Уважаемый, по условию задачи запрещается использовать операцию сравнения! Следуя Вашей логике, можно где то описать функцию и использовать ее? Тогда совсем просто получиться:int MoyFunc(int a, int b ){....}....min = MoyFunc(a, b );....

int ABS(int a) {return a & MAX_INT;}

Ваше решение не верно, т.к. (a & MAXINT) никоим образом не изменяет а! Допустим MAXINT равно 65535 в двоичной си – 1111 1111 1111 1111, а = -7(1111 1111 1111 1001). Смотрим:1111 1111 1111 1111&1111 1111 1111 1001__________________1111 1111 1111 1001Как видите ничего не изменилось! В общем вопрос свелся к определению знака числа, без использования сравнения.

:ugh: однако это будет работать для обратного кода, но не для дополнительного. Валенок уж должен знать..., наверное проверят на вшивость здешних обывателей :) а для дополнительного ... кхм... без ветвления тяжко...во, придумал! :consored: однако может продолжить интригу и дать возможность Ares'у самому придумать?по теме: если я правильно понял обсуждение, использование даже регистров попадает под запрет использования дополнительной памяти - то решение возможно только с помощью черной магии :lol:

Считаю, что решение без операции сравнения невозможно. Опять же чтоб переводить в доп код надо знать знак числа.

Сообщение отредактировал Ares: 26 Май 2006 - 23:58

  • 0
ЮРОДИВЫЙ

#35 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 00:26

Ваше решение не верно, т.к. (a & MAXINT) никоим образом не изменяет а! Допустим MAXINT равно 65535 в двоичной си – 1111 1111 1111 1111

...skiped...однако MAXINT - знаковый максимум, т.е. 32767 для вашего случая, и для обратного кода это бы работало...

Как видите ничего не изменилось! В общем вопрос свелся к определению знака числа, без использования сравнения.Считаю, что решение без операции сравнения невозможно. Опять же чтоб переводить в доп код надо знать знак числа.

вот решениеint ABS(int a) {return a ^ (a >> 31) - (a >> 31);}про 31 я думаю понятно, кол-во бит в int минус 1
  • 0

#36 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 27 Май 2006 - 01:12

...skiped...однако MAXINT - знаковый максимум, т.е. 32767 для вашего случая, и для обратного кода это бы работало...вот решениеint ABS(int a) {return a ^ (a >> 31) - (a >> 31);}про 31 я думаю понятно, кол-во бит в int минус 1

По умолчанию int – беззнаковое целое, т.е надо писать signed int. Далее a >> 31 – определили знаковый бит (пусть будет 1 => наше число отрицательное) и что получилось?1111 1111 1111 1001^0000 0000 0000 0001-------------------------1111 1111 1111 1000-0000 0000 0000 0001---------------------------1111 1111 1111 0111И Вы хотите сказать, что это правильное решение?
  • 0
ЮРОДИВЫЙ

#37 Bolan

Bolan

    шволочь

  • Жильцы
  • PipPipPipPipPipPipPipPip
  • 3 296 сообщений
  • 54 тем
  • Регистрация:23 Сен 2005
  • Пол:Мужчина

Отправлено 27 Май 2006 - 01:18

По умолчанию int – беззнаковое целое, т.е надо писать signed int. Далее a >> 31 – определили знаковый бит (пусть будет 1 => наше число отрицательное) и что получилось?1111 1111 1111 1001^0000 0000 0000 0001-------------------------1111 1111 1111 1000-0000 0000 0000 0001---------------------------1111 1111 1111 0111И Вы хотите сказать, что это правильное решение?

матчасть. учить. немедленно.для беззнаковых целых, котрые, кстати, ни разу не умолчательный тип - операция abs возвращает число. по определению.
  • 0

#38 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 27 Май 2006 - 01:36

матчасть. учить. немедленно.для беззнаковых целых, котрые, кстати, ни разу не умолчательный тип - операция abs возвращает число. по определению.

Ну и как работает операция abs, о великий ученый.
  • 0
ЮРОДИВЫЙ

#39 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 27 Май 2006 - 11:09

По умолчанию int – беззнаковое целое, т.е надо писать signed int.

В стандарте умолчание не прописано. Во всех виденных мной компиляторах, если не указан соответствующий ключ, int и char - signed.А решение действительно неправильное.Правильно будет так (в общем случае, независимо от типа представления числа):abs = a*(!sign(a))-a*sign(a);что для случая с int_32_t разворачиавется в abs = a*((a >> 31)^1 - (a>>31));т.е., если sign(a) = 1, получаем abs = -1*a, в противном случае получаем 1*a, ч.т.д.UPD: мда. называется, "прежде, чем упрощать выражения, нужно проснуться).

Сообщение отредактировал walenok: 27 Май 2006 - 12:51

  • 0
Мир спасут красота и ковровые бомбардировки

#40 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 12:18

По умолчанию int – беззнаковое целое, т.е надо писать signed int. Далее a >> 31 – определили знаковый бит (пусть будет 1 => наше число отрицательное) и что получилось?1111 1111 1111 1001^0000 0000 0000 0001-------------------------1111 1111 1111 1000-0000 0000 0000 0001---------------------------1111 1111 1111 0111И Вы хотите сказать, что это правильное решение?

Лол! для беззнакового инт функция взятия абсолютного значения выглядит такinline unsigned int ABS (unsigned int a) {return a;} :lol: далее: по умолчанию int и char - именно знаковые, попробуй поискать в инете исходники с ключевым словом signed и unsignedеще далее: смотри арифметический сдвиг вправопосле этого попробуй снова...

Сообщение отредактировал mefody: 27 Май 2006 - 12:19

  • 0

#41 Ares

Ares

    Продвинутый

  • Новичок
  • PipPipPip
  • 187 сообщений
  • 12 тем
  • Регистрация:20 Май 2005

Отправлено 27 Май 2006 - 12:32

Просто, чтоб докопаться до истины :pioneer: В принципе mefody видимо правильно понимает о чем я говорю. Насколько мне известно, есть 3 формата представления отрицательных чисел. Как они представлены – зависит от компилятора, но во всех старший бит = 0 соответствует плюсу, 1 минусу. Условимся о представлении без всяких там дополнений и углублений в значение MAXINT, а примерно так: 0000 … 0001 равно 1, 1000 … 0001 (-1). Для наглядности значения всех переменных приведены в двоичной си. Ну и вот так должна выглядеть функция ABS:int ABS(int a) {int mask = 1000 … 0000; //маска для установки знакового битаa = a | mask; //число а становится отрицательнымa = a ^ mask; //число а становится положительнымreturn a;}Особенно интересует мнение ветерана(чуть не написал инвалида) умственного труда г. Bolan. :clapping: Хотелось бы взглянуть на Ваше решение всезнающий.

Сообщение отредактировал Ares: 27 Май 2006 - 12:36

  • 0
ЮРОДИВЫЙ

#42 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 12:47

В стандарте умолчание не прописано. Во всех виденных мной компиляторах, если не указан соответствующий ключ, int и char - signed.А решение действительно неправильное.Правильно будет так (в общем случае, независимо от типа представления числа):abs = a*(!sign(a))-a*sign(a);что для случая с int_32_t разворачиавется в abs = a*((a >> 31)^1 - (a>>31)) = (-(a >> 31))*a;т.е., если sign(a) = 1, получаем abs = -1*a, в противном случае получаем -0*a, ч.т.д.

ч.т.д не получилось ибо -0*а = 0 а не |а|если с умножением то правильно такabs = ((a >> 31) | 1)*a;
  • 0

#43 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 27 Май 2006 - 12:58

int mask = 1000 … 0000; //маска для установки знакового битаa = a | mask; //число а становится отрицательнымa = a ^ mask; //число а становится положительным

Т.е., требуется обнулить старший бит? Так это и разворачивается в a &= mask-1;
  • 0
Мир спасут красота и ковровые бомбардировки

#44 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 13:00

Ares wrote' date='27 May 2006, 13:32>Насколько мне известно, есть 3 формата представления отрицательных чисел.правильно: прямой, обратный и дополнительный код (формат)> Как они представлены – зависит от компиляторанеправильно, от компилятора ничего не зависит, зависит от платформы - в x86 отрицательные целые представляются в дополнительном коде (да и я не представляю кто может использовать другие коды для отрицательных чисел)> но во всех старший бит = 0 соответствует плюсу, 1 минусу. это верно для всех форматов :D , остальное отличается>Условимся о представлении без всяких там дополнений и углублений в значение MAXINT, а примерно >так: 0000 … 0001 равно 1, 1000 … 0001 (-1). смотрим <limits.h>INT_MAX maximum value of type intINT_MIN minimum value of type intUINT_MAX maximum value of type unsigned intя думаю всем понятно что Валенок имел в виду INT_MAX == 0x7f..ff>>Для наглядности значения всех переменных приведены в двоичной си. Ну и вот так должна выглядеть функция ABS:int ABS(int a) {int mask = 1000 … 0000; //маска для установки знакового битаa = a | mask; //число а становится отрицательнымa = a ^ mask; //число а становится положительнымreturn a;}>>ну это верно для прямого кода, можно даже проще: a = a & (!mask) >Особенно интересует мнение ветерана(чуть не написал инвалида) умственного труда г. Bolan. :clapping: Хотелось бы взглянуть на Ваше решение всезнающий.чего тут решать, смотри мое решение... ну а по поводу сабжа, что нам скажет автор темы?
  • 0

#45 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 27 Май 2006 - 13:02

ч.т.д не получилось ибо -0*а = 0 а не |а|

Угу. Уже поправил.

если с умножением то правильно такabs = ((a >> 31) | 1)*a;

А в этом случае получится всегда a = 1*a, что неверно.Оно ((a >> 31)^1 - (a >> 31)) не упрощается.
  • 0
Мир спасут красота и ковровые бомбардировки

#46 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 13:23

А в этом случае получится всегда a = 1*a, что неверно.Оно ((a >> 31)^1 - (a >> 31)) не упрощается.

abs = ((a >> 31) | 1)*a;несогласен! Однако разберем по пунктам:арифметический сдвиг вправо копирует знаковый бит, т.е. если знаковый бит был = 1, то получится 0xFFFFFFFF что есть (-1)дк; если был 0, то получится 0x00, битовая "| 1" превратит это в 0x01 (и не повлияет на результат отрицательного случая)следовательно ((a >> 31) | 1) выдаст знак в формате (-1/+1) а не 0 для положительного и 1 для отрицательного.имхо оффтопик с abs'ом можно закрывать, и продолжить с сабжом...
  • 0

#47 walenok

walenok

    Продвинутый

  • Новичок
  • PipPipPip
  • 222 сообщений
  • 4 тем
  • Регистрация:15 Окт 2004
  • Город:Москва

Отправлено 27 Май 2006 - 13:48

abs = ((a >> 31) | 1)*a;несогласен! Однако разберем по пунктам:арифметический сдвиг вправо копирует знаковый бит, т.е. если знаковый бит был = 1, то получится 0xFFFFFFFF что есть (-1)дк; если был 0, то получится 0x00, битовая "| 1" превратит это в 0x01 (и не повлияет на результат отрицательного случая)следовательно ((a >> 31) | 1) выдаст знак в формате (-1/+1) а не 0 для положительного и 1 для отрицательного.имхо оффтопик с abs'ом можно закрывать, и продолжить с сабжом...

Мда. Действительно. Отвык я от чисел со знаком...
  • 0
Мир спасут красота и ковровые бомбардировки

#48 RItt

RItt

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 0 тем
  • Регистрация:14 Окт 2004

Отправлено 27 Май 2006 - 14:35

abs = ((a >> 31) | 1)*a;

несогласен! Однако разберем по пунктам:
арифметический сдвиг вправо копирует знаковый бит, т.е. если знаковый бит был = 1, то получится 0xFFFFFFFF что есть (-1)дк; если был 0, то получится 0x00, битовая "| 1" превратит это в 0x01 (и не повлияет на результат отрицательного случая)
следовательно ((a >> 31) | 1) выдаст знак в формате (-1/+1) а не 0 для положительного и 1 для отрицательного.
имхо оффтопик с abs'ом можно закрывать, и продолжить с сабжом...

это не так для С++

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 nonnegative value, the value of the result is the integral part of the quotient of E1 divided byt the quantity 2 raised to the power E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

и не так для С (С99)

6.5.7/5


Сообщение отредактировал RItt: 27 Май 2006 - 18:36

  • 0

#49 mefody

mefody

    Новичок

  • Новичок
  • Pip
  • 14 сообщений
  • 0 тем
  • Регистрация:26 Май 2006

Отправлено 27 Май 2006 - 18:44

это не так для С++

5.8/3The 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 nonnegative value, the value of the result is the integral part of the quotient of E1 divided byt the quantity 2 raised to the power E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

тут наверное реч об имплементации под разные платформы... для x86 я думаю используется Shift Arithmetic Rightи где вы эти стандарты берете только.... :lol:
  • 0

#50 RItt

RItt

    Новичок

  • Новичок
  • Pip
  • 9 сообщений
  • 0 тем
  • Регистрация:14 Окт 2004

Отправлено 27 Май 2006 - 19:04

тут наверное реч об имплементации под разные платформы... для x86 я думаю используется Shift Arithmetic Right

Ваш код не соответствует стандарту С и С++. Под зависимость от реализации понимают зависимость от компилятора и его право определить гарантию использования, например, для платформы x86 арифметического сдвига для знаковых.
  • 0




Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных