Целочисленная арифметика: добавьте 1 к UINT_MAX и разделите на n без переполнения

Question

Есть ли способ вычислить результат ((UINT_MAX+1)/x)*x-1 в С не прибегая к unsigned long (где x является unsigned int)? (соответственно "не прибегая к unsigned long long"в зависимости от архитектуры.)

Answer 1

Это довольно простая арифметика:

((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)

Answer 2

С целочисленными делениями мы имеем следующую эквивалентность

(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,

Answer 3

sizeof(unsigned long) == sizeof(unsigned int) == 4 на большинстве современных компиляторов. Вы можете использовать использовать unsigned long long.