Целочисленная арифметика: добавьте 1 к UINT_MAX и разделите на n без переполнения
Есть ли способ вычислить результат ((UINT_MAX+1)/x)*x-1
в С не прибегая к unsigned long
(где x
является unsigned int
)?
(соответственно "не прибегая к unsigned long long
"в зависимости от архитектуры.)
3 ответа
Решение
Это довольно простая арифметика:
((UINT_MAX + 1) / x) * x - 1 =
((UINT_MAX - x + x + 1) / x) * x - 1 =
((UINT_MAX - x + 1) / x + 1) * x - 1 =
(UINT_MAX - x + 1) / x) * x + (x - 1)
С целочисленными делениями мы имеем следующую эквивалентность
(y/x)*x == y - y%x
Итак, мы имеем
((UINT_MAX+1)/x)*x-1 == UINT_MAX - (UINT_MAX+1)%x
объединяя этот результат со следующей эквивалентностью
(UINT_MAX+1)%x == ((UINT_MAX % x) +1)%x
мы получаем
((UINT_MAX+1)/x)*x-1 == UINT_MAX - ((UINT_MAX % x) +1)%x
который вычисляется с unsigned int
,
sizeof(unsigned long) == sizeof(unsigned int) == 4 на большинстве современных компиляторов. Вы можете использовать использовать unsigned long long.