Гарантируем достаточно места для хранения 4 * ceil (n / 3), где n - это int

Question

Допустим, n - это целое число (переменная int в C). Мне нужно достаточно места для «4-кратного потолка n, разделенного на 3» байта. Как я могу гарантировать достаточно места для этого?

Как вы думаете, malloc(4*(int)ceil(n/3.0)) подойдет, или мне нужно добавить, скажем, 1, чтобы быть абсолютно безопасным (из-за возможных ошибок округления)?

Answer 1

вы можете достичь того же самого с помощью целочисленной арифметики, которая гарантирует, что вы выделите правильный объем памяти: edit фиксированные скобки

malloc(4*((n+2)/3))

Answer 2

Альтернативой общей формуле KerrekSB, которая гарантирует использование только одного деления, является вычисление

(n + m-1) / m

Чтобы увидеть, что оно производит то же самое,написать n = k*m + r с 0 <= r < m.Тогда n%m == r, а если r == 0, у нас есть n+m-1 = k*m + (m-1) и (n+m-1)/m == k, в противном случае n+m-1 = (k+1)*m + (r-1) и (n+m-1)/m == k+1.

Большинство современных аппаратных средств дает вам коэффициент (n/m) в одномзарегистрируйте и остаток (n%m) в другом, когда вы выполните целочисленное деление, так что вы можете получить обе части формулы Керрека в одном делении, и большинство компиляторов сделают это.Если компилятор не использует, но использует два деления, вычисления будут значительно медленнее, поэтому, если вычисления выполняются часто, а производительность является проблемой, вы можете обойти слабость компилятора с несколько менее очевидным кодом.

В данном случае malloc будет

malloc(4*((n+2)/3));

Но поскольку не всем очевидно, что делает эта формула, если вы ее используете, объясните ее в комментарии, а если нетнужно использовать его, используйте более очевидный код.

Answer 3

Чтобы вычислить потолок n / m целиком, просто скажите:

n / m + (n % m == 0 ? 0 : 1)

В общем, скажем malloc(4 * (n / 3 + (n % 3 ? 1 : 0)));.

Answer 4

Хотя Kerrek SB имеет точный ответ, на практике большинство инженеров будет использовать malloc (4 + 4 * n / 3) или (эквивалентно) malloc (4 * (1 + n / 3)). Правила для C оценивают n/3 как целое число, приводящее к усечению остатка. Добавление немного больше к выражению гарантирует, что любая фракция, игнорируемая делением, будет выделена.

Самое большее, это может потратить три байта. Только если их будет тысячи, любые дополнительные вычисления для объяснения этого могут быть оправданы - возможно. Реализации malloc часто округляют распределение памяти до кратных 4, 8 или 16 байт, чтобы упростить ее ведение.

Рассмотрим стоимость 3 байта памяти: Текущая цена составляет от 5 до 15 долларов за гигабайт. Три байта стоят $ 0,000 000 009.