2진법 중 1에 대한 문제 해법 총결

3460 단어
질문:
한 바이트 (8자리) 의 무기호 정형 변수에 대해 2진법 중 1의 개수를 구하십시오.
분석:
법1:
(n%2)==1은 2진수 n의 최저 위치가 1이고,count로 기록하면 다음 n은 반으로 줄어든다.
n/=2; (예를 들어 11101001에서 01110100으로 변경)
그래서 가장 기초적인 코드는 다음과 같다.
int GetAnswer1(unsigned char data)
{
    int count = 0;
    while (data)
    {
        if ((data % 2) == 1)
        {
            count++;
        }
        data /= 2;
    }
    return count;
}

법2:
비트 작업:
int GetAnswer2(unsigned char data)
{
    int count = 0;
    while (data)
    {
        count+=(data& 0x01);
        data >>= 1;
    }
    return count;
}

법3:
예를 들어 01011101, 목표가 1이므로 1만 판단한다.
코드:
int GetAnswer3(unsigned char data)
{
    int count = 0;
    while (data)
    {
        data&=(data-1);
    }
    return count;
}

법3에 대해 상세하게 분석해 보자.
핵심 코드는 데이터 & = (data-1)이다.
예를 들면 다음과 같습니다.
data=1101 1101
data-1=
  1101 1101 
- 0000 0001
=1101  1100
& 1101 1101
= 1101 1100
첫 번째 결과: 맨 오른쪽부터 세면 딱 최저가 1이기 때문에 0을 제거하고 이 자리의 이전 위치는 변하지 않는다(즉 빨간색 부분).
계속:
data-1=
  1101 1100
- 0000 0001
=1101 1011
&1101 1100
=1101 1000
오른쪽에서 왼쪽으로 0을 만난 사람은 모두 1로 변하고 1을 만났을 때까지 0을 제거한다.
같은 1 앞자리는 변하지 않는다.
다음 같은 조작...
그래서 1이 몇 개면 데이터 & = (data-1)을 몇 번 실행합니다.
 
법4:
공간으로 시간을 바꾸고 256 크기의 수조로 모든 답안을 저장하면 검색할 때 바로 O(1)의 시간을 얻을 수 있다.
 
제목 확장:
첫 번째 문제: 두 개의 정수(이진법으로 표시) A와 B를 정하고 A를 B로 바꾸려면 몇 자리를 바꿔야 합니까?
1단계: unsigned int x=A^B;(이 또는 조작, 위치는 0이고 다른 것은 1).
두 번째 단계: x 중 1의 개수를 판단한다.
 
두 번째 문제:
한 문장으로 하나의 정수가 2의 정수 차방인지 아닌지를 판단하다.
분석:
그의 2진법은 단지 1이다. 그러면 2의 정수 차원이다.
그래서: 데이터 & = (data-1);
오른쪽에서 왼쪽으로 첫 번째 하나를 만나다.
마지막으로 데이터가 0인지 아닌지를 판단합니다.
 
 
 
 
 
 
vim에서 vim rails 명령을 인식할 수 없습니다.
[Unity] 혼돈의 연성 시계추를 굴려 보는 슬픔.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage