loading...

Learn Data Structure and Algorithm in JavaScript | Part 20

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) ใƒป33 min read


Prerequisite (โœ‹๐Ÿ˜)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 19: Dynamic Programming

Part Table of Contents Description
01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String objectโ€™s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(โ—) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(๐Ÿ˜‰)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (๐Ÿ’ก).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (๐Ÿ‘€). (๐Ÿ˜ƒ)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (๐Ÿ˜ƒ)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (๐Ÿ”ˆ)) not (kwewe) okay? hehehe (๐Ÿ˜…); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (๐Ÿ˜ฎ) There are two types of linked lists: singly (โžก๏ธ) and doubly (โ†”๏ธ). Letโ€™s examine the singly linked list first.(๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (๐Ÿ˜ƒ)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (๐Ÿ‘)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (๐Ÿ˜‰)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (โฌ‡๏ธ). To explain dynamic programming, letโ€™s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (๐Ÿ˜‰)

Part 20: Bit Manipulation (๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ”ข)

Alt Text

Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

Bitwise Operators (0๏ธโƒฃ0๏ธโƒฃ)

Alt text

Here are the bitwise operators in JavaScript:

Symbol Meaning
& AND
| OR
~ NOT
^ XOR
<< Left Shift
>> Right Shift
>>> Zero-fill right shift

Note (๐Ÿ“): Recall from Part 3 that all numbers are represented with 32 bits (meaning there are 32 1s and 0s). When converting from decimal numbers (base 10) to binary (base 2), it is important to keep this in mind.

AND(1๏ธโƒฃโž•0๏ธโƒฃ)

The AND operator is true when both bits are 1. The ampersand (&) is used for the AND operator:

a Operator b Result
0 AND 0 0
0 AND 1 0
1 AND 0 0
1 AND 1 1

In bitwise operations, the numbers are in binary representation. For example, 9 in binary is 1001, and 5 in binary is 101. For each bit, the AND operation has to be performed:

// 9: 1 0 0 1
// 5: 0 1 0 1
//  : 0 0 0 1 (Base 2)
//  : 1 (Base 10)

console.log(9 & 5); // Print: "1"

// 40: 1 0 1 0 0 0
// 41: 1 0 1 0 0 1
//   : 1 0 1 0 0 0 (Base 2)
//   : 40 (Base 10)

console.log(40 & 41); // Print: "40"
Enter fullscreen mode Exit fullscreen mode
// 9: 1 0 0 1 // 5: 0 1 0 1 // : 0 0 0 1 (Base 2) // : 1 (Base 10) console.log(9 & 5); // Print: "1" // 40: 1 0 1 0 0 0 // 41: 1 0 1 0 0 1 // : 1 0 1 0 0 0 (Base 2) // : 40 (Base 10) 40 & 41; // Print: "40" // Note: You will notice that we removed the console.log, we did that so that runkit would not return undefined, so it is optional

OR(1๏ธโƒฃโ†”๏ธ0๏ธโƒฃ)

The OR operator is when either bit is 1. The pipe (|) is used for the OR operator:

a Operator b Result
0 OR 0 0
0 OR 1 1
1 OR 0 1
1 OR 1 1
// 9: 1 0 0 1
// 5: 0 1 0 1
//  : 1 1 0 1 (Base 2)
//  : 13 (Base 10)

console.log(9 | 5); // Print: "13"

// 40: 1 0 1 0 0 0
// 41: 1 0 1 0 0 1
//   : 1 0 1 0 0 1 (Base 2)
//   : 41 (Base 10)

console.log(40 | 41); // Print: "41"
Enter fullscreen mode Exit fullscreen mode
// 9: 1 0 0 1 // 5: 0 1 0 1 // : 1 1 0 1 (Base 2) // : 13 (Base 10) console.log(9 | 5); // Print: "13" // 40: 1 0 1 0 0 0 // 41: 1 0 1 0 0 1 // : 1 0 1 0 0 1 (Base 2) // : 41 (Base 10) 40 | 41; // Print: "41"

XOR(1๏ธโƒฃโ†”๏ธ1๏ธโƒฃ)

XOR means exclusive or (See on Wikipedia). It evaluates to true only when one of the bits is 1. The caret (^) is used for the XOR operator:

a Operator b Result
0 XOR 0 0
0 XOR 1 1
1 XOR 0 1
1 XOR 1 0
// 9: 1 0 0 1
// 5: 0 1 0 1
//  : 1 1 0 0 (Base 2)
//  : 12 (Base 10)
console.log(9 ^ 5); // Print: "12"

// 40: 1 0 1 0 0 0
// 41: 1 0 1 0 0 1
//   : 0 0 0 0 0 1 (Base 2)
//   : 1 (Base 10)

console.log(40 ^ 41); // Print: "1"
Enter fullscreen mode Exit fullscreen mode
// 9: 1 0 0 1 // 5: 0 1 0 1 // : 1 1 0 0 (Base 2) // : 12 (Base 10) console.log(9 ^ 5); // Print: "12" // 40: 1 0 1 0 0 0 // 41: 1 0 1 0 0 1 // : 0 0 0 0 0 1 (Base 2) // : 1 (Base 10) 40 ^ 41; // Print: "1"

NOT(1๏ธโƒฃโŒ0๏ธโƒฃ)

The NOT operator inverses all bits. The tilde (~) is used for the NOT operator:

NOT a Result
~0 1
~1 0
// 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
//  : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 (Base 2 - Inverted)
//  : -10 (Base 10)

console.log(~9); // Print: "-10"

// 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
//  : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 (Base 2)
//  : -6 (Base 10)

console.log(~5); // Print: "-6"
Enter fullscreen mode Exit fullscreen mode
// 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 // : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 (Base 2 - Inverted) // : -10 (Base 10) console.log(~9); // Print: "-10" // 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 (Base 2) // : -6 (Base 10) ~5; // Print: "-6"

Left Shift(1๏ธโƒฃโฌ…๏ธ0๏ธโƒฃ)

In left shift, all the bits are shifted to the left, and any excess bits shifted off to the left are discarded. The double left-angle brackets (<<) is the operator of left shift:

var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
           // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (Base 2)
           // 288 (Base 10)
console.log(a << b);

// Explain:
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 (1st)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 (2nd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 (3rd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 (4th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (5th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (After)
Enter fullscreen mode Exit fullscreen mode
var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (Base 2) // 288 (Base 10) a << b; // Print: "288" // Explain: // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 (1st) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 (2nd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 (3rd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 (4th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (5th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 (After)

Left shift often multiplies elements by 2 for each shift. This is because binary is a base 2 system, implying a left shift is equal to multiplying all the digits by 2. And we have a math formula for it:

xร—(2y) x \times \lparen 2^{y}\rparen

Note (๐Ÿ“): However, the shift can cause the bit to overflow and reduce the value.

Right Shift(1๏ธโƒฃโžก๏ธ0๏ธโƒฃ)

In right shift, all the bits are shifted to the right, and any excess bits shifted off to the right are discarded. The double right angle brackets (>>) is the operator for right shift:

var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
           // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (Base 2)
           // 0 (Base 10)
console.log(a >> b); // Print: "0"

// Explain: "|" means cut (discarded)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 1 (1st)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0 1 (2nd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 0 1 (3rd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 0 0 1 (4th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 1 0 0 1 (5th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (After)
Enter fullscreen mode Exit fullscreen mode
var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (Base 2) // 0 (Base 10) a >> b; // Print: "0" // Explain: "|" means cut (discarded) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 1 (1st) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0 1 (2nd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 0 1 (3rd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 0 0 1 (4th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 1 0 0 1 (5th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (After) // Note: You can change "9" to "-9" and gives you "-1" result. This is because it has different base 2 representation.

Zero-Fill Right Shift(โžก๏ธโžก๏ธโžก๏ธ)

In zero-fill right shift, all the bits are shifted to the right, and any excess bits shifted off to the right are discarded. However, the sign bit (the leftmost bit) becomes a 0 before the shift, and this results in a non-negative number. The triple right brackets (>>>) is the operator for the zero-fill right shift:

var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Positive)
var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
           // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (Base 2)
           // 0 (Base 10)
console.log(a >>> b); // Print: "0"

// Explain: "|" means cut (excess is discarded)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 1 (1st)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0 1 (2nd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 0 1 (3rd)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 0 0 1 (4th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 1 0 0 1 (5th)
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (After)


var a = -9; // 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 (Negative)
var b = 5;  // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
            // 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (Base 2)
            // 134217727 (Base 10)
console.log(a >>> b); // Print: "134217727"

// Explain: "|" means cut (excess is discarded)
// 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 (Before)
// 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 | 1 (1st)
// 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 | 1 1 (2nd)
// 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 | 1 1 1 (3rd)
// 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 0 1 1 1 (4th)
// 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 1 0 1 1 1 (5th)
// 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (After)
Enter fullscreen mode Exit fullscreen mode
var a = 9; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Positive) var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (Base 2) // 0 (Base 10) console.log(a >>> b); // Print: "0" // Explain: "|" means cut (excess is discarded) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 (Before) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 1 (1st) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0 1 (2nd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 0 1 (3rd) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 0 0 1 (4th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 1 0 0 1 (5th) // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (After) var a = -9; // 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 (Negative) var b = 5; // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (Base 2) // 134217727 (Base 10) a >>> b; // Print: "134217727" // Explain: "|" means cut (excess is discarded) // 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 (Before) // 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 | 1 (1st) // 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 | 1 1 (2nd) // 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 | 1 1 1 (3rd) // 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 0 1 1 1 (4th) // 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 1 0 1 1 1 (5th) // 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (After)

Practical Use #1: Number Operators (๐Ÿ”ข๐Ÿ”ข)

Alt text

This section will cover how to perform addition, subtraction, multiplication, division, and modulus using bitwise operators.

Addition(9๏ธโƒฃโž•5๏ธโƒฃ)

Adding binary numbers is no different from adding decimal numbers. The function that implements this is as follows:

function BitwiseAdd(a, b) {
    while (b != 0) {
        var carry = (a & b);
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

console.log(BitwiseAdd(9, 5)); // Print: "14"

// Explain 1:
//            9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
//            5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
//   a = a ^ b = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 (Base 2)
//   a = a ^ b = "12" (Base 10)

// Explain 2:
//                    a: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
//                    b: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
// var carry = (a & b) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 (Base 2)

// Explain 3:
//          carry: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
//              1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
// b = carry << 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 (Base 2)
// b = carry << 1: "2" (Base 10)

// Explain 4:
//       2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
//      12: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
// 2 ^ 12 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 (Base 2)
// 2 ^ 12 = "14" (Base 10)
Enter fullscreen mode Exit fullscreen mode
function BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a; } BitwiseAdd(9, 5); // Print: "14" // Explain 1: // 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 // 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // a = a ^ b = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 (Base 2) // a = a ^ b = "12" (Base 10) // Explain 2: // a: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 // b: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 // var carry = (a & b) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 (Base 2) // Explain 3: // carry: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 // 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 // b = carry << 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 (Base 2) // b = carry << 1: "2" (Base 10) // Explain 4: // 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // 12: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 // 2 ^ 12 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 (Base 2) // 2 ^ 12 = "14" (Base 10)

Subtraction(9๏ธโƒฃโž–5๏ธโƒฃ)

Subtraction is the difference of two numbers. However, you can also think of it as adding a negative number. Hereโ€™s an example: 5โˆ’4=5+(โˆ’4)5 - 4 = 5 + (-4) . Therefore, first create a negate function. In binary, subtracting a negative binary number from a positive one is obtained by inverting all the bits and adding 1. This is implemented in the following code block:

// Bitwise: Add function
function BitwiseAdd(a, b) {
    while (b != 0) {
        var carry = (a & b);
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Bitwise: Negate function
function BitwiseNegate(a) {
    return BitwiseAdd(~a, 1);
}

// Negating A Positive Number Gives Back A Negative Number:
// Uncomment it: console.log(BitwiseNegate(5)); // Print: "-5"

// Negating A Negative Number Gives Back A Positive Number:
// Uncomment it: console.log(BitwiseNegate(-5)); // Print: "5"

// Negation With Itself Gives Back The Original:
// Uncomment it: console.log(BitwiseNegate(BitwiseNegate(5))); // Print: "5"

// Bitwise: Substract function
function BitwiseSubstract(a, b) {
    return BitwiseAdd(a, BitwiseNegate(b));
}

console.log(BitwiseSubstract(9, 5)); // Print: "4"
// Uncomment it: console.log(BitwiseSubstract(5, 9)); // Print: "-4"
Enter fullscreen mode Exit fullscreen mode
// Bitwise: Add function function BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a; } // Bitwise: Negate function function BitwiseNegate(a) { return BitwiseAdd(~a, 1); } // Negating A Positive Number Gives Back A Negative Number: // Uncomment it: console.log(BitwiseNegate(5)); // Print: "-5" // Negating A Negative Number Gives Back A Positive Number: // Uncomment it: console.log(BitwiseNegate(-5)); // Print: "5" // Negation With Itself Gives Back The Original: // Uncomment it: console.log(BitwiseNegate(BitwiseNegate(5))); // Print: "5" // Bitwise: Substract function function BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b)); } BitwiseSubstract(9, 5); // Print: "4" // Uncomment it: console.log(BitwiseSubstract(5, 9)); // Print: "-4"

Multiplication(9๏ธโƒฃโœ–๏ธ5๏ธโƒฃ)

The following code block illustrates multiplication using bitwise operator, and it also handles negative numbers:

// Bitwise: Add function
function BitwiseAdd(a, b) {
    while (b != 0) {
        var carry = (a & b);
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Bitwise: Negate function
function BitwiseNegate(a) {
    return BitwiseAdd(~a, 1);
}

// Bitwise: Multiply function
function BitwiseMultiply(a, b) {
    var m = 1,
        c = 0;
    if (a < 0) {
        a = BitwiseNegate(a);
        b = BitwiseNegate(b);
    }
    while (a >= m && b) {
        if (a & m) {
            c = BitwiseAdd(b, c);
        }
        b = b << 1;
        m = m << 1;
    }
    return c;
}

console.log(BitwiseMultiply(9, 5)); // Print: "45"
Enter fullscreen mode Exit fullscreen mode
// Bitwise: Add function function BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a; } // Bitwise: Negate function function BitwiseNegate(a) { return BitwiseAdd(~a, 1); } // Bitwise: Multiply function function BitwiseMultiply(a, b) { var m = 1, c = 0; if (a < 0) { a = BitwiseNegate(a); b = BitwiseNegate(b); } while (a >= m && b) { if (a & m) { c = BitwiseAdd(b, c); } b = b << 1; m = m << 1; } return c; } BitwiseMultiply(9, 5); // Print: "45"

Division(9๏ธโƒฃโž—5๏ธโƒฃ)

Division can be thought of as the number of times you can subtract b from a, given a/b. For example, 4/2 = 2 because 4-2-2 = 0. Using this property, bitwise division can be implemented as follows:

// Bitwise: Add function
function BitwiseAdd(a, b) {
    while (b != 0) {
        var carry = (a & b);
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Bitwise: Negate function
function BitwiseNegate(a) {
    return BitwiseAdd(~a, 1);
}

// Bitwise: Substract function
function BitwiseSubstract(a, b) {
    return BitwiseAdd(a, BitwiseNegate(b));
}

// Bitwise: Divide Positive function
function BiwiseDividePositive(a, b) {
    var c = 0;
    if (b != 0) {
        while (a >= b) {
            a = BitwiseSubstract(a, b);
            c++;
        }
    }
    return c;
}

BiwiseDividePositive(9, 3); // Print: "3"
Enter fullscreen mode Exit fullscreen mode
// Bitwise: Add function function BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a; } // Bitwise: Negate function function BitwiseNegate(a) { return BitwiseAdd(~a, 1); } // Bitwise: Substract function function BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b)); } // Bitwise: Divide Positive function function BiwiseDividePositive(a, b) { var c = 0; if (b != 0) { while (a >= b) { a = BitwiseSubstract(a, b); c++; } } return c; } BiwiseDividePositive(9, 3); // Print: "3"

This is relatively simple for positive numbers. The while loop can keep subtracting, and a counter variable can store how many times b subtracted a. However, what about for negative numbers? -10/2 = -5, but we cannot subtract 2 from -10 because the while loop would go on forever. To avoid this, convert both the numbers into positive numbers. Doing this, we have to keep track of the sign:

a b Must Be
+ + +
+ - -
- + -
- - +

If negative is represented as 1 and positive as 0, this is the same truth table as an XOR table:

a b Must Be
0 0 0
0 1 1
1 0 1
1 1 0

The division algorithm is shown next. This function subtracts b from a until it is zero. Again, negative numbers have to be handled appropriately at the end with a negation helper function:

// Bitwise: Add function
function BitwiseAdd(a, b) {
    while (b != 0) {
        var carry = (a & b);
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Bitwise: Negate function
function BitwiseNegate(a) {
    return BitwiseAdd(~a, 1);
}

// Bitwise: Substract function
function BitwiseSubstract(a, b) {
    return BitwiseAdd(a, BitwiseNegate(b));
}

// Bitwise: Divide Positive function
function BiwiseDivide(a, b) {
    var c = 0,
        isNegative = 0;
    if (a < 0) {
        a = BitwiseNegate(a); // Convert to Positive
        isNegative = !isNegative;
    }
    if (b < 0) {
        b = BitwiseNegate(b) // Convert to Positive
        isNegative = !isNegative
    }
    if (b != 0) {
        while (a >= b) {
            a = BitwiseSubstract(a, b);
            c++;
        }
    }
    if (isNegative) {
        c = BitwiseNegate(c);
    }
    return c;
}

BiwiseDivide(9, 3); // Print: "3"
BiwiseDivide(-9, 3); // Print: "-3"
Enter fullscreen mode Exit fullscreen mode
// Bitwise: Add function function BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a; } // Bitwise: Negate function function BitwiseNegate(a) { return BitwiseAdd(~a, 1); } // Bitwise: Substract function function BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b)); } // Bitwise: Divide Positive function function BiwiseDivide(a, b) { var c = 0, isNegative = 0; if (a < 0) { a = BitwiseNegate(a); // Convert to Positive isNegative = !isNegative; } if (b < 0) { b = BitwiseNegate(b) // Convert to Positive isNegative = !isNegative } if (b != 0) { while (a >= b) { a = BitwiseSubstract(a, b); c++; } } if (isNegative) { c = BitwiseNegate(c); } return c; } console.log(BiwiseDivide(9, 3)); // Print: "3" BiwiseDivide(-9, 3); // Print: "-3"

Practical Use #2: In Development (๐Ÿ”ข๐Ÿ”ข)

Alt text

There are a couple of ways to use bitwise operators to speed up your JavaScript. The first is to use bitwise operations instead of pure mathematical operations. For example, you may have tried this code:

for (var i = 0, len = rows.length; i < len; i++) {
    if (i % 2) {
        // Even
    } else {
        // Odd
    }
}
Enter fullscreen mode Exit fullscreen mode

This can easily be determined by using a bitwise AND operation on a given number. When the number is even, the result of bitwise AND 1 is 0; when the number is odd, the result of bitwise AND 1 is 1:

for (var i = 0, len = rows.length; i < len; i++) {
    if (i & 2) {
        // Even
    } else {
        // Odd
    }
}
Enter fullscreen mode Exit fullscreen mode

Although the code change is small, this code is faster compared to the first.

The second way to use bitwise operators is a technique known as a bitmask (See on Wikipedia). Bitmasking is a popular technique in computer science when there are a number of Boolean options that may be present at the same time. For example:

var OPTION_A = 1;
var OPTION_B = 2;
var OPTION_C = 4;
var OPTION_D = 8;
var OPTION_E = 16;
Enter fullscreen mode Exit fullscreen mode

With the options defined, you can create a single number that contains multiple settings using the bitwise OR operator:

var options = OPTION_A | OPTION_C | OPTION_D;
Enter fullscreen mode Exit fullscreen mode

You can then check whether a given option is available by using the bitwise AND operator. The operation returns 0 if the option isnโ€™t set and 1 if the option is set:

// is option A in the list?
if (options & OPTION_A) {
    // do something
}

// is option B in the list?
if (options & OPTION_B) {
    // do something
}
Enter fullscreen mode Exit fullscreen mode

Bitmask operations such as this are very quick since the function takes place at a lower level of the framework, as described earlier. Bitmasks will help to speed up the overall method if there are a variety of choices that are always stored and reviewed together.

Summary (๐Ÿ“š๐Ÿ“š)

Alt text

Part 20 covered the basics of bit manipulation in JavaScript. Bit manipulation is used for high-performance numerical operations. Using bitwise operators is much faster than using the native methods in the Math class.

With JavaScript advancing into server-side programming, more efficient code is needed. To consolidate the concepts from this chapter, Table 20-1 summarizes bitwise operators and their usage:

Operator Operation Use Case
& AND 1 when both bits are 1
| OR 1 when either bit is 1
โˆผ NOT Inverts all the bits
^ XOR 1 when only one of the bits is 1
<< Left shift Shifts to the left, and any excess bits are shifted off
>> Right shift Shifts to the right, and any excess bits are shifted off
>>> Zero-fill right shift Shifts to the right, and any excess bits are shifted off and the sign bit comes 0

Ending Message (๐Ÿ˜„๐Ÿ‘‹)

Like I said, I was motivated to blog about data structures and algorithms in JavaScript because very few people do it in general, and I thought it was an opportunity to share as much as I could, at first, I thought no one will read my blog, I'm just here because of the pandemic, I'm at home, and I thought writing online was another idea I could try.

My advice as you read the blog, think about where they apply, think about the objects, things in the world that you can put in the code, think about the things that move the world, the winds, the sunshine, the appearance of moon, moving vehicles, flying planes, flowing waters, flying birds, swimming fish, and more

In bioinformatics, mathematics, economics, dynamic programming is generally used. For example, with the assistance of dynamic programming, tasks such as sequence alignment, protein folding, RNA structure estimation and protein-DNA binding are conducted in bioinformatics. It is used in mathematics in matrix multiplication and matrix multiplication has very large applications, such as in Rocket science, where the rocket path is calculated by solving too many parameters.

Do you have any idea where data structures and algorithms can be applied in real life? How effective? I'd be very thankful if you'd help it spread by emailing it to a friend or posting it on Twitter or Facebook if you liked this message. And Oh, thank you!

Next week I'll talk about how to speed up your application as a JavaScript Developer. I also want to write a blog about web development and react development. Finally, I also want to write a blog in other programming languages โ€‹โ€‹like python, Java, C, and C++ that focus on concept and practice.

Alt Text

Discussion

pic
Editor guide
Collapse
dephraiim profile image
Ephraim Atta-Duncan

Wow, this is amazing.

Collapse
edisonnpebojot profile image
Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Author

Thanks @dephraiim ! โค๏ธโค๏ธ

Collapse
uds5501 profile image
Uddeshya Singh

One suggestion, how about solving related problems on Leetcode and linking the question to the relevant tutorial blog? It will give users recommended practice material imo.

Collapse
edisonnpebojot profile image