убийственная задачка на integer arithmetic

[wizzard]

Long story short: написать функцию целочисленного деления, с округлением “вверх” (к ближайшему целому, которое больше или равно результату, полученному в результате деления вещественных (float) чисел). Без использования floating-point arithmetic и 64bit arithmetic. Для signed int32.

Если честно – я подумал и решил забить. Кому надо реализовать корректно – интернет знает решение. А кому хочется поломать мозги – милости просим в комменты :)

UPD: хехе, now i have a solution. но подсмотренный вариант Майка Абраша все равно лучше – он гораздо читабельнее.

Comments

"Убийственная" задачка по целочисленной арифметике.

[(Anonymous)]

Вариант С'89:

signed int div_up(signed int lhs, signed int rhs)
{
signed int mod
, flag
, sign
, div_low;

div_low = lhs / rhs;
sign = div_low / -div_low;
mod = lhs % rhs;
flag = abs(rhs / mod);

return ( flag < 2 || flag == 2 && (rhs % mod) == 0 ) ? div_low + (1 * sign)
: div_low;
}


Вариант С++'03 для любого типа, отвечающего концепту целого числа:

template
<
typename IntType
>
IntType div_up(const IntType lhs, const IntType rhs)
{
BOOST_CONCEPT_ASSERT((Integer));

IntType div_low = lhs / rhs
, sign = div_low / -div_low
, mod = lhs % rhs
, flag = std::abs(rhs / mod);

return ( flag < 2 || flag == 2 && (rhs % mod) == 0 ) ? div_low + (1 * sign)
: div_low;
}

Я, как в том анегдоте, **ал и плакал. Мельчает народ наш, если уж такие задачки называют "убийственными".

Re: "Убийственная" задачка по целочисленной арифметике.

[(Anonymous)]

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

Re: "Убийственная" задачка по целочисленной арифметике.

[wizzard]

Вы код свой хоть запускали-то? :D

Fail: -3/-3=Division by zero, expected 1, FP result:1
Fail: -3/-2=0, expected 2, FP result:1,5
Fail: -3/-1=Division by zero, expected 3, FP result:3
Fail: -3/1=Division by zero, expected -3, FP result:-3
Fail: -3/2=-2, expected -1, FP result:-1,5
Fail: -3/-2147483648=Division by zero, expected 1, FP result:1,39698386192322E-09
Fail: -3/-2147483647=Division by zero, expected 1, FP result:1,39698386257374E-09
Fail: -3/-2147483646=Division by zero, expected 1, FP result:1,39698386322426E-09
Fail: -3/2147483645=Division by zero, expected 0, FP result:-1,39698386387478E-09
Fail: -3/2147483646=Division by zero, expected 0, FP result:-1,39698386322426E-09

Too many errors, further test output suppressed.
total tests: 132, trivial: 13, passed: 9, failed: 123

Исправляйте, мне интересно :)

Re: "Убийственная" задачка по целочисленной арифметике.

[wizzard]

Округлять всегда. Напишите в одну строку, посмотрим :)