2의 보수가있는 숫자에서 이진수를 찾는 것, C

Question

나는 이것이 약간 복잡 할 수도 있다고 생각한다. 우리는 long을 전달하고 숫자의 2 진 표현에 1의 수를 반환해야합니다. 네거티브의 경우 2의 보수를 반환합니다. 나는 긍정적 인 반응을 보였지만, 2의 보수는 약간 벗어났다. 이 작품을 만들기위한 조언을 주시면 감사하겠습니다.

unsigned int binaryOnesCounter(long n) { 


unsigned int oneCounter, negCounter; 
    int binaryStorage[63]; 
    int index, negFlag; 

    oneCounter = negFlag = index = 0; 


    int i; 
    for (i = 0; i < 63; ++i) 
    { 
    binaryStorage[i] = 0; 
    } 

    if(n < 0) { 
    if (n == -1){ 
     oneCounter = 63 + 1; 
    } else { 
     /* negate and add 1*/ 
     negFlag = 1; 
     n = (n * -1) + 1; 
    } 
    } 
    while (n>=1) { 
    if (n%2 == 1) { 
     oneCounter++; 
     binaryStorage[index] = 1; 
    } 
    else if (n%2 == 0) { 
     binaryStorage[index] = 0; 
    } 
    n = n/2; 
    } 


    if (negFlag == 1 && n != 1) { 
    negCounter = 64; 
    oneCounter = negCounter - oneCounter; 
    } 
    return oneCounter; 
} 

Answer 1

은이 overcomplicated된다

int countones(long long i) 
{ 
    int nOnes = 0; 
    unsigned long long *ptr = &i; 

    while (*ptr) 
    { 
     nOnes += *ptr & 1; 
     *ptr >>= 1; 
    } 
    return nOnes; 
} 

PS -4 62 개 것하지 63 여기 0b1111111111111111111111111111111111111111111111111111111111111100

좀 더 보편적 하나 (어떤 물체에 거의 카운트)이다 갖는다

int getbit(void *obj, size_t bit); 

size_t countBitsUniversal(void *obj, size_t osize) 
{ 
    size_t nOnes = 0, tmp = osize; 
    osize <<= 3; 

    if (osize && osize > tmp) 
    { 
     do 
     { 
      nOnes += getbit(obj, --osize); 

     } while (osize); 
    } 
    return nOnes; 
} 

int getbit(void *obj, size_t bit) 
{ 
    uint8_t *p = obj; 

    return !!(p[bit >> 3] & (1 << (bit & 7))); 
} 

__________ 
usage example 


double x; 
printf("%zu\n", countBitsUniversal(&x, sizeof(x))); 

long long arr[100]; 
printf("%zu\n", countBitsUniversal(arr, sizeof(arr))); 

Answer 2

고전적인 해결책 :

0 ( char, int, 또는 long) :

int countBits(unsigned long long x) 
{ 
    int count = 0; 
    while (x) 
    { 
     count++; 
     x = x & (x - 1); 
    } 
    return count; 
} 

Althought 내가 unsigned long long의 매개 변수를 복용으로 위의 선언, 서명 또는 정수 유형의 수를 수정할 수 있습니다.

Answer 3

하는 쉬운 방법은 비트 시프트 비트 마스크 연산을 사용하여 정확한 표현으로 n을 가지고하는 것 (즉, 단지 n 양의 값, 또는 음의 n들에 대한 2-보완에 대한).

음수 값을 2로 보완하는 시스템에서 작동하는 경우 (대부분 일반적인 시스템이 그렇듯이) n을 부호없는 값, 즉 unsigned long ul = n으로 볼 수 있습니다. 그런 다음 ul에는 음수가 2 음수 인 보조 문자 n이 포함됩니다. 다른 형태의 음의 값 (예를 들어, 하나의 보완 및 부호 비트)를 나타내는 시스템에서 작동하는 경우

, 당신은 당신의 자신의 2의 보수를 만들 수 :

unsigned int binaryOnesCounter(long n) { 

    unsigned long ul; 

    if (n < 0) { 
     ul = -n; 
     ul = (~ul) + 1; 
    } 
    else { 
     ul = -n; 
    } 

    int count=0; 
    while(ul) { 
     if (ul & 0x01) 
      count++; 

     ul >>= 1; 
    } 
    return count; 
} 

Answer 4

가 two's complement이 실제로 얼마나 고려 표현.

의 당신이 기능 value의 이진 표현에 사람들의 수를 반환

int bits_set_in_unsigned_long(unsigned long value); 

을 가정 해 봅시다.

우리는 음수가 아닌 입력을 해당 함수에 직접 제공 할 수 있습니다. 음성 입력을 위해, 우리는 (AN unsigned long에서) 자신의 2의 보수를 계산하고, 문제 정의에 따라, 그에 사람들의 수를 반환 :

int bits_set_in_long(long value) 
{ 
    if (value >= 0) 
     return bits_set_in_unsigned_long((unsigned long)value); 
    else 
     return bits_set_in_unsigned_long(~(ULONG_MAX - (unsigned long)value + 1UL) + 1UL); 
} 

