5

可能重复：
查找 1 或 0 的连续位串

是否可以从左数连续的 1 整数？所以：从最高位开始的连续设置位的总数。

仅使用：

! ~ & ^ | + << >>

-1=0xFFFFFFFF将返回 32

0xFFF0F0F0将返回 12 (FFF = 111111111111)

不幸的是，没有循环。

可以假设机器：

  1. 使用 2s 补码，32 位整数表示。

  2. 以算术方式执行右移。

  3. 将整数移动超过字长时具有不可预测的行为。

我被禁止：

  1. 使用任何控制结构，例如 if、do、while、for、switch 等。

  2. 定义或使用任何宏。

  3. 在此文件中定义任何附加函数。

  4. 调用任何函数。

  5. 使用任何其他操作，例如 &&、||、- 或 ?：

  6. 使用任何形式的铸造。

  7. 使用除 int 以外的任何数据类型。这意味着您不能使用数组、结构或联合。

我看过 寻找 1 或 0 的连续位串 它正在使用循环，我不能使用。我什至不知道从哪里开始。

（是的，这是一项任务，但我只是向你们中那些足够熟练的人寻求帮助。我已经完成了几乎所有我需要做的事情，但这一个根本行不通。）

（对于那些仅仅因为它是为了学校而投反对票的人：常见问题解答：1 一个特定的编程问题，请检查 2 但是，如果您的动机是“我希望其他人向我解释 ______”，那么您可能没问题。）

4

5 回答 5

2

给你。函数参数可以是有符号或无符号的。alg 与签名无关。

int leftmost_ones(int x)
{
    x = ~x;
    x = x | x >> 1 | x >> 2 | x >> 3 | x >> 4 | x >> 5 | x >> 6 | x >> 7 | 
        x >> 8 | x >> 9 | x >> 10 | x >> 11 | x >> 12 | x >> 13 | x >> 14 | 
        x >> 15 | x >> 16 | x >> 17 | x >> 18 | x >> 19 | x >> 20 | x >> 21 | 
        x >> 22 | x >> 23 | x >> 24 | x >> 25 | x >> 26 | x >> 27 | x >> 28 | 
        x >> 29 | x >> 30 | x >> 31;
    x = ~x;
    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}

有一些优化的版本：

int leftmost_ones(int x)
{
    x = ~x;
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    x = ~x;

    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}
于 2012-09-26T16:40:13.230 回答
1

你可以使用循环吗？

int mask = 0x80000000;
int count = 0;
while (number & mask) {
    count += 1;
    mask >>= 1;
}
于 2012-09-26T15:52:45.243 回答
1

我认为这是可行的，基本上展开典型的循环并且通常很烦人。

怎么样：当且仅当答案为 1 时表达式为 1？我提供：

const int ok1 = !((number & 0xc0000000) - 0x800000000);

当然，!减法是为了解决有人破坏了==我们键盘上的键的问题。

然后，当且仅当 anwer 为 2 时，表达式为 1：

const int ok2 = !((number & 0xe0000000) - 0xc0000000);

如果你继续形成这些，最终的答案是它们的总和：

const int answer = ok1 + ok2 + ... + ok32;

顺便说一句，我似乎不记得我在学校时被分配了这些奇怪的限制作业，我想时代已经改变了。:)

于 2012-09-26T16:35:54.533 回答
1

你可以这样做：

int result = clz(~x);

即反转所有位，然后计算前导零。

clz返回前导零位的数量（通常也称为ffsor nlz） - 请参阅此处了解实现细节：http ://en.wikipedia.org/wiki/Find_first_set#Algorithms

于 2012-09-26T16:09:24.767 回答
0 
int count_consecutive_bits(unsigned int x) {
    int res = 0;
    while (x & 0x80000000) { ++res; x <<= 1; }
    return res;
}
于 2012-09-26T15:50:39.947 回答