DEV Community

Santiago Salazar Pavajeau
Santiago Salazar Pavajeau

Posted on

Simple bit manipulation

While looking at algorithms in the past, whenever I came across a bitwise operator like <<, >>, &, |, ^, I would think: "this is too complicated". However, with time learning is amazing because we can start accepting new concepts and they stop being unreachable.

Simply put these are some 'binary numbers'. As we move a 1 to the left the previous number multiplies by 2.

0001 is 1
0010 is 2
0011 is 3 // 3 is 2 and 1 combined
0100 is 4
Enter fullscreen mode Exit fullscreen mode

To know why binary to regular numbers(decimal) converts like this in more depth check this out.

Taking these fundamentals into account operations with binaries or bit manipulation allows to make modifications or also to compare different numbers, and even also do the same with characters converted to binary.

So bitwise operators are similar to math operators or logical operators but they deal with binary numbers.

As a quick example of a bitwise operation if we do 2<<1 the result is 4. This is because the left shift << serves to move all 1 bits in a binary number to the left so:

2 which is 0010

moves left and becomes

4 which is 0100
Enter fullscreen mode Exit fullscreen mode

So a left shift << 1 by one space, multiplies by two.

Same with the right shift >> 1 and it simply divides by two.

Now with the other operations & | ^ or ~. We are able to compare two binary numbers. And with this context a video like this might make more sense.

Mapping characters to Binary

So to achieve this we have to recall that letters have the corresponding number codes called ASCII codes. In javascript, we can get this code with the .charCodeAt() method.

For example, a lowercase 'a' has an ASCII code of 97 and a lowercase 'b' is 98.

Then a character can be mapped to a binary by moving a bit to correspond to an ASCII code.

let anumberOfLeftShifts = 'a'.charCodeAt(0) - 97 // returns 0 bc 97 - 97

let aInBinary = 1 << anumberOfLeftShifts
// => 0001

let bnumberOfLeftShifts = 'b'.charCodeAt(0) - 97 // returns 1 bc 98 - 97

let aInBinary = 1 << bnumberOfLeftShifts
// => 0010

Enter fullscreen mode Exit fullscreen mode

So mapping a number and a character to binary is a different process but both ways allow to do bit manipulation.

As a quick example, we can see if two strings have the same letters.

let s1 = "hello"
let s2 = "loeh"

let s1Mask = 0
let s2Mask = 0

for(let i = 0;i<s1.length; i++){
 s1Mask = s1Mask | 1 << targetString[i].charCodeAt(0) - 97
// add each character to as a bit in corresponding position to mask
}

for(let i = 0;i<s2.length; i++){
 s2Mask = s2Mask | 1 << targetString[i].charCodeAt(0) - 97
// add each character to as a bit in corresponding position to mask
}

if(s1Mask & s2Mask === s1Mask){
 // compare masks to see if all bits match
 // by comparing the result of an AND bitwise operation
 // to the original mask
 console.log('strings have the same letters')
}
Enter fullscreen mode Exit fullscreen mode

Here a list of what bitwise operators do in comparing bits:

  • & AND if they are the same returns same bit, if they are different returns 0

  • | OR if they are the same returns same bit, if they are different returns 1

  • ^ XOR if they are the same returns 0, if they are different returns 1

Feel more than welcome to reach out with any ideas/comments at Linkedin or Twitter, or check out my portfolio.

Top comments (0)