?

Log in

No account? Create an account

Программистское - Ваши рубидии уже у кобальта во ртути

Jan. 12th, 2011

04:01 pm - Программистское

Previous Entry Share Next Entry

Забавная задачка: напишите как можно более эффективно
unsigned long long mean(unsigned long long a, unsigned long long b)
возвращающую округленное вниз среднее арифметическое чисел a и b.

Upd:
Очевидное решение: a < b ? a + (b-a)/2 : b + (a-b)/2
Логичное решение: a/2 + b/2 + (a & b & 1) (для пуристов - a/2 + b/2 + (a%2)*(b%2))
Подход к оптимальному решению первым описал kdv2005.
Собственно решение дал raindog_2.
Комментарии больше не скринятся.

Comments:

[User Picture]
From:lev
Date:January 13th, 2011 12:02 am (UTC)
(Link)
типа а/2 + b/2?
или а>>1 + b>>1
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:08 am (UTC)
(Link)
И что будет при a = 1, b = 1?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:maksa
Date:January 13th, 2011 12:08 am (UTC)
(Link)
Побитово сложить, а потом сдвинуть на бит?
Я ни разу не программист, и наверное, не понимаю, в чём сложность задачи.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:12 am (UTC)
(Link)
Не столько сложность, сколько некоторая неочевидность и вариативность ответа - ради чего вопрос и задается. Команда арифметического сложения в компьютерах - в сущности, сложение по модулю 2разрядность процессора.
(Reply) (Parent) (Thread)
[User Picture]
From:avva
Date:January 13th, 2011 12:08 am (UTC)
(Link)
return a < b ? a+(b-a)/2 : b+(a-b)/2;
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:14 am (UTC)
(Link)
Не самый простой способ.
(Reply) (Parent) (Thread) (Expand)
From:ex_juan_gan
Date:January 13th, 2011 12:10 am (UTC)
(Link)
Cases are: either their difference is bigger than the ulonglong range (then add them and divide), or it is less, then divide the difference and add to whatever.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:24 am (UTC)
(Link)
How about avoiding conditionals?
(Reply) (Parent) (Thread)
From:rezkiy
Date:January 13th, 2011 12:12 am (UTC)
(Link)
((a >> 1) + (b >> 1) + (a & b & 0x1))
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:15 am (UTC)
(Link)
Тепло, но можно проще.
(Reply) (Parent) (Thread)
[User Picture]
From:kdv2005
Date:January 13th, 2011 12:14 am (UTC)
(Link)
А так?

a<b? a + (b-a)/2 : b + (a-b)/2;
(Reply) (Thread)
From:zhengxi
Date:January 13th, 2011 12:25 am (UTC)
(Link)
(a>>1) + (b>>1) + (a&b&1)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:27 am (UTC)
(Link)
Тепло, но можно проще.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:cema
Date:January 13th, 2011 12:39 am (UTC)
(Link)
Let c = b-a (no overflow here). Then b = a+c and mathematically (ignoring the rounding) (a+b)/2 = (a+ (a+c))/2 = (2a+c)/2 = a + c/2 (which is obvious anyway). To round it down we can round c/2 up. So: calculate c, c/2, round it up, subtract from a.

Must be an easier way, I am rusty with bits. Perhaps this: calculate d = a+b (with possible overflow). Without overflow, right shift d, obviously. In case of overflow, the actual sum is d+2k, where k is the number of bits in an unsigned long long. The result would then be d/2+2k-1, where the first element (d/2) is again the right shift, and the second element is one bit set at position k, other bits zeros. I guess this way should be more efficient: we calculate d, then shift it right, and if there was an overflow set that bit.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:43 am (UTC)
(Link)
See update.
(Reply) (Parent) (Thread)
(Deleted comment)
(Deleted comment)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 13th, 2011 12:56 am (UTC)
(Link)
Минимальное число операторов. Этим же достигнется и минимальное число циклов.
(Reply) (Parent) (Thread) (Expand)
(Deleted comment)
(Deleted comment)
[User Picture]
From:raindog_2
Date:January 13th, 2011 01:34 am (UTC)
(Link)
Если не ошибаюсь, можно еще вот так:

(a^b)/2 + (a&b)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 13th, 2011 01:40 am (UTC)
(Link)
Это оно.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:January 13th, 2011 09:20 am (UTC)
(Link)
Век живи, век учись.
(Reply) (Thread)