Detailed explanation of javascript data structure and algorithm

Please implement a function that inputs an integer and outputs the number of 1s represented by the binary representation of the number. For example, if 9 is expressed as 1001 in binary, 2 bits are 1. So if you enter 9, the function outputs 2. First of all, for the solution of binary 1, what we should think of most here are some operators about bit operations. There are five operations in total, namely: AND (&), OR (|), XOR (^), right shift (>>), and left shift (<<).

The first solution that may cause an infinite loop:
Idea 1: First judge the integer you gave, whether the rightmost part of this number is 1. If it is 1, give a counter and add 1 to it. Then shift the input integer to the right by one bit, and keep shifting until the integer becomes 0, and then output the counter.

function NumberOf1(n)
{
  let count = 0;
  while(n) {
    if(n & 1) {
      count ++;
    }
    n = n >> 1;
  }
  return count;
}
console.log(NumberOf1(9));</p>
<p>This algorithm has no problem for unsigned numbers, but it is a big problem for signed numbers, and it is very likely to cause an infinite loop. When n is a negative number, n is shifted right and 1 is added to the highest bit (to ensure that the data is negative), so an infinite loop will eventually form. For example: 0x80000000, a problem will occur at this time. When shifted one position to the right, it becomes 0xC0000000. Because it is a shift of a negative number, it must be ensured that the shifted number is a negative number, so the highest bit will always be 1, which means that in the end this number will always loop endlessly. </p>
<p>Idea 2: Move 1, first determine whether the lowest bit is 1, and then move 1 to 2. Then compare it with the integer ratio to determine whether the penultimate digit is 1, and so on. . . In this way, an effect can be achieved in the end, and the number of all 1's can be obtained. </p>
<pre class="brush:php;toolbar:false">function NumberOf1(n) {

  let count = 0;
  let flag = 1;
  while(flag) {
    if(n & flag) {
      count ++;
    }
    flag = flag << 1;
  }
  return count;
}
console.log(NumberOf1(9));

Finally, we provide the best method.

Idea 3: Subtract 1 from an integer, and then perform an AND operation with the original integer. The 1 on the rightmost side of the integer will be turned into 0, and all the 0s after the 1 will be turned into 1. Then, as many 1's as there are in the binary system of an integer, this operation can be performed as many times as possible. Finally, the counter is used to determine the number of operations and the counter is output.

//更好的解法
function NumberOf1(n) {
  let count = 0;
  while(n) {
    count ++;
    n = (n-1) & n;
  }
  return count;
}
console.log(NumberOf1(9));

Related recommendations:

Data structure in PHP: Detailed explanation of DS extension

Sequential linked list and sequence of php data structure Linked linear table example

JavaScript data structure singly linked list and circular linked list example sharing

The above is the detailed content of Detailed explanation of javascript data structure and algorithm. For more information, please follow other related articles on the PHP Chinese website!