计算数组中值为 1 的位数 - 理解其背后的代码 (C)

Question

The following code counts the number of bits of value '1' in the array 'buf':

long bit_count(long *arr, int size)
{
    int w,b;
    unsigned long word=0;
    long n = 0;

    for(w = 0; w<size ; w++){
        word = arr[w];
        while(word != 0){
            n += word & 1;
            word >>= 1;
        }
    }
    return n;
}

int main() {

     char buf[] = {"There is always one more!"};         //(1)
     int length = strlen(buf)>>3;                        //(2)
     long *a = (long*) (buf + length);                   //(3)
     //char * b = (char *)a; // this is a comment.       //(4)
     int len = strlen((char*)a);                         //(5)
     long total_count = bit_count((long*) buf, length);  //(6)
     *a = (*a) & (((long)1<<(len*8))-1);                 //(7)
     char *c = (char*)a;                                 //(8)
     total_count += bit_count(a,1);                      //(9)
     printf("bits number %ld\n",total_count);            //(10)

    return 0;
}

这是我对代码的理解：（如有错误请指正，我想深入理解）

在第 (2) 行中，他们计算了 buf 中的字母数，即 25，相当于 25 个字节。因为 char 的大小是 1 个字节。然后将该数字右移 3 位，然后除以 8， 8 定义了 8 个字节 = 1 个 long 类型。 那么这个buf数组包含了多少"longs"。

第 (3) 行 - 'a' 指向一个值，该值包含将 buf 的其余部分转换为 (long *) - 在第 (4) 行中，我看到 b* 值将是“！ “这正是数组中 1 个字节的余数。 但我不太理解转换为 (long *) 如果我检查

我得到的值是不同的

long check = (long) (buf + length);

所以当我这样做时到底发生了什么 - {(long*)buf} 是我的第一个问题。

在第 (6) 行中，我计算了数组第一部分中的位（按长）在第 (9) 行中，我计算余数中的位数。

我不明白的是 - 第 (7) 行发生了什么？

Answer 1

代码没有什么猫腻，但不是很好。实际上，它非常糟糕，不是因为样式而是因为它破坏了内存。

(2)  int length = strlen(buf)>>3;

这一行计算适合字符串的 long 个对象的总数，假设 long 是八个字节（应该使用 / sizeof(long) 而不是 >>3 ) 并且 int 足以容纳数字（应该使用 size_t 而不是 int）。

(3)  long *a = (long*) (buf + length);

这似乎是打算将a设置为指向字符串末尾的片段，该片段的长度不足以包含另一个long对象。但是，因为 length 是 long 个对象的数量，而 buf 充当指向 char 的指针，所以它的算法是不正确的。当它打算计算 buf 加 length long 个对象时，它计算 buf 加 length char 个对象。它应该使用 (long *) buf + length。此外，它假定具有任意对齐方式的 char * 可以合理地转换为 long *，这是 C 标准不保证的。

(5)  int len = strlen((char*)a);

这将计算片段中的字节数。这是一种浪费，因为代码之前计算了字符串的长度。它本可以保存该长度并取商和余数对 long 的大小取模，而不是再次调用 strlen。

(6)  long total_count = bit_count((long*) buf, length);

这会计算缓冲区主要部分中设置的位数，即被视为 long 个对象的整数部分。与之前的转换一样，它假设 char * 可以转换为 long *，而且，它调用的例程使用该指针从未定义的对象中读取 long 对象作为 long 的数组，因此违反了 C 别名规则。

(7)  *a = (*a) & (((long)1<<(len*8))-1);

回想一下，a 指向字符串中的一些尾随字节。 (long)1<<(len*8) 将位移动到刚好超过该字节数，假设字节是八位（应该使用 CHAR_BIT 而不是 8）。（例如，如果有两个字节，则创建值 10000₁₆。）然后减去一个为字节创建一个位掩码 (FFFF₁₆ 在示例中）。然后 *a 尝试从字符串末尾读取 long ，然后使用 & 应用掩码将读取的值减少为字符串中的字节。这不仅再次违反了 C 的别名规则，而且还读取了 buf 的内存之外的内容，这具有未定义的行为。最后，该语句将更新后的值写入 *a，这更糟——如果您在 buf 之外读取，现在代码正在 buf 之外写入，导致某处损坏未知。

(8)  char *c = (char*)a;

此行无用，因为从未使用过 c。

(9)  total_count += bit_count(a,1);

这计算在 (7) 中更新的 long 中设置的位数。

在bit_count例程中，我们发现代码是一位一位地计算位。这是荒谬的。如果正在使用的特定 C 实现允许使用未对齐地址的别名，则违反关于别名的 C 规则对于获得处理整个 long 对象而不是单个 char 对象的一些性能优势可能是有意义的。但是这段代码只是进行了逐位处理；它不会从处理器上的某些位计数（也称为人口计数）指令中获得任何优势。

此外，bit_count 例程识别出它应该使用 unsigned long 作为位数，因为它将 word 定义为 unsigned long。但是它没有意识到它应该在整个过程中使用 unsigned long，因为 long 可能有一个会导致代码失败的陷阱表示。

它还定义了 b 但从未使用过它。

计算数组中值为 1 的位数 - 理解其背后的代码 (C)

Counting the number of bits of value 1 in an array - Understanding the code behind it (C)

c

arrays

count

bits