用二进制补码查找二进制数，C

Question

我想我可能会让这有点复杂。我们应该通过一个很长的时间，并返回数字的二进制表示中1的数目。对于负数，我们返回二的补码。我有积极的工作，但两个补充是有点关闭。任何提示做这项工作将不胜感激。

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

它过于复杂

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

经典解决方案：

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

Althought我声明了如上所服用的unsigned long long的参数，它可被修改以进行签名或任何整数类型的：（char，int，或long）。

Answer 3

一个简单的方法是使用位移位和位掩码操作，把你的n到正确的表示（即只n为正值，或者负n S中的2补）。

如果您在代表负值的系统上操作了2个补充（并且大多数常用系统都这样做），那么您只需将n视为无符号值即unsigned long ul = n。然后，ul将包含负数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实际上是表示。

让我们假设你有一个函数

int bits_set_in_unsigned_long(unsigned long value); 

返回那些在value二进制表示的数量。

我们可以直接向该功能提供非负性输入。对于负输入端，我们计算出它们的补（在unsigned long），并返回者的数量在每问题的定义：

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); 
} 

您需要#include <limits.h>为ULONG_MAX。

以上，表达

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

转换value（的long型）其unsigned long补。让我们看看这是如何完成的。

对于二进制补码表示，我们首先需要作为无符号long的否定值value。但是，在许多体系结构中，-LONG_MIN == LONG_MIN，因为LONG_MAX的数量级小于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和1是常量，所以编译器可能希望先将它们加在一起，然后抱怨它溢出了类型（它没有，因为unsigned long类型使用模算术，我们对此很满意）。所以，我把减法放在中间，只是为了避免一些C编译器可能发出的警告（因为一些C编译器可能认为这样的构造通常是无意的错误，即使它们是完全标准的C代码）。

换句话说，(ULONG_MAX - (unsigned long)value + 1UL)给我们的value的大小（或绝对值），为unsigned long，由于value是在这一点上负。

要将其转换为二进制补码格式，我们需要将其所有的二进制数字--C ~操作员完成 - 并最终添加一个。因此，我们在

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

到现在，还有其他的方式来表达在C同样的事情，但我选择了这名P不知道任何一个关节的两个简单的原因：首先，它是最简单的证明是正确的;第二，我使用的编译器（GCC）将它视为一个无操作的体系结构，它带有用于负整数的二进制补码表示（至少x86和x86-64，这是我在GCC- 5.4.0）。换句话说，没有理由去尝试和“优化”表达式，除非你实际上有一个具有非二进制补码表示的负整数的体系结构;只是因为这个表达式已经在二进制补码架构上简化为无。

Answer 5

这是学生练习吗？在这种情况下，这个答案可能不是你想要的，因为它并不表明你理解的运动，但它是最有可能是最有效的方式做到这一点：

前提是：

• 可移植性不需要
• GCC是正在使用的编译器

（如果“无符号整型”您的系统上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（无符号整数）为4和sizeof（长）为8

进一步了解的gcc __builtins here

Answer 6

一种方法可能比移32倍更有效的，是使用查找表。与实例蚕食明智查询：

#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个字节大的查找等。

如果是带符号的数字，只需使用相同的功能，但将带符号的数字转换为无符号数。