Как найти следующее кратное 10 любого целого числа?

Question

Динамическое целое число будет любым числом от 0 до 150.

т.е. - число возвращает 41, нужно вернуть 50. Если число равно 10, нужно вернуть 10. Число равно 1, нужно вернуть 10.

Думал, что мог бы использовать функцию потолка, если бы я изменил целое число как десятичное число ...? затем использовать функцию потолка и вернуть обратно в десятичную?
Единственное, что также нужно знать, это число, состоящее из 1, 2 или 3 цифр (т.е. - 7 против 94 против 136)

Есть ли лучший способ добиться этого?

Спасибо,

Answer 1

n + (10 - n % 10)

Как это работает. Оператор% оценивает остаток от деления (поэтому 41 % 10 оценивается до 1, а 45 % 10 оценивается до 5). Вычитание этого из 10 оценивает, сколько вам нужно, чтобы достичь следующего кратного.

Единственная проблема заключается в том, что это превратит 40 в 50. Если вы этого не хотите, вам нужно добавить проверку, чтобы убедиться, что она не кратна 10.

if (n % 10)
    n = n + (10 - n % 10);

Answer 2

Вы можете сделать это, выполнив целочисленное деление на 10 , округлив , а затем умножив результат на 10.

Чтобы разделить A на B округления, добавьте B - 1 к A и затем разделите его на B, используя "обычное" целочисленное деление

Q = (A + B - 1) / B 

Итак, для вашей конкретной задачи время в целом будет выглядеть следующим образом

A = (A + 9) / 10 * 10

Это "привязает" A к следующему большему кратному 10.

Потребность в делении и выравнивании возникает так часто, что обычно в моих программах у меня были бы макросы для деления [беззнаковых] целых чисел с округлением в большую сторону

#define UDIV_UP(a, b) (((a) + (b) - 1) / (b))

и для выравнивания целого числа по следующей границе

#define ALIGN_UP(a, b) (UDIV_UP(a, b) * (b))

, который бы выглядел как

A = ALIGN_UP(A, 10);

P.S. Я не знаю, нужно ли это распространить на отрицательные числа. Если вы это сделаете, нужно позаботиться о том, чтобы сделать это правильно, в зависимости от того, что вам нужно в результате.

Answer 3

А как же ((n + 9) / 10) * 10?

Выход 0 => 0, 1 => 10, 8 => 10, 29 => 30, 30 => 30, 31 => 40

Answer 4

tl; dr: ((n + 9) / 10) * 10 компилируется в самый лучший (самый быстрый) asm-код в большинстве случаев , и его легко читать и понимать для людей, которые знают, что делает целочисленное деление в C. Это довольно общая идиома.

Я не исследовал, какой вариант лучше всего подходит для работы с отрицательным значением n, так как вы можете захотеть округлить от нуля, а не по-прежнему в направлении + Infinity, в зависимости от приложения.

---

Глядя на операции C, используемые различными предложениями, наиболее легким является Марк Дикинсон (в комментариях):

(n+9) - ((n+9)%10)

Это выглядит более эффективно, чем прямое деление / умножение, предложенное парой людей (включая @bta): ((n + 9) / 10) * 10, потому что вместо умножения просто добавление. (n+9 является общим подвыражением, которое должно быть вычислено только один раз.)

Оказывается, что оба компилируются в буквально идентичный код, используя хитрость компилятора преобразования деления на константу в умножения и сдвига, см. Эти вопросы и ответы о том, как это работает В отличие от аппаратной инструкции div, которая стоит одинаково, независимо от того, используете ли вы частное, остаток или оба результата, метод mul / shift принимает дополнительные шаги для получения остатка. Таким образом, компилятор видит, что он может получить тот же результат из более дешевых вычислений, и в итоге компилирует обе функции в один и тот же код.

Это верно для x86, ppc и ARM и всех других архитектур, на которые я смотрел в проводнике компилятора Godbolt. В первой версии этого ответа я видел sdiv для %10 на gcc4.8 Годболта для ARM64, но он больше не установлен (возможно, из-за неправильной настройки?) ARM64 gcc5.4 этого не делает.

У Godbolt сейчас установлен MSVC (CL), и некоторые из этих функций компилируются по-разному, но я не потратил время на то, чтобы выяснить, какая компиляция лучше.

---

Обратите внимание, что в выводе gcc для x86 умножение на 10 выполняется дешево: lea eax, [rdx + rdx*4] для n * 5, а затем add eax,eax для удвоения. imul eax, edx, 10 будет иметь на 1 цикл большую задержку в Intel Haswell, но будет короче (на одну меру меньше). gcc / clang не использует его даже с -Os -mtune=haswell: /

