Bitwise Operator? I Hardly Know Her!

NOT

“Tilde?! What does that even mean?”

I was recently working on the following coding challenge in CodeFights:

Given a string s, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'. Write a solution that only iterates over the string once and uses O(1) additional memory.

Here was my naive solution:

function firstNotRepeatingCharacter(s) {
const record = {}
for (let i = 0; i < s.length; i++) {
if (record[s[i]]) {
record[s[i]] += 1
} else {
record[s[i]] = 1
}
}
for (let key in record) {
if (record[key] === 1) {
return key
}
}
return '_'
}

After all my tests passed, I wanted to see how other people solved it. I clicked on the tab to see other solutions, and found the JavaScript solution with the most votes.

firstNotRepeatingCharacter = s => {
r = {}
for (e of s)
r[e] = -~r[e]
for (e in r)
if (r[e] == 1)
return e
return '_'
}

I read the solution, got confused by the fourth line, and then had that bittersweet moment where I thought, “It looks like I get to learn something new.”

I didn’t recognize the tilde, so I immediately Googled “js tilde.” I was relieved when I saw a result from MDN Web Docs.

Apparently, this sorcery had a name, and that name is Bitwise Operators. When the page loaded, I read the summary at the top of the page:

Bitwise operators treat their operands as a sequence of 32 bits (zeroes and ones), rather than as decimal, hexadecimal, or octal numbers. For example, the decimal number nine has a binary representation of 1001. Bitwise operators perform their operations on such binary representations, but they return standard JavaScript numerical values.
“That’s cool, but I still don’t know what the tilde is/does.”

Below the description, there was a chart of a bunch of operators that I pretty much never use on a daily basis. I scanned the chart, and clicked on the Bitwise NOT link next to the tilde example. The description read:

