быстрое увеличение числа до mod 16 в C

#c #math #video #bit-manipulation #modulus

#c #математика #Видео #манипулирование битами #модуль

Вопрос:

каков наилучший способ получить ближайшее, не меньшее число, которое делится на 16?

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

 int non_smaller_int_divisible_by_16(int x)
{
  return x   ((16 - (x % 16)) % 16);
}

ожидаемые результаты

 result | X values
-------|----------
16     | 1,2,..., 16
32     | 17, 18, ... 32
48     | 33, 34, ..., 48

и т. д

Ответ №1:

 int non_smaller_int_divisible_by_16(int x)
{
  return (x   15) amp; ~15;
}

Поскольку 16 — это степень двойки, вы можете использовать двоичную маскировку — добавьте 15, чтобы мы получили следующее по величине кратное, и замаскируйте побитовой инверсией 15, чтобы очистить нижние биты.

Редактировать:

Неясно, чего вы хотите добиться с отрицательными числами — и ваш, и мой код будут округляться до более положительных значений (т. Е. Отрицательные числа станут меньше). Если отрицательные значения не имеют смысла в вашей программе, было бы лучше использовать неподписанный тип.

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

1. действительно, отрицательные числа здесь неуместны, а с беззнаковыми типами оператор по модулю работает так же, как в математике колледжа, что значительно упрощает функцию.

Ответ №2:

решение @therefromhere более элегантное и быстрое, но если вам нужно сделать это с числом, которое не является степенью 2, тогда вы можете использовать этот подход.

 int non_smaller_int_divisible_by_n(int x, int n)
{
  return n*((x n-1)/n);
}

1. На самом деле, если вы объявите все «неподписанным» и сделаете n константой времени компиляции, GCC (по крайней мере) создаст код, идентичный версии с битовым изменением. Поскольку ваша форма более понятна и обобщенна, это предпочтительнее…

2. @nemo вы очень правы, на самом деле я продвигаю это как новый ответ

Ответ №3:

следуя комментарию @nemo, есть отличный способ решить эту проблему, который работает для всех баз модов, очень удобочитаем и должен быть быстрым

 unsigned int non_smaller_int_divisible_by_16(unsigned int x)
{
   return x   ((-x) % 16);
}

таким образом, общая версия

 unsigned int non_smaller_int_divisible_by_base(unsigned int x, unsigned int base)
{
   return x   ((-x) % base);
}

Ответ №4:

 int non_smaller_int_divisible_by_16(int x) {
    return (x amp; 15) ? (x | 15)   1 : x;
}