Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
October 3, 2020 12:53 am GMT

Learn Data Structure and Algorithm in JavaScript | Part 20



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 objects 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 (). Lets 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, lets 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 (00)

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(10)

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"
// 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(10)

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"
// 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(11)

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"
// 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(10)

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"
// 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(10)

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 1var 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)
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 1var 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}\rparenx(2y)

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

Right Shift(10)

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 1var 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)
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 1var 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)
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(95)

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)
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(95)

Subtraction is the difference of two numbers. However, you can also think of it as adding a negative number. Heres an example: 54=5+(4)5 - 4 = 5 + (-4)54=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 functionfunction BitwiseAdd(a, b) {    while (b != 0) {        var carry = (a & b);        a = a ^ b;        b = carry << 1;    }    return a;}// Bitwise: Negate functionfunction 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 functionfunction BitwiseSubstract(a, b) {    return BitwiseAdd(a, BitwiseNegate(b));}console.log(BitwiseSubstract(9, 5)); // Print: "4"// Uncomment it: console.log(BitwiseSubstract(5, 9)); // Print: "-4"
// Bitwise: Add functionfunction BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a;}// Bitwise: Negate functionfunction 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 functionfunction BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b));}BitwiseSubstract(9, 5); // Print: "4"// Uncomment it: console.log(BitwiseSubstract(5, 9)); // Print: "-4"

Multiplication(95)

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

// Bitwise: Add functionfunction BitwiseAdd(a, b) {    while (b != 0) {        var carry = (a & b);        a = a ^ b;        b = carry << 1;    }    return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) {    return BitwiseAdd(~a, 1);}// Bitwise: Multiply functionfunction 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"
// Bitwise: Add functionfunction BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) { return BitwiseAdd(~a, 1);}// Bitwise: Multiply functionfunction 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(95)

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 functionfunction BitwiseAdd(a, b) {    while (b != 0) {        var carry = (a & b);        a = a ^ b;        b = carry << 1;    }    return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) {    return BitwiseAdd(~a, 1);}// Bitwise: Substract functionfunction BitwiseSubstract(a, b) {    return BitwiseAdd(a, BitwiseNegate(b));}// Bitwise: Divide Positive functionfunction BiwiseDividePositive(a, b) {    var c = 0;    if (b != 0) {        while (a >= b) {            a = BitwiseSubstract(a, b);            c++;        }    }    return c;}BiwiseDividePositive(9, 3); // Print: "3"
// Bitwise: Add functionfunction BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) { return BitwiseAdd(~a, 1);}// Bitwise: Substract functionfunction BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b));}// Bitwise: Divide Positive functionfunction 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 functionfunction BitwiseAdd(a, b) {    while (b != 0) {        var carry = (a & b);        a = a ^ b;        b = carry << 1;    }    return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) {    return BitwiseAdd(~a, 1);}// Bitwise: Substract functionfunction BitwiseSubstract(a, b) {    return BitwiseAdd(a, BitwiseNegate(b));}// Bitwise: Divide Positive functionfunction 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"
// Bitwise: Add functionfunction BitwiseAdd(a, b) { while (b != 0) { var carry = (a & b); a = a ^ b; b = carry << 1; } return a;}// Bitwise: Negate functionfunction BitwiseNegate(a) { return BitwiseAdd(~a, 1);}// Bitwise: Substract functionfunction BitwiseSubstract(a, b) { return BitwiseAdd(a, BitwiseNegate(b));}// Bitwise: Divide Positive functionfunction 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    }}

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    }}

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;

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;

You can then check whether a given option is available by using the bitwise AND operator. The operation returns 0 if the option isnt 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}

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 thesign 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


Original Link: https://dev.to/edisonnpebojot/learn-data-structure-and-algorithm-in-javascript-part-20-45pb

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To