为什么 n*(n+1)/2 % 2 等同于 if 条件下的按位运算 (n+1) & 2？

Question

更新 again:sorry 以输入错误 link 需要登录...您现在可以看到代码

更新：抱歉误导...已经编辑了标题

有一个 problem :

divide the sequence 1 ... n into 2 sequences which have the same sum, such as... you can divide [1 2 3 4 5 6 7] into [1 6 7] and [2 3 4 5], but not all sequences from 1 to n could divide like that, apparently if the sum of 1 to n, which is n*(n+1)/2, if this value is a odd number, it is impossible to do that.

但是我想知道，为什么条件[n*(n+1)/2 % 2]可以被[(n+1) & 2]代替？

我在 website

中看到了这个

问题网站是：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>
auto& c = std::cout;

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

Answer 1

n(n+1)和(n+1)的低2位由n的低2位决定。 n 的低 2 位只有 4 种可能，所以你可以将它们全部检查以确保两个表达式对应：

n%4   (n+1)%4   n(n+1)%4   (n+1)&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

是的，它工作得很好。

Answer 2

n*(n+1)/2 % 2 == 0 有效测试 n 或 n+1 是否可以被 4 整除；是否可以被2整除两次。确实，有两种可能性；如果 n 是偶数，那么 n+1 是奇数，所以除以 2 两次的唯一方法是让 n 被 4 整除。同样，如果 n 是奇数，那么 n+1 是偶数并且必须能被 4 整除才能满足条件。

类似地，(n+1) & 2 == 0 测试 n 或 n+1 是否可以被 4 整除。它测试 n+1 中的第二低位是否为零。如果最低位也是零，那么 n+1 可以被 4 整除（它看起来像二进制的 X00，所以可以右移两位而不产生进位）。如果n+1中的最低位是1，那么n中的最低位是0，那么n的形式是X00并且可以被4整除。

为什么 n*(n+1)/2 % 2 等同于 if 条件下的按位运算 (n+1) & 2？

why n*(n+1)/2 % 2 is equivalent to bitwise operation (n+1) & 2 in if condition?

c++

algorithm

bit-manipulation