집 > 기사 > 웹 프론트엔드 > 자바스크립트 데이터 구조 및 알고리즘에 대한 자세한 설명

자바스크립트 데이터 구조 및 알고리즘에 대한 자세한 설명

小云云원래의: 2018-02-23 15:31:342080검색

정수를 입력받아 숫자의 이진수 표현으로 표현되는 1의 개수를 출력하는 함수를 구현해주세요. 예를 들어 9를 이진수로 1001로 표현하면 2비트는 1이다. 따라서 9를 입력하면 함수는 2를 출력합니다. 우선, 이진수 1의 해법을 위해 여기서 가장 생각해야 할 것은 비트 연산에 관한 몇몇 연산자들이다. 총 5가지 연산이 있습니다. 즉, AND(&), OR(|), XOR(^), 오른쪽 시프트(>>), 왼쪽 시프트(<<)입니다.

무한 루프를 일으킬 수 있는 첫 번째 해결 방법:
아이디어 1: 먼저 주어진 정수를 판단하여 이 숫자의 가장 오른쪽 부분이 1인지 판단하세요. 1이면 카운터를 하나 주고 1을 더합니다. 그런 다음 입력된 정수를 오른쪽으로 1비트 이동하고 정수가 0이 될 때까지 계속 이동한 후 카운터를 출력합니다.

function NumberOf1(n)
{
  let count = 0;
  while(n) {
    if(n & 1) {
      count ++;
    }
    n = n >> 1;
  }
  return count;
}
console.log(NumberOf1(9));</p>
<p>이 알고리즘은 부호 없는 숫자에는 문제가 없지만 부호 있는 숫자에는 큰 문제가 되고 무한 루프가 발생할 가능성이 매우 높습니다. n이 음수인 경우 n은 오른쪽으로 이동하고 가장 높은 비트에 1이 추가되므로(데이터가 음수인지 확인하기 위해) 결국 무한 루프가 형성됩니다. 예를 들어 0x80000000 이 때 문제가 발생하게 되는데 한 자리 오른쪽으로 이동하면 0xC0000000이 됩니다. 음수 이동이기 때문에 이동된 숫자가 음수인지 확인해야 합니다. 따라서 가장 높은 비트는 항상 1이 됩니다. 즉, 결국 이 숫자는 항상 끝없이 반복됩니다. </p>
<p>아이디어 2: 1을 이동하려면 먼저 가장 낮은 비트가 1인지 확인한 다음 1을 2로 이동하세요. 그런 다음 이를 정수 비율과 비교하여 끝에서 두 번째 숫자가 1인지 확인합니다. . . 이런 식으로 결국 효과를 얻을 수 있고, 모두 1의 개수를 얻을 수 있다. </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));

마지막으로 가장 좋은 방법을 제공합니다.

아이디어 3: 정수에서 1을 뺀 다음 원래 정수로 AND 연산을 수행하면 정수의 가장 오른쪽 1이 0으로 바뀌고 1 뒤의 모든 0이 1로 바뀝니다. 그런 다음 정수의 이진법에 1이 있는 만큼 이 작업을 여러 번 수행할 수 있습니다. 마지막으로 카운터를 사용하여 작업 횟수를 결정하고 카운터를 출력하면 됩니다.

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

자바스크립트 데이터 구조 및 알고리즘에 대한 자세한 설명

관련 기사