如何简化模数算术？

Question

I have

let f = x => x % 4 === 0 ? 0 : 4 - x % 4

但那个函数太糟糕了。求救。

x 永远不可能为负数。

---

这里有一个真理表之类的东西。

x   x % 4     4 - (x % 4)     f(x)
0   0         4               0
1   1         3               3
2   2         2               2
3   3         1               1
4   0         4               0
5   1         3               3
6   2         2               2
7   3         1               1
8   0         4               0
9   1         3               3

我在这里尝试寻找一些相关性，但现在已经很晚了，我不认为我的大脑能正常工作。嗯嗯嗯

在f(x)列中，我看到的是一种反向模数，即输出从032103210...循环而不是01230123...

我感觉使用Math.max或Math.min与Math.abs相结合可能会有所帮助……可能还有一个x * -1。

你能帮我写一个更好的f吗？

- Mulan

Answer 1

将Redu的按位运算符的使用向前推进一点：

f(x) = -x & 3

真理表™

x       x       -x       3    -x&3    -x&3
-    ----    -----    ----    ----    ----
0    0000     0000    0011    0000       0
1    0001    -0001    0011    0011       3
2    0010    -0010    0011    0010       2
3    0011    -0011    0011    0001       1
4    0100    -0100    0011    0000       0
5    0101    -0101    0011    0011       3
6    0110    -0110    0011    0010       2
7    0111    -0111    0011    0001       1
8    1000    -1000    0011    0000       0
9    1001    -1001    0011    0011       3

var i, 
    f = x => -x & 3;

for (i = 0; i < 20; i++) {
    console.log(i, f(i));
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

原始解决方案使用负值和负偏移量3，然后进行取模运算并再次添加相同的偏移量。

f(x) = (-x - 3) % 4 + 3

var i, 
    f = x => (-x - 3) % 4 + 3;

for (i = 0; i < 20; i++) {
    console.log(i, f(i));
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

哈，我有点想知道你在线上，也许这会引起你的注意。很高兴能从你那里得到答案。 - Mulan

@naomik，我尽力了。也许你可以看一下简化的位运算解决方案... ;) - Nina Scholz

超酷。我也在这个里面添加了一个逐步表格。下次我使用模数时，我会尝试使用位运算符来看看是否可以实现相同的结果 - 如果有什么不同，只是为了开发我的大脑的那一部分。 - Mulan

我很天真地认为-x＆n可以适用于任意值的n，但我现在卡在了-x＆4无法工作上，现在尝试生成一个04321043210...序列。我会看看能想出什么，但如果你找到了什么，请告诉我！ - Mulan

Answer 2

像这样的东西肯定可以：

(4 - (x % 4)) % 4

以下是更多的真相：

x   x % 4     4 - (x % 4)     (4 - (x % 4)) % 4
0   0         4               0
1   1         3               3
2   2         2               2
3   3         1               1
4   0         4               0
5   1         3               3
6   2         2               2
7   3         1               1
8   0         4               0
9   1         3               3

- freakish

---

我会将这个答案标记为被接受的，因为它是第一个正确的答案，而且没有任何问题。对于以后发现这个问题/答案的人，请查看其他用户提供的两个位运算解决方案——它们非常棒。 - Mulan

Answer 3

我以为你不想使用模数。那么这里是你的代码。

var f = x => 2 * (x & 2 ? ~x & 1 : x & 1) + (x & 1)

x   x % 4    4 - (x % 4)       f(x)
0     0         4               0
1     1         3               3
2     2         2               2
3     3         1               1
4     0         4               0
5     1         3               3
6     2         2               2
7     3         1               1
8     0         4               0
9     1         3               3

解释：我只需要回忆一下真值表的旧日子，就能帮助我解决这个问题。现在我们有输入和输出。由于我们使用模4，我们只关注最后两位。

 Input    Output
0 : 0 0    0 0
1 : 0 1    1 1
2 : 1 0    1 0
3 : 1 1    0 1

因此，如果我们看一下，输出2^1位是输入2^0和2^1的XOR，因此是 2 * (x & 2 ? ~x & 1 : x & 1)，而输出2^0位实际上是输入2^0位。也就是说是 (x & 1) 因此... var f = x => 2 * (x & 2 ? ~x & 1 : x & 1) + (x & 1)

注意：(foo XOR bar = foo ? !bar : bar)

---

                                 u       v
                        y        z       z       w
   x       x & 2   ?    ~x       y & 1   x & 1   2 * z  w + v  f(x)
-- ------  ------  ---  -------  ------  ------  -----  -----  ----
0  0000    0000    F    -0001    0001    0000    0      0      0
1  0001    0000    F    -0010    0000    0001    2      3      3
2  0010    0010    T    -0011    0001    0000    2      2      2
3  0011    0010    T    -0100    0000    0001    0      1      1
4  0100    0000    F    -0101    0001    0000    0      0      0
5  0101    0000    F    -0110    0000    0001    2      3      3
7  0110    0010    T    -0111    0001    0000    2      2      2
8  0111    0010    T    -1000    0000    0001    0      1      1
9  1000    0000    F    -1001    0001    0000    0      0      0

- Redu

---

这看起来很有趣。我非常想了解这个函数的设计过程。你介意给我讲解一下吗？ - Mulan

这太酷了。真的很棒能看到位运算被用在这样的地方。你能帮我可视化一下 ~x 吗？控制台输出并不能真正帮助我。(~2).toString(2) 输出 -11？(~4).toString(2) 输出 -101。 - Mulan

等等，二进制输出有问题吗？使用二进制补码，~2 === -3，但是我们如何用二进制表示 -3 呢？ - Mulan

哦！哈哈哈...好的，我得认真去睡觉了。-3只是-11...这正是控制台之前所说的... - Mulan

我添加了一个逐步真值表以增加可视化效果。看到这个表格后，我对你的公式更加印象深刻了。它是一件美丽的事情。好的，现在要去睡觉了。ありがとう！^_^ - Mulan