당신은 ULONG_MAX에 대한 #include <limits.h>해야합니다.

위, 표현

~(ULONG_MAX - (unsigned long)value + 1UL) + 1UL 

는 unsigned long 2의 보수에 value (유형 long의) 변환합니다. 이것이 어떻게 성취되는지 정확히 봅시다.

2의 보수 표현의 경우 음수 값 value이 먼저 부호없는 long으로 필요합니다. 그러나 크기가 보다 작기 때문에 많은 아키텍처에서 -LONG_MIN == LONG_MIN이 발생합니다. 그러나이 시점에서 값이 음수라는 것을 알기 때문에 먼저 값을 캐스팅 한 다음 음수 값을 조정할 수 있습니다.

(unsigned long)value 캐스트 value에서 unsigned long 유형. 값이 두 유형 모두에서 표현 가능하면 값은 동일하게 유지됩니다. 그렇지 않으면 모듈로 산술 연산이 사용됩니다 (ISO C11, 6.3.1.3). 이 시점에서 value이 음수이므로 캐스트 값은 value + ULONG_MAX + 1UL입니다.

따라서 -value을 얻으려면 캐스팅 값을 ULONG_MAX + 1UL에서 뺍니다. ULONG_MAX과 은 상수이기 때문에 컴파일러는 먼저 이들을 더하고 그 다음에 형식을 오버플로한다고 불평 할 수 있습니다.이 형식은 unsigned long 형식이 모듈로 산술을 사용하기 때문에 형식을 오버플로한다고 불평합니다. 따라서 중간에 뺄셈을 넣으면 일부 C 컴파일러가 방출 할 수있는 경고가 표시되지 않습니다 (일부 C 컴파일러는 완벽하게 표준 C 코드 임에도 불구하고 그러한 구성이 일반적으로 부주의 한 오류라고 생각할 수 있기 때문입니다). value이 시점에서 네거티브이므로 말하면

는 (ULONG_MAX - (unsigned long)value + 1UL)는 unsigned long 같이 우리 value의 크기 (또는 절대 값)을 제공한다.

2의 보수 형식으로 변환하려면 C ~ 연산자가 수행하는 모든 2 진수를 반전하고 마지막으로 하나를 더해야합니다. 따라서, 우리는 C에서 똑같은 일을 표현하는 다른 방법이 지금

~(ULONG_MAX - (unsigned long)value + 1UL) + 1UL 

에 도착,하지만 난이 p는 두 가지 간단한 이유로 모든 관절 하나 모르겠어요 선택 : 첫째,이 있었다 두 번째로, GCC에서 사용하는 컴파일러는 부정적인 정수 (또는 최소한 x86 및 x86-64에 대한 2의 보수 표현을 사용하는 아키텍처에 대해서는 아무런 연산도하지 않고 GCC에서 테스트 한 것입니다. 5.4.0). 다시 말해, 음수에 대해 2의 보수가 아닌 표현을 사용하는 아키텍처를 실제로 사용하지 않는 이상 표현을 시도하고 "최적화"할 이유가 없습니다. 표현식이 이미 2의 보수 구조에서 단순화 되었기 때문입니다.

Answer 5

학생 운동입니까? 이 경우이 대답은 당신이 운동을 이해한다는 표시되지 않기 때문에 당신이 원하지 않는 것을 아마이지만, 그것을 할 수있는 가장 효율적인 방법이 가장 높습니다 :

• 이식성은 다음과 같습니다 것을 제공

  필요하지

• GCC는 사용되는 컴파일러

(AN '부호 INT는'시스템에 4 바이트를, 그리고 '긴'8 바이트 인 경우) __builtin_popcount() 같은 것을 사용할 수 있습니다 :

unsigned int binaryOnesCounter(long n) { 
     unsigned int nrOfOnes = __builtin_popcount((unsigned int)(n & 0xffffffff)); 

     nrOfOnes += __builtin_popcount((unsigned int)(n >> 32)); 
     return nrOfOnes; 
    } 

일부 아키텍처에서는 이것이 하드웨어로 이루어지기 때문에 gcc가 도움이 될 것입니다.코드 예 위에서는 sizeof (부호 INT)가 4를 sizeof (길이)이다 고 가정

주 8 32 시간 시프트보다 더 효율적일 수있다 GCC __builtins here

Answer 6

하나 개의 접근법에 대한

외 조회 테이블을 사용하는 것입니다. 예는 니블 현명한 룩업 :

#include <stdint.h> 
#include <stdio.h> 
#include <inttypes.h> 

uint32_t count_ones (uint32_t data) 
{ 
    static const uint8_t ONES [16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; 
    uint32_t count = 0; 

    while(data) 
    { 
    count += ONES[data & 0xF]; 
    data >>= 4; 
    } 

    return count; 
} 

int main() 
{ 
    uint32_t data = 0xAABBCCDD; 

    printf("%"PRIu32, count_ones(data)); 
} 

이는 256 바이트 큰 룩업 등으로 바이트 현명한 룩업을 확장 할 수 있습니다.

부호가있는 번호의 경우 단순히 동일한 기능을 사용하지만 서명 된 번호는 부호가없는 번호로 전송하면됩니다.