2의 거듭제곱, Google 인터뷰 질문 해결. 비트를 가지고 놀기.

질문: 정수가 주어지면 2의 거듭제곱인지 결정하는 함수를 작성하십시오. (범위: 1 - 2^31-1)

예: 입력: 16, 출력: 2^4 = 16이므로 참입니다.
입력 : 18, 출력 : 거짓.

브루트 포스

따라서 명백한 무차별 접근 방식은 2를 나누고 1에 도달하는지 확인하는 것입니다.

var powerOftwo = function(n){
    if(n<=0) return false;
    while(n%2 == 0) n = n/2;
    return n == 1;
}

Percompute 및 Use Set

범위가 0 - 2^31-1 사이에 있기 때문에 이를 사용하여 다양한 가능한 출력을 미리 계산하고 세트에 저장하고 교차 검사할 수 있습니다.

  let set = new Set();

  for(let i=0;i<31;i++){
    set.add(Math.pow(2,i));
  }

  console.log(set);

  var powerOfTwo = function(n){
    if(set.has(n)) return true;
    return false;
  }

이제 우리가 성취하고자 하는 것이 무엇인지 알았으니 Google이 우리에게 무엇을 기대하는지 생각해 봅시다.

팁 : 내가 알아차린 일반적인 패턴 중 하나는 회사에서 이해하기 쉽고 구현하기 쉬운 질문을 할 때마다 그 질문이 비트 조작과 관련이 있어야 한다는 것입니다.

그렇다면 어떻게 2의 거듭제곱과 비트를 연관시킬 수 있을까요?

아시다시피 컴퓨터의 경우 모든 것은 숫자를 포함하여 0과 1의 조합으로 귀결됩니다. 따라서 n=0에서 31까지 2^n을 나타내는 숫자가 비트 형식으로 어떻게 표현되는지 살펴보겠습니다.



따라서 여기서 일반적인 패턴은 2의 거듭제곱인 숫자는 1비트만 1로 설정되고 나머지는 0이라는 것입니다.

그래서 우리는 이것을 우리의 이점에 어떻게 사용합니까? 어떤 작업을 수행해야 하는지 살펴보겠습니다.

   &: and operator          1&1 = 1, 0 & anything = 0
   |: or  operator          0&0 = 0, 1 & anything = 1
   ^: xor operator          x^x = 0, x^n = 1
   ~: negate                ~1 = 0 | ~0 = 1

팁: 질문이 비트 조작에 관한 것이라면 먼저 & 및 ^ 연산자를 사용하여 해결해 보십시오.

& 연산자로 해결해 봅시다. 그러나 우리는 무엇을 해야 합니까?

숫자를 생성해 보겠습니다. 숫자가 홀수이면 +1/-1은 짝수를 생성하고 그 반대도 마찬가지입니다.

이제 우리는 "&"연산자와 2개의 숫자를 가지고 있습니다.

   even number : 6  = 110 
            +1 : 7  = 111
            -1 : 5  = 101

   6&7 = 6   6&5 = 4

   multiple of 2 : 16 = 10000
              +1 : 17 = 10001
              -1 : 15 = 01111

   16&17 = 16  16&15 = 0

여기에 우리의 해결책이 있습니다. 16&15는 0이 됩니다. 이전에 입증된 바와 같이 숫자가 2의 거듭제곱이면 1비트만 설정되므로 n-1은 현재 위치에서 모든 이전 비트를 1로 설정합니다.

예:

   8 : 1000       7: 0111      8&7 = 0
   16: 10000     15: 01111    16&15 = 0 
   32: 100000    31: 011111   32&31 = 0

그러나 동시에 홀수를 사용하면

예:

   17: 10001     16: 10000     17&16 = 16

이것으로부터 n이 2의 거듭제곱이면 n&(n-1) = 0이라고 말할 수 있습니다.

이로 인해 우리의 코드는 다음과 같이 요약됩니다.

   var powerOfTwo = function(n){
    n = n&(n-1);
    return n == 0;
   }

놀랍지 않나요? 얼마나 적은 비트 조작이 그러한 과감한 결과를 초래하고 더 간결하고 읽기 쉬운 코드로 이끄는가.

비슷한 것을 연습하고 싶다면 다음을 해결하십시오.

질문: 주어진 숫자의 이진 표현에서 1의 수를 세십시오.

이 질문에 대한 해결책을 댓글로 남겨주세요 :)

내가 어딘가에 엉망이 된 경우 아래에 내 설명 댓글이 마음에 들었기를 바랍니다.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/powerOfTwo.js