---

Принятый ответ (n + 10 - n % 10) вычисляется еще дешевле: n+10 может происходить параллельно с n%10, поэтому цепочка зависимостей на один шаг короче. Компилируется в одну инструкцию меньше.

Однако дает неправильный ответ для кратных 10: например, 10 -> 20. Предлагаемое исправление использует if(n%10), чтобы решить, делать ли что-либо. Это компилируется в cmov, поэтому он длиннее и хуже, чем код @ Bta. Если вы собираетесь использовать условное выражение, сделайте это, чтобы получить вменяемые результаты для отрицательных входных данных.

---

Вот как ведут себя все предложенные ответы, в том числе для отрицательных входных данных :

./a.out | awk -v fmt='\t%4s' '{ for(i=1;i<=NF;i++){ a[i]=a[i] sprintf(fmt, $i); } } END { for (i in a) print a[i]; }'
       i     -22     -21     -20     -19     -18     -12     -11     -10      -9      -8      -2      -1       0       1       2       8       9      10      11      12         18      19      20      21      22
    mark     -10     -10     -10     -10       0       0       0       0       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
    igna     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      10      10      10      10      20      20      20         20      20      30      30      30
    utaal    -20     -20     -20     -10     -10     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
     bta     -10     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      10      10      10      10      20      20         20      20      20      30      30
    klatchko -10     -10     -10     -10       0       0       0       0       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
    branch   -10     -10     -20       0       0       0       0     -10      10      10      10      10       0      10      10      10      10      10      20      20         20      20      20      30      30

( Транспонировать программу awk )

Игнасио n + (((9 - (n % 10)) + 1) % 10) работает «правильно» для отрицательных целых чисел, округляя в сторону + Infinity, но намного дороже для вычисления. Это требует двух операций по модулю, поэтому это в два раза дороже. Он компилирует примерно вдвое больше инструкций x86, выполняя примерно вдвое больше других выражений.

Программа для печати результатов (такая же, как ссылки на Godbolt выше)

#include <stdio.h>
#include <stdlib.h>

int f_mark(int n) { return (n+9) - ((n+9)%10); }                   // good
int f_bta(int n) { return ((n + 9) / 10) * 10; }                   // compiles to literally identical code

int f_klatchko(int n) { return n + 10 - n % 10; }                  // wrong, needs a branch to avoid changing multiples of 10
int f_ignacio(int n) { return n + (((9 - (n % 10)) + 1) % 10); }   // slow, but works for negative
int roundup10_utaal(int n) {  return ((n - 1) / 10 + 1) * 10; }

int f_branch(int n) { if (n % 10) n += (10 - n % 10); return n; }  // gcc uses cmov after f_accepted code

int main(int argc, char**argv)
{
    puts("i\tmark\tigna\tutaal\tbta\tklatch\tbranch");
    for (int i=-25 ; i<25 ; i++)
    if (abs(i%10) <= 2 || 10 - abs(i%10) <= 2)  // only sample near interesting points
        printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n", i, f_mark(i), f_accepted(i),
           f_ignacio(i), roundup10_utaal(i), f_bta(i), f_branch(i));
}

Answer 5

Как насчет использования целочисленной математики:

N=41
N+=9   // Add 9 first to ensure rounding.
N/=10  // Drops the ones place
N*=10  // Puts the ones place back with a zero

Answer 6

Имейте в виду, что ответы, основанные на операторах div и mod ("/" и "%"), не будут работать для отрицательных чисел без теста if, потому что C и C ++ неправильно реализуют эти операторы для отрицательных чисел. (-3 mod 5) равно 2, но C и C ++ вычисляют (-3% 5) как -3.

Вы можете определить свои собственные функции div и mod. Например,

int mod(int x, int y) {
  // Assert y > 0
  int ret = x % y;
  if(ret < 0) {
    ret += y;
  }
  return ret;
}

Answer 7

in C , однострочный :

int inline roundup10(int n) {
  return ((n - 1) / 10 + 1) * 10;
}

Answer 8

Вы можете сделать число мод 10. Затем возьмите тот результат, вычтите его из десяти. Затем добавьте этот результат к оригиналу.

if N%10 != 0  #added to account for multiples of ten 
  a=N%10
  N+=10-a

Answer 9

int n,res;
...

res = n%10 ? n+10-(n%10) : n;

или

res = (n / 10)*10 + ((n % 10) ? 10:0);

Answer 10

n + (((9 - (n % 10)) + 1) % 10)