Блог

Главная - Вопросы по программированию - почему n*(n 1)/2% 2 эквивалентно побитовой операции (n 1)

почему n*(n 1)/2% 2 эквивалентно побитовой операции (n 1)

#c #algorithm #bit-manipulation

Вопрос:

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

обновление:извините, что ввел в заблуждение…уже отредактировал заголовок

есть проблема :

разделите последовательность 1 ... n на 2 последовательности, которые имеют одинаковую сумму, например… вы можете разделить [1 2 3 4 5 6 7] на [1 6 7] и [2 3 4 5] , но не все последовательности от 1 до n могут делиться подобным образом, по-видимому, если сумма от 1 до n , то есть n*(n 1)/2 , если это значение нечетное число, это невозможно сделать.

но я хочу знать, почему это условие [n*(n 1)/2 % 2] может быть заменено на [(n 1) amp; 2] ?

Я вижу это на веб-сайте

проблема веб-сайта заключается в следующем : https://cses.fi/problemset/task/1092

и этот код находится здесь :https://paste.ubuntu.com/p/GfVG9R67zj/

 ///2021-06-17 02:21:43  SchizoYoshi C  17   0.10 s
///paste from https://cses.fi/problemset/hack/1092/entry/2352488/
#include <iostream>
autoamp; c = std::cout;

int main() {
    int n, i{};
    std::cin >> n;
    if (  n amp; 2)
        c << "NO ";
 
    c << "YES " << n-- / 2 << ' ';
    while (n - i  )
        if (i - n amp; 2)
            c << i << ' ';
    c << n-- / 2 << ' ';
    while (--i)
        if (n - i amp; 2)
            c << i << ' ';
}

Комментарии:

1. Они не эквивалентны. Как ты думаешь, почему они такие? Ссылка «веб-сайт» ведет на пустую страницу для меня, поэтому я не уверен, что вы там видите. Не могли бы вы скопировать и вставить все, что здесь есть, чтобы нам не нужно было входить в систему, чтобы просмотреть это?

2. Они не равны, попробуй n=2 .

3. Они не всегда могут быть равны. Возможные значения n*(n 1)/2 % 2 равны 0 и 1; возможные значения (n 1) amp; 2 равны 0 и 2

4. Мне жаль вводить вас в заблуждение… они в хорошем состоянии

5. Они равны как условия. если оба они будут переданы в условие, оба будут выполнять одну и ту же ветвь, которая указана в вопросе

Ответ №1:

n*(n 1)/2 % 2 == 0 эффективно проверяет n , делится ли n 1 оно на 4; может ли оно быть дважды разделено на 2. Действительно, есть две возможности; если n четно, то n 1 нечетно, поэтому единственный способ разделить на 2 дважды-это n разделить на 4. Аналогично, если n нечетно, то n 1 четно и должно быть делимо на 4, чтобы условие выполнялось.

Аналогично, (n 1) amp; 2 == 0 проверяет, делится ли или n или n 1 на 4. Он проверяет, что второй младший бит равен нулю n 1 . Если младший бит также равен нулю, то n 1 он делится на 4 (выглядит как X00 в двоичном формате, поэтому может быть сдвинут на два бита вправо без создания переноса). Если младший бит в n 1 равен 1, то младший бит в n равен нулю, а затем n имеет форму X00 и делится на 4.

Ответ №2:

Нижние 2 бита n(n 1) и (n 1) определяются нижними 2 битами n. Есть только 4 возможности для младших 2 бит n, поэтому вы можете просто проверить их все, чтобы убедиться, что два выражения соответствуют:

 n%4   (n 1)%4   n(n 1)%4   (n 1)amp;2   n(n 1)/2%2   
---   -------   --------   -------   ----------
 0       1         0          0          0
 1       2         2          2          1
 2       3         2          2          1
 3       0         0          0          0

Да, это работает просто отлично.

Метки: