Как работает округление числа вверх до кратного?

Question

Как работает округление числа вверх до кратного?

Рейтинг: 1Ответов: 2Опубликовано: 21.05.2023

Вычитал в одной статье технику, которая позволяет округлить число X в большую сторону так, чтобы оно было кратно Y.

int roundup(int x, int y) {
    return ((x+y-1) & ~(y-1));
}

int main() {
    int x = 1020; // number to round up

    x = roundup(x, 512);

    return 0;
}

Этот пример кода округляет X до 1024, однако нигде не объясняется что происходит в функции roundup, поэтому прошу у вас объяснения по этому вопросу.

c# математика битовые-операции

Источник: Stack Overflow на русском

Answer 1

▲ 3Принят

Это работает при округлении до степеней двойки, а не до любого числа. Впрочем, такое округление нужно часто.

(x+y-1)

увеличивает число x так, чтобы получилось число, не меньше кратного y (включая x!), но не достигающее следующего кратного. Например, при y=4

8 + 3 = 11       8<=11<12 
9 + 3 = 12       12<=12<16 
10 + 3 = 13      12<=13<16 
11 + 3 = 14      12<=14<16 
12 + 3 = 15      12<=15<16 
13 + 3 = 16      16<=16<20

Инверсия

~(y-1)

при этой операции над числом y=2^k в скобках получается бинарное число с хвостом из единиц, причем количество этих единиц соответствует степени двойки k

4-1 = 3 = 0b00000011

А при его инверсии получается число из единиц с хвостом из k нулей.

~0b00000011 = 0b11111100

При выполнении операции AND обнуляется k последних бит, вот и получается кратность y

14 = 0b00001110
0b00001110 &  0b11111100 = 0b00001100 = 12

Про более универсальный вариант с целочисленным делением-умножением Harry уже написал

Answer 2

▲ 3

Секрет в &~(y-1), который обнуляет биты в конце, т.е. по сути выполняет деление на y с последующим умножением на него же и обеспечивает результат, кратный y.

int roundup(int x, int y) {
    return ((x+y-1)/y*y);
}

Кстати, этот вариант будет работать и для других y, не только степеней двойки.

Как работает округление числа вверх до кратного?

Ответы