1 비트 수

난이도 쉽게
자주 묻는 질문 어도비 벽돌 상자 시스코 Facebook 퀄컴
비트 비트 조작 비트조회수 132

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

우리는 모두 해밍 무게 이진수의. 해밍 가중치는 이진수로 설정된 비트 / 1 초의 수입니다. 이 문제에서 1 비트 수 주어진 해밍 가중치를 찾아야합니다. 번호.

숫자 = 3

이진 표현 = 011

해밍 가중치 = 2

숫자 = 4

이진 표현 = 100

해밍 가중치 = 1

몇 가지 이미지 표현이 더 많은 도움이 될 것입니다.

1 비트 수

이제 그것을 찾는 방법을 살펴 보겠습니다.

접근 – 1A

브 루트 포스

무차별 대입 접근 방식은

  • n % 2를 찾아 해당 위치에서 비트를 제공합니다.
  • n = n / 2를 계산하여 다음 비트로 이동

숫자 = 5

1 비트 수

코드를 살펴 보겠습니다.

JAVA 프로그램 

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         ans=ans+(n%2);
         n=n/2;
     }
     return ans; 
    }
};

C ++ 프로그램

public class Solution { 
       // you need to treat n as an unsigned value 
       public int hammingWeight(int n) 
       { 
           int ans=0; 
           while(n!=0) 
           { 
               ans=ans+(n%2); 
               n=n/2; 
           } 
           return and; 
      } 
}

시간 복잡도 = O (n)

접근 방식 – 1B

무차별 대입이지만 더 똑똑해!

이제 우리는 간단한 접근 방식을 가지고 있습니다. 비트 조작에 대해 자세히 살펴 보겠습니다.

먼저 몇 가지 스마트 포인트로 게임 강화

  • 허용되는 정수는 최대 32 비트 길이가 될 수 있습니다.
  • a&1=1 1&0=0

이러한 것들을 유지하면 32 개를 반복하고 AND 연산을 수행하여 설정된 비트를 찾을 수 있습니다.

1 비트 수를위한 JAVA 프로그램

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;
    }
}

1 비트 수를위한 C ++ 프로그램

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;    
    }
};

시간 복잡도 = O (n)

지금까지 수집 한 많은 접근 방식은 선형입니다. 우리는 게임을 최적화하기 위해 분명히 한두 가지 똑똑한 것을 우리 고양이에 가져야합니다. 그래서, 나는 금을 발견했습니다.

접근 – 2

Brian Kernighan 알고리즘

모든 지식과 알고리즘을 익히기 전에 프로세스를 설명하겠습니다.

  • n-1을 계산합니다.
  • 우리와 그것은 n 즉 n & (n-1)
    • 따라서 가장 오른쪽 비트 설정 해제
  • 0이 될 때까지 위의 단계를 계속 반복하십시오.

number = 5하자

이진 표현 = 101

num = 5에 대해 설명 된 프로세스
num = 5에 대해 설명 된 프로세스

최적화

  • 알고리즘은 설정된 비트 수만큼 반복됩니다.

코드 살펴보기

1 비트 수를위한 Java 프로그램

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
}

1 비트 수를위한 C ++ 프로그램

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
};

시간 복잡성 분석

각 정수에는 log (n) 비트가 있으며 최악의 경우 모든 비트를 통과합니다.

시간 복잡도 = Log (n)

이제 우리는 O (1)을 취하는 접근 방식을 어떻게 놓칠 수 있는지 속도를 높이고 있습니다.

도입

접근 – 3

고급 작업 사용

이진수가 11010011이라고 가정하겠습니다.

여기서는 비트 마스크 즉 0101,0011,00001111,00000000011111111 및 000000000000000001111111111111111을 사용하여 그림에 표시된 절차를 수행합니다.

 

Bitmask를 사용하여 해밍 가중치 계산
Bitmask를 사용하여 해밍 가중치 계산

1 비트 수를위한 JAVA 프로그램

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    n = (n & 0x55555555) + (n >>  1 & 0x55555555); // put count of each  2 bits into those  2 bits 
    n = (n & 0x33333333) + (n >>  2 & 0x33333333); // put count of each  4 bits into those  4 bits 
    n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F); // put count of each  8 bits into those  8 bits 
    n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits 
    n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits 
    return n;
    }
}

위의 접근 방식의 시간 복잡도와 공간 복잡도는 모두 O (1)로 끝납니다.

바이너리 이상을 알고 싶습니다. 튜닝!

참조

균열 시스템 설계 인터뷰
Translate »