Автор Тема: [Задачка-закачка] abs() - намиране на алтернатива  (Прочетена 4867 пъти)

LinuxFanUNIX

  • Напреднали
  • *****
  • Публикации: 408
  • Distribution: Slackware 12.2
  • Window Manager: KDE 3.5.10
    • Профил
Здравейте. Тъй като нямам права за писане в раздела със задачките, моля правоимащите да преместят тази тема там, а този ред - да бъде изтрит.

Всички знаем за функцията abs(int x) която е математическото представяне на абсолютната стойност на дадена променлива (от целочислен тип), която присъства в (да не кажа всеки) почти всеки език.

Задачката е следната:

"Да се напише на любим за Вас език функция abs(), към която може да се добавя един аргумент (целочислена стойност), връщаща (отново) целочислена стойност.

Каква е уловката?

- Да не се използва if (така че случая с if (a < 0) return a*-1 - отпада), switch и всякакви вариации на : ? (в PHP) && || и т.н.
- Да не се създават никакви променливи във функцията abs()

Решението на "гатанката" ще бъде публикувано след 7 дни, считано от датата и часа на пускане на темата (освен ако някой не се е добрал до него първи, при което темата ще бъде заключена с флаг "Solved").

Дерзайте!  ;D
« Последна редакция: Jul 17, 2011, 00:56 от LinuxFanUNIX »
Активен

h_paskalev

  • Гост
sqrt(a^2) !?
Активен

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Просто:

Код
GeSHi (C):
  1. unsigned int abs(int x)
  2. {
  3.   return (x + (x >> 31)) ^ (x >> 31);
  4. }
  5.  

http://en.wikipedia.org/wiki/Two%27s_complement
« Последна редакция: Jul 18, 2011, 11:39 от VladSun »
Активен

"Knowledge is power" - France is Bacon

LinuxFanUNIX

  • Напреднали
  • *****
  • Публикации: 408
  • Distribution: Slackware 12.2
  • Window Manager: KDE 3.5.10
    • Профил
sqrt(a^2) !?
Компилирано под C++, при a=3, извежда 1... (моля вписвайте пълните решения + езика на който е написана)

Просто:

Цитат
unsigned int abs(int x)
{
   return (x + (x >> 31)) ^ (x >> 31);
}

http://en.wikipedia.org/wiki/Two%27s_complement
Извежда правилно решение което означава че имаме вече един отговор.

Продължавайте... Други идеи?
Активен

bot

  • Гост
 асемблер за Microchip контролер

       cblock 0x20
       integ
       integ_abs
       endc

 MainLoop:
       ...
       movf integ,w        ; записва стойността на променливата integ в w регистъра
       call   abs              ; извиква подпрограма за изчисляване на абсолютната стойност на integ
       movwf integ         ; записва върната абсолютна стойност обратно в integ променливата
       ...

 abs:
       movwf  integ_abs  ; прехвърля съдържанието на w регистъра в променливата integ_abs
       btfsz     status,z    ; проверява за 0, ако съдържанието на w е нула, то и абсолютната стойност е 0, ако да - излизане от
                                  ; подпограмата, ако не е нула - следващия оператор се прескача
       return
       btfss     integ_abs,7 ; проверява най-старшия бит, ако е 0 то числото е положително, следователно и абсолютната му стойност е същата
                                    ; ако е отрицателно - следващия оператор се прескача, ако е положително - изход от подпрограмата
       return
       xorlw    0xff          ; изключващо "или" на съдържанието на w регистъра с 0xff, резултатът се записва обратно в w регистъра
       addlw    0x01        ; съдържанието на w се събира с 1 , т.е. увеличава се с 1, резултатът се записва в w регистъра
       return                  ; изход от подпрограмата. Резултатът се съдържа в w регистъра и се извлича от там


       пример
       
       integ = -127 (10000001)
       10000001 xor 11111111 = 01111110 (126)
       увеличено с 1 = 127

       пример 2

       integ = -2 (11111110)
       11111110 xor 11111111 = 00000001 (1)
       увеличено с 1 = 2
« Последна редакция: Jul 17, 2011, 03:24 от bot »
Активен

bot

  • Гост
 това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.
Активен

c111100101

  • Гост
това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.
Или го пусна да се изфукаш, че можеш да пишеш на асемблер!
Активен

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Активен

0x2B|~0x2B

