Data Structures & Algorithms 101: Bit Manipulation in JavaScript Part 2
Welcome back fellow developers! I’m excited for this week’s part 2 of bit manipulation. If you haven’t read part 1 and you’re new to bit manipulation, I would recommend checking out part 1 before you venture on. Just to recap, last week I introduced bit manipulation and its significance in data structure and algorithms. I also went through several bitwise operations that were some basic manipulation techniques for bits. This week, I want to dive a little deeper and cover more advanced operations such as shifting, and adding and subtracting complements. Let’s dive right in!
Shifting (<< / >>)
Shifting is a bitwise operation that causes a binary representation to shift either left or right according to a specified number. There are two types of shifts you will encounter, logical and arithmetic. Logical shifting is very simple, it shifts the binary representation left or right based on a specified number and a 0 is included at the end of the shifted binary number. Let’s review an example!
Logical Shifting
Left-Logical Shift (<<): The left logical shift of one position moves each bit to the left by one. The least significant bit (LSB), which is the right most bit in the binary representation is filled with 0 and the most significant bit (MSB), which is the left most bit in the binary representation, is discarded.
Right-Logical Shift (>>): The right logical shift of one position moves each bit to the right by one. The LSB is discarded and then the MSB is filled with 0.
Arithmetic Shifting
When it comes to arithmetic shifting, the only difference it has with logical shifting is when you shift right. The left shifting, whether logical or arithmetic are identical in process. Arithmetic shift operations are primarily used for dividing or multiplying an integer variable. The left shift operation will provide a result of multiplying 2^n, where n is the number of shifted bit positions. Let’s look at an example in our console.
If you look at the example, the variable six has a value of 6 and it is represented in binary as 110. Using the left shift operator, we were able to shift the binary representation of six (‘110’) to the left and following the process above, we are returned a value of 12 or in binary, 1100. The left shift operation (<<) multiplied six by 2¹ to provide a value of 12 (6 * 2). I used the left shift operation once more to multiply six by 2² (4) to get a result of 24 or in binary, 11000.
Right-Arithmetic Shift
Although the left arithmetic shift is similar to the left logical shift, the right arithmetic shift is not the same as its logical counterpart. The right arithmetic shift operation moves each bit to the right by one. The LSB is discarded and the vacant MSB is filled with the value of the previous (now shifted one position to the right) MSB. Let’s look at an example.
The right arithmetic shift operator is used to divide an integer variable. It is a division of the binary number by 2^n, with n being the number of shifted bit positions. Let’s look at an example in our console. We can use the variable six again.
You can see from the example that when we use the right shift operator on six (110), when we shift by one we receive a value of 3 because the value of 6 is divided by 2¹, which is how we received a result of 3 or ‘11’ in binary. I also tested the operator by shifting six by 2 and received a result of 1, which confirms the method.
Adding and Subtracting
When it comes to adding and subtracting bits it is not too different from the procedures of adding and subtracting decimals. However, subtracting binary numbers requires an additional step prior to getting the result. Let’s walk through each operation through examples.
Addition
Similar to the procedure for addition with decimals, binary numbers are handled the same way. Let’s go to the board and see an example.
In this example, we add 1101 (value: 13) and 1011 (value: 11) to get the answer 11000, which equals 24 in decimal form. When we walk through this we start at the least significant bit (1 + 1) and work from right to left. From the LSB we get 10 (2) where we leave the 0 and carry the 1 to the next integers. 1 plus 0 equals 1 but plus the 1 that we carried over from the previous integers equals 10 (2) and we leave 0 and carry the 1 to the next integer. In the next integers, 1 + 0, we add both to get 1 but similar to the last two integers, we need to add the 1 that was carried over. We get a similar result and leave the 0 and carry the one to the following integers. Finally, we reach the most significant bits (1 + 1), which equals a value of 2 (bit: 10), but we need to make sure we add the 1 that carried over from the previous integer. 2 + 1 equals a value of 3 which returns a binary representation of 11. The final answer we calculated is the binary representation 11000, which has a value of 24 and coincides with the decimal result of 13 + 11.
Subtraction
When working with bits, unlike addition, subtraction uses a different procedure. When we subtract binary numbers from each other, we start by taking the inverse (complement) of the second operand. Once we obtain the second operand’s complement, we add 1 to it. Then we add the first positive operand and the negative second operand to subtract the two numbers. Let’s look at an example where we subtract 3 (0011) from 7 (0111).
If we look at the example we invert 3 and add the inversion to get the negative value of 3. Then we add 111 (value: 7) to 101 (value: -3) to get the result of 100 (value: 4). If you look at the calculation above, you will see that I applied the same addition procedures as I did in the addition section above. In this example, please note I used a signed number in order to establish positive and negative numbers.
Conclusion
Well, thank you for coming back to examine part 2 on bit manipulation to learn about shifting and adding and subtracting binary numbers. I hope this little tutorial gave you some tools for tackling bit manipulation. I have only covered the foundations of bit manipulation though, and there is still so much more to learn about! As always I challenge you to work on bit manipulation problems online and practice using some of these methods. Thank you again for joining and I hope to see you next week!