c - 从左边数连续 1 位的个数

Question

我被困在这个问题上：假设我们有 32 位整数，编写一个 C 函数来计算从左边开始的连续 1 位的数量。例如：

leftCount(0xFF000000) = 8
leftCount(0x0FFFFFFF) = 0 (because the number starts with 0)
leftCount(-1) = 32

在函数中，我可以使用逻辑运算符，例如！~ & ^ | + << >>

不允许使用循环和条件结构。

谢谢

Answer 1

在 GCC 中，您可以使用内置函数：

内置功能：int __builtin_clz (unsigned int x)

返回 中前导 0 位的数量x，从最高有效位位置开始。如果x为 0，则结​​果未定义。

您必须使用二进制否定来否定输入：~x（0 将变为 1，反之亦然）。

---

这是一个更学术的解决方案：

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

int leftCount (unsigned int value) {
    if (~value == 0) {
        return 32; // you said your ints were 32 bits, so the code assumes that
    }
    int result = 0;
    while (value >> 31 == 1) { // test if highest bit is set
        value <<= 1; // shift the input to the left
        ++result; // one more bit was seen
    }
    return result;
}

int main (void) {
    unsigned int value;
    while (scanf ("%i", &value) == 1) {
        printf ("leftCount(0x%x) == %u\n", value, leftCount(value));
    }
    return 0;
}

Answer 2

您可以通过评估来测试 bitx是否设置了值。如果未设置该位，则为零。yy & (1 << x)

使用它，您可以从 31 循环到 0，检查每个位是否已设置，当您到达未设置的位时停止。您应该能够自己编写代码。

您可以通过二进制搜索来加快速度。您可以通过评估来检查前 16 位是否已设置(y & 0xFFFF0000) == 0xFFFF0000。如果是，那么您可以以类似的方式检查接下来的 8 位；如果不是，那么您可以检查前 8 位。使用此方法向下递归，您将拥有更快的算法。

Answer 3

有一个快速的函数来计算前导零的数量，并且很容易将这个问题转换为：补充输入。

int leftCount = input == 0 ? 0 : __builtin_clz(~input);

那里甚至没有算法。

Answer 4

我在互联网上找到了自己的解决方案。但我的要求是使用不超过 50 个逻辑运算符，所以请任何人帮我优化这个功能。

int bit_count_from_left(int x) {
/* Shift every bit to the rightmost bit and & it with 1, then start from the leftmost bit and determine 
 * whether a given bit and all the bits to its left are set to 1. */
    int lb01 = ((x >> 31) & 1); int lb02 = ((x >> 30) & 1); int lb03 = ((x >> 29) & 1);
    int lb04 = ((x >> 28) & 1); int lb05 = ((x >> 27) & 1); int lb06 = ((x >> 26) & 1);
    int lb07 = ((x >> 25) & 1); int lb08 = ((x >> 24) & 1); int lb09 = ((x >> 23) & 1);
    int lb10 = ((x >> 22) & 1); int lb11 = ((x >> 21) & 1); int lb12 = ((x >> 20) & 1);
    int lb13 = ((x >> 19) & 1); int lb14 = ((x >> 18) & 1); int lb15 = ((x >> 17) & 1);
    int lb16 = ((x >> 16) & 1); int lb17 = ((x >> 15) & 1); int lb18 = ((x >> 14) & 1);
    int lb19 = ((x >> 13) & 1); int lb20 = ((x >> 12) & 1); int lb21 = ((x >> 11) & 1);
    int lb22 = ((x >> 10) & 1); int lb23 = ((x >> 9) & 1);  int lb24 = ((x >> 8) & 1);
    int lb25 = ((x >> 7) & 1);  int lb26 = ((x >> 6) & 1);  int lb27 = ((x >> 5) & 1);
    int lb28 = ((x >> 4) & 1);  int lb29 = ((x >> 3) & 1);  int lb30 = ((x >> 2) & 1);
    int lb31 = ((x >> 1) & 1);  int lb32 = ((x) & 1);
    int bool01 = lb01;          int bool02 = bool01 & lb02; int bool03 = bool02 & lb03;
    int bool04 = bool03 & lb04; int bool05 = bool04 & lb05; int bool06 = bool05 & lb06;
    int bool07 = bool06 & lb07; int bool08 = bool07 & lb08; int bool09 = bool08 & lb09;
    int bool10 = bool09 & lb10; int bool11 = bool10 & lb11; int bool12 = bool11 & lb12;
    int bool13 = bool12 & lb13; int bool14 = bool13 & lb14; int bool15 = bool14 & lb15;
    int bool16 = bool15 & lb16; int bool17 = bool16 & lb17; int bool18 = bool17 & lb18;
    int bool19 = bool18 & lb19; int bool20 = bool19 & lb20; int bool21 = bool20 & lb21;
    int bool22 = bool21 & lb22; int bool23 = bool22 & lb23; int bool24 = bool23 & lb24;
    int bool25 = bool24 & lb25; int bool26 = bool25 & lb26; int bool27 = bool26 & lb27;
    int bool28 = bool27 & lb28; int bool29 = bool28 & lb29; int bool30 = bool29 & lb30;
    int bool31 = bool30 & lb31; int bool32 = bool31 & lb32;
    int result = bool01 + bool02 + bool03 + bool04 + bool05 + bool06 + bool07 + bool08 + bool09 + bool10
        + bool11 + bool12 + bool13 + bool14 + bool15 + bool16 + bool17 + bool18 + bool19 + bool20
        + bool21 + bool22 + bool23 + bool24 + bool25 + bool26 + bool27 + bool28 + bool29 + bool30
        + bool31 + bool32;
    return result;
}

Answer 5

剧透：

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

unsigned naive_leading1bit_count(uint32_t val)
{
unsigned cnt;

for (cnt=0; val & (1u << (sizeof val*CHAR_BIT-1)); val <<=1 ) {
        cnt += 1;
        }
return cnt;
}

int main(void)
{
unsigned res;
uint32_t uuu;

for (uuu = 0xf; uuu; uuu <<=1) {
        res = naive_leading1bit_count( uuu );
        printf("%x: %u\n", uuu, res);
        }

return 0;
}