kierenski

  • Напреднали
  • *****
  • Публикации: 92
    • Профил
Колеги кой ви е бил по главата да използвате такива сложни функции като корен квадратен, а не
използвате само булева функция AND с константа  :)

Код
GeSHi (C):
  1. unsigned int abs (unsigned int x)
  2. {
  3. return (x&konstanta);
  4. }
« Последна редакция: Jul 18, 2011, 11:39 от VladSun »
Активен

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Не мисля че е възможно, поне по начина по който се представят signed integer-ите в "модерните" архитектури. Би могло ако се представяха по следният начин:

[sign bit][stoinost]

и примерно 000000001 e 1, а 10000001 e -1. Това изглежда безкрайно логично и просто, но не се ползва. Ако все пак се ползваше, тогава абсолютната стойност се смята лестно, примерно с AND:

Цитат
return (x&0x7FFFFFFF);

Или с две побитови отмествания:

Цитат
return ((x>>1)<<1);

Активен

"Knowledge is power" - France is Bacon

teleport

  • Напреднали
  • *****
  • Публикации: 134
    • Профил
На php:

Код
GeSHi (PHP):
  1. function xabs($x){
  2. return (int) sqrt(pow($x,2));
  3. }

Код
GeSHi (PHP):
  1. function xabs($x){
  2. return (int) substr(sprintf("%+d",$x),1);
  3. }

Само че не става ясно някакъв хитър математически начин ли се търси, нещо по-бързо от стандартната abs() (за конкретен език) или да се ползва страничен ефект от записването на променливите (пак в конкретен език)?
« Последна редакция: Jul 18, 2011, 11:38 от VladSun »
Активен

h_paskalev

  • Гост
sqrt(a^2) !?
sqrt(a**2)
Не съм имал предвид синтаксис на конкретен език... Предложих решение с израз - корен от квадрат на x.
Но определено решението с побитови операции е по-елегантно, макар и относително. :)

П.П. А сега се досетих, че може би просто предлагаш решение в Perl или друг език. :D
« Последна редакция: Jul 18, 2011, 00:04 от H. Paskalev »
Активен

bot

  • Гост
това последното го пуснах на майтап като отговор на условието "да се напише на любим програмен език". Програмата би трябвало да работи, но не е спазено едно от условията - да не се използва if - проверката на битовете в специалните регистри си е един вид if при езиците от по-високо ниво.
Или го пусна да се изфукаш, че можеш да пишеш на асемблер!

 Така е! Ако искаш мога да ти напиша горния фрагмент на асемблер за Атмел, Silicon Labs процесори или 8051 базирани. Ей сега вече ще мога да спя по-спокойно.
 
 пп споменах ли #C
« Последна редакция: Jul 17, 2011, 12:41 от bot »
Активен

Acho

  • Напреднали
  • *****
  • Публикации: 5275
  • Distribution: Slackware, MikroTik - сървърно
  • Window Manager: console only
    • Профил
    • WWW
Спомена.
Активен

CPU - Intel Quad-Core Q8400, 2.66 GHz; Fan - Intel Box; MB - Intel G41M-T2; RAM - DDR2-800, Kingston HyperX, 2X2048 MB; VC - onboard, Intel G41 Express Chipset; HDD - Toshiba, 500 GB, SATAII; SB - Realtek HD Audio; DVD-RW - TSSTcorp DVD-RW; LAN - Realtek PCI-E GBE Controller; PSU - Fortron 350 Watt.

kierenski

  • Напреднали
  • *****
  • Публикации: 92
    • Профил
Всичко си зависи от архитектурата и всичко може да се разбие винаги на по-малък код, но на ниско ниво (асемблер например) не е възможно да не се използват регистри (променливи), а и в условието не е споменато какъв е типът на думата и архитектурата така че за мен *2.

отговорът за допълнителен код при интел архитектура е:

Код
GeSHi (C):
  1. unsigned int abs(int x)
  2. {
  3. return (x^(x>>31))+(((x>>31)+2)&0x1);
  4. }
  5.  
при този код:
Код
GeSHi (C):
  1. unsigned int abs(int x)
  2. {
  3.   return (x + (x >> 31)) ^ (x >> 31);
  4. }
  5.  
има грешка от препълване при което някои числа ще правят проблеми
« Последна редакция: Jul 18, 2011, 11:38 от VladSun »
Активен