비트 계산

난이도 중급
자주 묻는 질문 아마존 Apple
비트 조작 비트 동적 프로그래밍조회수 30

카운트 비트에 관한 모든 것!

인간은 자신이 만든 컴퓨터와 통신하는 데 문제가 있습니다.

이유는 무엇입니까?

인간은 수년에 걸쳐 말하고 듣게 된 언어를 말하고 이해하지만 가난한 컴퓨터 0과 1을 가르쳤습니다.

그래서 오늘은 우리 컴퓨터에 숫자를 세다 우리의 문제 진술인 숫자에서 1 중 XNUMX의 숫자입니다 (for Counting Bits).

주어진 : 모든 양의 정수가 될 수있는 정수 숫자

우리는 무엇을해야 하는가?

1에서 num까지 각 숫자에서 XNUMX의 수를 찾으십시오. 한 줄에 답을 인쇄하십시오.

접근 비트 계산에 간단한 비트 조작 사용

세부 사항에 들어가기 전에 몇 가지 비트 작업을 살펴 ​​보겠습니다.

">>" 이것은 오른쪽 시프트 연산자를 나타냅니다.

"&"    이것은 AND 연산자를 나타냅니다.

이제 비트 계산으로 이동하기 전에 몇 가지 예를 참조하십시오.

a = 1001하자

a >> 1 = 100

a & 1 = 1

또한 숫자를 오른쪽으로 한 단위 이동할 때마다이를 XNUMX로 나눈다 고 말할 수 있습니다.

b = 100100 일 때

b >> 1 = 10010

이미 포함되어 있고 배열의 b / 2에 저장됩니다.

b & 1 = 0

이 작업은 마지막 비트가 1인지 0인지를 찾는 데 도움이됩니다.

c = 1

c >> 1 = 0

c & 1 = 1

따라서 모든 숫자 num에 대해 1의 수 = (num / 2) + (num & 1)에있는 XNUMX의 수

실시

비트 계산을위한 Java 프로그램

class Solution 
{
    public int[] countBits(int num) 
    {
    int a[]=new int[num+1];
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;
    }
}

비트 계산을위한 C ++ 프로그램

class Solution 
{
public:
    vector<int> countBits(int num) 
    {
    vector<int>a(num+1);
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;    
    }
};

8
13

복잡성 분석

위 접근법의 시간 복잡도 = O (n)

위 접근법의 공간 복잡도 = O (n) 여기서 n은 입력에서 우리에게 제공하는 값입니다.

참조

Translate »
1