如何使用C语言查找一个数字中前导零的数量

Question

例如，如果我有数字64，则其二进制表示将为0000 0000 0000 0000 0000 0000 0100 0000，因此前导零的数量为25。 请告诉我正确的做法。即使您的复杂度> O（1），也请发布您的答案。谢谢

- user609306

---

O(1)的意思是，随着问题的变化，计算解决方案所需的时间保持恒定（大致上）。对于像你的固定大小的问题来说就没有意义了。 - sigfpe

这是一道作业题吗？你已经尝试了什么？ - Jacinda

我刚刚注意到 [functional-programming] 标签 - 这是真正的函数式编程吗？还是你只需要一个能够实现这个功能的函数？ - sarnold

你可以在任何进制下的数字前面随意添加任意多个0，而不改变它的值。你是否假设了32位整数类型？如果是这样，请明确说明。请注意，C语言并不要求提供恰好32位的类型：char/short/int/long的大小仅指定为最小值，并相对于彼此。 - Karl Knechtel

@sigfpe：如果您认为问题的规模是二进制表示中前导零的数量，则在此处使用O(1)是正确的。许多执行此操作的算法的复杂度取决于实际数字中前导零的数量。 - kriss

Answer 1

我刚刚在搜索结果的顶部发现了这个问题和这段代码:

int pop(unsigned x) {
    unsigned n;
    n = (x >> 1) & 033333333333;
    x = x - n;
    n = (n >> 1) & 033333333333;
    x = x - n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

int nlz(unsigned x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return pop(~x);
}

针对1位二进制数计数的pop函数，比第一个(得到赞同的)答案快几倍。

我没有注意到问题是关于64位数字的，所以在这里提供：

int nlz(unsigned long x) {
    unsigned long y;
    long n, c;
    n = 64;
    c = 32;
    do {
        y = x >> c;
        if (y != 0) {
            n = n - c;
            x = y;
        }
        c = c >> 1;
    } while (c != 0);
    return n - x;
}

这是一个64位算法，比上述提到的算法快了几倍。

- user6713148

Answer 2

请参见此处获取32位版本和其他优秀的位操作技巧。

// this is like doing a sign-extension
// if original value was   0x00.01yyy..y
// then afterwards will be 0x00.01111111
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x |= (x >> 32);

然后你只需要返回64 - numOnes(x)。一个简单的方法是numOnes32(x) + numOnes32(x >> 32)，其中numOnes32被定义为：

int numOnes32(unsigned int x) {
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}

我还没有尝试过这段代码，但这应该可以直接使用numOnes64（在更短的时间内）：

int numOnes64(unsigned long int x) {
     x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L);
     x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L);
     // collapse:
     unsigned int v = (unsigned int) ((x >>> 32) + x);
     v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f);
     v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff);
     return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff);
}

- MotiNK

Answer 3

右移是你的好朋友。

    int input = 64;
    int sample = ( input < 0 ) ? 0 : input;
    int leadingZeros = ( input < 0 ) ? 0 : 32;

    while(sample) {
        sample >>= 1;
        --leadingZeros;
    }
    printf("Input = %d, leading zeroes = %d\n",input, leadingZeros);

- Prince John Wesley

---

谢谢John...我也想要同样的东西...但它的大O是以2为底的O(log n)。 如果你取64，那么你必须将位移动log 64次，即6次。 取另一个数字n，使得while循环运行log n次。 - user609306

@user609306：由于这里最大可能的n是32（或64位数字为64），因此在使用ceil时应非常谨慎。调用ceil后面的常数倍数可能比执行64个循环或更少的时间要长得多。 - kriss

Answer 4

我会选择：

unsigned long clz(unsigned long n) {
    unsigned long result = 0;
    unsigned long mask = 0;
    mask = ~mask;
    auto size = sizeof(n) * 8;
    auto shift = size / 2;
    mask >>= shift;
    while (shift >= 1) {
        if (n <= mask) {
            result += shift;
            n <<= shift;
        }
        shift /= 2;
        mask <<= shift;
    }
    return result;
}

- Tomasz Gawel

Answer 5

由于以2为底数的对数大致代表了表示一个数字所需的比特数，因此在答案中可能会有用：

irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor()
=> 25
irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor()
=> 25
irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor()
=> 25
irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor()
=> 24

当然，使用log(3)的一个缺点是它是一个浮点数例程；可能有一些极其聪明的位操作技巧来查找整数中前导零位的数量，但我想不出一个。

- sarnold

Answer 6

使用浮点数并不是正确的答案...

这里有一个我用来计算末尾0的算法...想要计算首位0可以进行修改... 这个算法的时间复杂度为O(1)（在某些CPU上总是以大约相同的时间执行甚至完全相同）。

int clz(unsigned int i)
{
  int zeros;
  if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0;
  if ((i&0xff)==0) zeros+= 8, i>>= 8;
  if ((i&0xf)==0) zeros+= 4, i>>= 4;
  if ((i&0x3)==0) zeros+= 2, i>>= 2;
  if ((i&0x1)==0) zeros+= 1, i>>= 1;
  return zeroes+i;
}

- user3256556

---

代码中的分支对于这种事情没有意义。使用位操作技术，您可以在没有任何分支的情况下完成此操作，请参见例如：http://aggregate.org/MAGIC/#Leading Zero Count - MotiNK

实际上，在具有条件执行并且每行代码将被3条指令（其中2条是条件指令）替换的ARM类型芯片上，这样的分支确实有意义。例如：ANDS R4，R0，＃0xff addeq R1，R1，＃8，moveq R0，R0 shl 8。然后，整个函数变成了3 * 5条指令，具有精确的时间执行。位操作可能不会更好。当然，ARM芯片具有您可以使用的CLZ指令！ - user3256556