计算左边连续1位的数量

Question

我坚持这个问题:假设我们有32位整数,写一个C函数来计算从左边开始的连续1位的数量.例如:

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

在函数中,我被允许使用逻辑运算符,如!〜&^ | + << >>

不允许循环和条件结构.

谢谢

Answer 1

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

使用它,您可以从31向下循环到0,检查每个位是否已设置,当您达到未设置位时停止.你应该能够自己编码.

您可以通过二进制搜索加快速度.您可以通过评估来检查是否设置了前16位(y & 0xFFFF0000) == 0xFFFF0000.如果是,则可以以类似的方式检查接下来的8位; 如果不是,那么你可以检查前8位.使用此方法递减,您将获得更快的算法.

Answer 2

在GCC中,您可以使用内置函数:

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

x从最高有效位开始返回前导0位的数量.如果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;
}