Javascript Tip: a neat trick with the minus tilde for Objects

I'm currently doing some technical interview practice over at CodeSignal, and since a solution to a problem I wrestled with a bit is so much more elegant than mine, even though mine passed, I figured it would be helpful for others to see what is happening, so I'm posting it here.

The problem was to find the first instance of a character that is not repeated in a string, but only iterate over the string once (no nested for loops).

The solution had this weird thing I'd never seen: the minus, then a tilde.
Here's the original code:

firstNotRepeatingCharacter = s => {
    r = {}
    for (e of s)
      r[e] = -~r[e]


    for (e in r)         
        if (r[e] == 1)            
            return e

    return '_'
}

Nice!
But I couldn't figure out what was going on at first glance. Here is what I did to figure it out. I refactored it a little bit to separate the loops and added some console logs to output what is happening.

After doing a bit of research (you can look it up yourself) and testing, the minus tilde combination has the effect of taking the value that's already there and adding one to it, but the neat thing about this trick is that it will convert a return value of undefined to 1. Or, as it was (better) explained in the comments:

The ~ operator is the bitwise NOT. It inverts the bits. So undefined is treated as 0, and when inverted is 1111111111111111 which is basically -1 in two's-complement.

So now you have -(-1) which is 1.

If you ~1, you get 1111111111111110 which is -2. -(-2) = 2, and so on.

• Kiliman

The code below can be run to see exactly what's going on (the console tables are pretty slow so give it a minute if it's a long string).

firstNotRepeatingCharacter = s => {
    r = {}
    for (e of s) {
  console.log(`r[e] is the letter ${e}.\n   It's returning ${r[e]} from the object and being converted to ${-~r[e]} with the minus tilde`)
  r[e] = -~r[e];
  console.log(`storing ${e} in obj r with value ${-~r[e]}\n    object now looks like this:`);
  console.table(r);

    }
    console.table(r);
    for (e in r) {
        console.log(`checking ${e}`);
        if (r[e] == 1)

            return e
    }
    return '_'
}

So, what is happening above is that the first loop iterates over the string, and stores each letter inside an object (aka hash table, dictionary in other languages), with a value that is based on what is returned from the object.

If the letter is not already in the object, then it returns undefined, which will convert to 1 using the minus tilde operators.

If the letter is already in the object, then the minus tilde has the effect of adding 1 to the value already stored there.
So, the net effect of this code is to store the number of times the letter has been seen in the string as the value of the key (which in this case is the letter that was found in the string).
This is a shortcut that could have just as easily been accomplished by an if statement (which I think is more readable, but is probably not used for performance reasons):

if (r[e] == undefined) {
  r[e] = 1;
} else {
  r[e] += 1;

After the entire string has been checked and stored in the object, then the object is iterated over, in the order it was stored (in other words, in the same order they first appeared in the string).
The first letter that was only seen once in the string will return 1, so the if check will short circuit the second loop to return the first non repeating character from the function.

Hope this helps someone and saves them the ~hour I spent figuring this out :)

Comments

[Kiliman]

Nice.

The ~ operator is the bitwise NOT. It inverts the bits. So undefined is treated as 0, and when inverted is 1111111111111111 which is basically -1 in two's-complement.

So now you have -(-1) which is 1.

If you ~1, you get 1111111111111110 which is -2. -(-2) = 2, and so on.

developer.mozilla.org/en-US/docs/W...
en.wikipedia.org/wiki/Two%27s_comp...

[mikkel250]

Ahaaa! That's part of what I was failing to understand, is how the two were working together. The minus has the effect of flipping it back to positive. Thanks for the concise explanation!