Performs the NOT operator on each bit. NOT a yields the inverted value (a.k.a. one's complement) of a.
“Again, that’s cool, but I still don’t know what the tilde is/does.”

Then there was the following code sample:

 9 (base 10) = 00000000000000000000000000001001 (base 2)
--------------------------------
~9 (base 10) = 11111111111111111111111111110110 (base 2) = -10 (base 10)
“I don’t know if you’re trying to confuse me, but if you are, it’s working. I’m going to sleep. I’ll try again tomorrow.”

I read that code sample, and decided that was a good stopping for that night (I think it was around 1am). The following day, I decided to try another approach.

“Instead of reading the docs and scary code samples, I’m just going to go play in the browser.”

I opened up a blank browser tab, opened the JavaScript console, and pasted the solution where I originally saw the tilde. I then slowly analyzed each line one at a time.

firstNotRepeatingCharacter = s => { // define function and args
r = {} // declare object to keep track of counts
for (e of s) // iterate through each character of the string
r[e] = -~r[e] // ¯\_(ツ)_/¯
for (e in r)
if (r[e] == 1)
return e
return '_'
}
“When in doubt, add some logging.”

I added a bunch of console.log's to see what was happening.

firstNotRepeatingCharacter = s => {
r = {}
for (e of s) {
console.log("--------------")
console.log("r: ", r)
console.log("e: ", e)
console.log(`r[${e}]: `, r[e])
r[e] = -~r[e]
}
console.log("r: ", r)
for (e in r)
if (r[e] == 1)
return e
return '_'
}

Then I called the function with the input from the first test case.

firstNotRepeatingCharacter('abacabad')
--------------
r: {}
e: a
r[a]: undefined
--------------
r: {a: 1}
e: b
r[b]: undefined
--------------
r: {a: 1, b: 1}
e: a
r[a]: 1
--------------
r: {a: 2, b: 1}
e: c
r[c]: undefined
--------------
r: {a: 2, b: 1, c: 1}
e: a
r[a]: 2
--------------
r: {a: 3, b: 1, c: 1}
e: b
r[b]: 1
--------------
r: {a: 3, b: 2, c: 1}
e: a
r[a]: 3
--------------
r: {a: 4, b: 2, c: 1}
e: d
r[d]: undefined
r: {a: 4, b: 2, c: 1, d: 1}
“Somehow, that tilde is building up a count of occurrences.”

After looking at the logs, the tilde started making a little bit of sense.

I logged a line of dashes to easily differentiate between the iterations, the state of the object, r, the current character of the string, e, and the value r[e]. Then after the loop was completed, I logged the ending state of the object, r.

Iteration #1: r is {}, e is 'a', and r[a] is undefined. Makes sense.
Iteration #2: r is {a: 1}, e is 'b', and r[b] is undefined. Makes sense.
Iteration #3: r is {a: 1, b: 1}, e is 'a', and r[a] is 1. Why is it 1?

So then I added another console.log to understand why r[a] equals 1.

firstNotRepeatingCharacter = s => {
r = {}
for (e of s) {
console.log("--------------")
console.log("r: ", r)
console.log("e: ", e)
console.log(`r[${e}]: `, r[e])
console.log(`~r[${e}]`, ~r[e])
r[e] = -~r[e]
}
console.log("r: ", r)
for (e in r)
if (r[e] == 1)
return e
return '_'
}

Then I called the function with the same input as the previous run.

firstNotRepeatingCharacter('abacabad')
--------------
r: {}
e: a
r[a]: undefined
~r[a] -1
--------------
r: {a: 1}
e: b
r[b]: undefined
~r[b] -1
--------------
r: {a: 1, b: 1}
e: a
r[a]: 1
~r[a] -2
--------------
r: {a: 2, b: 1}
e: c
r[c]: undefined
~r[c] -1
--------------
r: {a: 2, b: 1, c: 1}
e: a
r[a]: 2
~r[a] -3
--------------
r: {a: 3, b: 1, c: 1}
e: b
r[b]: 1
~r[b] -2
--------------
r: {a: 3, b: 2, c: 1}
e: a
r[a]: 3
~r[a] -4
--------------
r: {a: 4, b: 2, c: 1}
e: d
r[d]: undefined
~r[d] -1
r: {a: 4, b: 2, c: 1, d: 1}
“~undefined === -1? What a country?!” — Dr. Nick

The new logs let me clearly see what the tilde was doing.

~undefined === -1 // true
~1 === -2 // true
~2 === -3 // true
~3 === -4 // true

When applied to an int, the tilde seemed like it was incrementing the int by one, and then multiplying the incremented int by -1.

I now realize that if I had read the entire section from the documentation, instead of giving up and going to bed, I would have seen this explanation much sooner.

Bitwise NOTing any number x yields -(x + 1). For example, ~5 yields -6.

Once I understood that, I was able to understand where the character counts were coming from.

If ~1 === -2, then -(~1) === 2.

And once I understood where the character counts were coming from, I was able to understand where the return value was coming from.

for (e in r)       // iterate through each character:count pair
if (r[e] == 1) // if that character's count equals 1
return e // return that character
return '_' // if no character counts equal 1, return '_'

While I understood the solution, I wanted to try rewriting it to see if I could make it cleaner.

I pasted the solution in my text editor, and saved the file. Since I recently started using prettier, the code style automatically updated to match the style defined in my configuration (mostly default).

Here is the output after running the original solution through prettier:

firstNotRepeatingCharacter = s => {
r = {};
for (e of s) r[e] = -~r[e];
for (e in r) if (r[e] == 1) return e;
return '_';
};

On one hand, I really like how short the solution is. But on the other hand, I don’t think it’s immediately clear what’s going on, especially if you’re not familiar with the Bitwise NOT operator. Additionally, it feels like a Code Golf solution.

Bonus Learning: I showed this solution to two of my coworkers that are way smarter than me, and they immediately informed me about a thing called Two’s complement.

While I’m bummed that it took me as long as it did to understand what the tilde does in JavaScript, I’d rather learn the hard way than not learn at all.

Feel free to leave a comment, follow me on Twitter, and/or follow me on Instagram.