5

I have 

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

But that's a piece of garbage function. Help.

x is never going to be negative.

Here's a sort of Table of Truth, or something.

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

I'm trying to find some correlations here, but it's late and I don't think my brain is working correctly. zzz

What I'm seeing in the f(x) column is a sort of reverse modulus, whereby the outputs cycle from 032103210... instead of 01230123...

I'm sensing some use of Math.max or Math.min in combination with Math.abs might help … There's probably an x * -1 in there somewhere too …

Can you help me write f such that it doesn't suck so badly ?

Mulan
  • 129,518
  • 31
  • 228
  • 259

3 Answers3

4

Moving Redu's use of bitwise operators a bit ahead:

f(x) = -x & 3

Table of Truths™

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; }

Original solution with negative value and a negative offset of 3 then modulo and add the same offset again.

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; }
Community
  • 1
  • 1
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • 1
    ha, I was sort of wondering if you were online and this might get your attention. happy to get an answer from you. – Mulan Sep 07 '16 at 07:36
  • @naomik, i do what i can. maybe you have a look at the simplified bitwise solution ... ;) – Nina Scholz Sep 08 '16 at 20:26
  • 1
    super cool. I added a step-by-step table to this one too. Next time I reach for modulus, I'm gonna play with bitwise operators and see if I can achieve the same result – if anything, just to develop that part of my brain. – Mulan Sep 08 '16 at 20:45
  • I was naive and thought `-x & n` would work for arbitrary values of `n` but I'm stuck with `-x & 4` not working trying now to produce a 04321043210... sequence. I'll see what I can come up with, but let me know if you find something ! – Mulan Sep 09 '16 at 07:42
3

Something like this will definitely do:

(4 - (x % 4)) % 4

Here's some more truth:

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
Mulan
  • 129,518
  • 31
  • 228
  • 259
freakish
  • 54,167
  • 9
  • 132
  • 169
  • 3
    I'm going to leave this answer as accepted because it was the first correct answer and there is nothing wrong with it. For future peoples that find this question/answer, please see the two bitwise solutions provided by other users – they're brilliant. – Mulan Sep 08 '16 at 20:49
3

I thought you don't want to use modulo. Then here is your code.

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

Explanation: I just had to recall the back old days of truth tables which helped me to solve out this problem. So now we have inputs and output. Since we work in modulo 4 we are interested only in the last two bits.

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

So if we look, the output 2^1 digit is XOR of input 2^0 and 2^1 hence 2 * (x & 2 ? ~x & 1 : x & 1) and the output 2^0 digit is in fact input 2^0 digit. Which is (x & 1) hence... var f = x => 2 * (x & 2 ? ~x & 1 : x & 1) + (x & 1)

Note: (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
  • 25,060
  • 6
  • 56
  • 76
  • This looks interesting. I'm really interested to know the *design process* of this function. Would you mind walking me thru it ? – Mulan Sep 07 '16 at 07:37
  • @naomik Sure... I will edit the answer to include an explanation. – Redu Sep 07 '16 at 07:38
  • 1
    This is so fricken cool. Seriously awesome to see bitwise operations used like this. Can you help me visualize `~x` ? Console output isn't really helping me. `(~2).toString(2)` outs `-11` ? `(~4).toString(2)` outputs `-101`. – Mulan Sep 07 '16 at 07:52
  • Wait, is the binary output just wonky there? With two's compliment, `~2 === -3` but how do we write `-3` in binary ? – Mulan Sep 07 '16 at 07:54
  • Oh ! hahaha... ok I seriously need to go to bed. `-3` is just `-11` ... which is exactly what the console said before ... – Mulan Sep 07 '16 at 07:56
  • `~` is the bitwise not operator. It inverts 1 to 0 and 0 to 1. So since 4 is 100 you should expect to get 011 by ~4 but since JS has signed integers you negate the sign bit too and you get a negative figure. However if you limit 4 to its rightmost three bits like `(7 & ~4).toString(2)` you shall get `011`. – Redu Sep 07 '16 at 08:02
  • 1
    I added a step-by-step truth table for added visualization. I'm even more impressed by your formula after seeing this table. It's a thing of beauty. Ok, going to bed now. ありがとう！^_^ – Mulan Sep 07 '16 at 08:27
  • @naomik That's great job. Good night :) – Redu Sep 07 '16 at 08:31