c 서명되지 않은 숯의 '1'비트 수를 계산하는 C 코드

StackOverflow https://stackoverflow.com/questions/697978

  •  22-08-2019
  •  | 
  •  

문제

C의 서명되지 않은 숯으로 1의 수를 반환하려면 C 코드가 필요합니다. 명백하지 않은 경우 왜 작동하는지에 대한 설명이 필요합니다. 나는 32 비트 번호에 대한 많은 코드를 찾았지만 서명되지 않은 숯은 그리 많지 않았습니다.

도움이 되었습니까?

해결책

서명되지 않은 문자에 대해 동일한 코드가 작동합니다. 테스트하는 모든 비트를 루프하십시오. 보다 이것.

다른 팁

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

0에서 15까지의 비트 수를 아는 배열이 있습니다. 각 니블의 결과를 추가하십시오.

해킹 이 알고리즘은 3 개의 작업에 있습니다 (대략 C로 변환) :

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

(ULL 64 비트 산술을 강요하는 것입니다. 간신히 ...이 계산에는 33 비트 정수가 필요합니다.)

실제로, 두 번째 상수를 다음으로 교체 할 수 있습니다 042104210021ULL, 당신은 8 비트 만 계산하기 때문에, 그것은 멋지게 대칭적인 것처럼 보이지 않습니다.

이것은 어떻게 작동합니까? 에 대해 생각하다 c 비트와 함께 기억하십시오 (a + b) % c = (a % c + b % c) % c, 그리고 (a | b) == a + b IFF (a & b) == 0.

  (c * 01001001001ULL & 042104210421ULL) % 017
  01   01001001001                01         1
  02   02002002002       02000000000         1
  04   04004004004          04000000         1
 010  010010010010            010000         1
 020  020020020020               020         1
 040  040040040040      040000000000         1  # 040000000000 == 2 ** 32
0100 0100100100100        0100000000         1
0200 0200200200200           0200000         1

64 비트 산술이 없으면 분할 할 수 있습니다. c 9 개의 작업을 수행하여 니블에 들어가서 각 절반을 수행합니다. 이것은 13 비트 만 있으면되므로 16 또는 32 비트 산술을 사용하면 작동합니다.

bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;

(c * 0421 & 01111) % 7
 1   0421      01    1
 2  01042   01000    1
 4  02104    0100    1
 8  04210     010    1

예를 들어, if c == 105 == 0b11001001,

c == 0100
   |  040
   |  010
   |   01 == 0151
* 01001001001001ULL == 0100100100100
                     |  040040040040
                     |  010010010010
                     |   01001001001 == 0151151151151
& 0421042104210421ULL ==  0100000000
                       | 04000000000
                       |      010000
                       |          01 ==   04100010001
% 017                                == 4

c & 017      ==            8 | 1           ==                   011
011 * 0421   ==     8 * 0421 | 1 * 0421    == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 ==   010 | 01   ==   011
011 % 7      == 2

c >> 4       ==            4 | 2            ==                     06
06 * 0421    ==     4 * 0421 | 2 * 0421     == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 ==  0100 | 01000 == 01100
01100 % 7    == 2

2 + 2 == 4

비트 Twiddling Hacks 페이지를 참조하십시오. http://graphics.stanford.edu/~sander/bithacks.html#countbitssetkernighan

이것에 대한 많은 좋은 해결책이 있습니다.

또한 가장 간단한 구현 에서이 기능은 상당히 사소합니다. 시간을 내어이 작업을 수행하는 방법을 배워야합니다.

서명되지 않은 숯만큼 작은 정수의 경우 작은 조회 테이블을 사용하여 최고의 성능을 얻습니다.

나는 당신이 언급하고있는 인구 계산 알고리즘을 알고 있습니다. 그들은 레지스터에 저장된 정수보다 작은 여러 단어의 산술을 수행하여 작동합니다.

이 기술은 Swar라고합니다.http://en.wikipedia.org/wiki/swar).

자세한 내용은 해커 선거 웹 사이트 (www.hackersdelight.org)를 확인하십시오. 그는 예제 코드를 가지고 있으며 이러한 트릭을 자세히 설명하는 책을 썼습니다.

이미 대답 한 바와 같이, 비트를 계산하는 표준 방법은 서명되지 않은 숯에서도 작동합니다.

예시:

    unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
    if ( value & 1 == 1 ) 
        bitCount++;
    value >>= 1;
}

부호없는 숯은 32 비트 플로트 또는 정수가 "숫자"인 것과 같은 방식으로 "숫자"입니다. 컴파일러가 표현하는 것으로 간주되는 것은 변경 사항입니다.

숯을 비트로 묘사하면 :

01010011 (8 비트);

다음을 수행하여 세트 비트를 계산할 수 있습니다.

값을 취하고 X라고 말하고 X % 2를 가져 가십시오. 나머지는 1 또는 0입니다. 나머지를 별도의 변수로 축적하십시오 (이것은 세트 비트의 결과 수입니다).

그런 다음 >> (오른쪽 시프트) 1 비트.

8 비트가 이동 될 때까지 반복하십시오.

C 코드는 내 의사 코드에서 구현하기가 매우 간단하지만 기본적으로

public static int CountSetBits(char c)
{
    int x = 0;
    int setBits = 0;
    while (x < 7)
    {
       setBits = setBits + c % 2;
       c = c >> 1;
       x = x + 1;
    }
}

Ephemient의 게시물을 기반으로, 우리는 No Branched 8 비트 버전이 있습니다. 그것은 16 진수 표현입니다.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

두 번 적용하면 9 개의 작업이 필요한 16 비트 버전이 있습니다.

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

여기에 64BITS 레지스터와 11 개의 작업이 필요한 변형 16BITS 버전을 작성합니다. 이전 것보다 낫지는 않지만 1 모듈로 작동 만 사용합니다.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top