-1

我在一个练习中遇到了一些麻烦，我们必须只使用位运算符（在 C 中）、一元运算符 ~ 和 ! 以及有符号整数变量来实现函数。我们不允许使用任何条件、循环或任意数字——见鬼，我们甚至不允许使用减号（-），但有一个非常简单的解决方法。

基本上，任务是从最高有效位开始计算设置位的数量，直到找到未设置的位。我以为我已经把这一切都弄清楚了，除了我无法找到和传播第一个未设置的位。我的想法是反转并将（现在）最左边的 1 位向右传播，以便能够将其隔离，然后向右移动 3（因为隔离会将其向上移动），结果应该成为这样做在右边设置 1 位。

我在这方面最大的障碍是找到最左边的位（无论是设置还是未设置）并传播它......任何想法，提示或线索？

我的理论算法会做什么的一个例子：

1110 0101 1011 1100    // our target
0001 1010 0100 0011    // invert it
0001 1111 1111 1111    // propagate
0001 0000 0000 0000    // magic happens -- isolate the leftmost 1 bit
0000 0100 0000 0000    // shift by >>2
// it's at this point I realize I have no idea what I'm doing anymore
// this looks like 2^10 which is a bit too big...

所以基本上，我什么都没有。有人可以给我一个关于我应该读什么的提示吗？

4

1 回答 1

1

通过逐位测试8位整数的“蛮力”解决方案：

int countLeadingBits(int8 x)
{
    int isSetFirst1 = (!!(x & 0x80));               /* 1 if bit pattern is 1xxxxxxx */
    int isSetFirst2 = (!!(x & 0x40)) & isSetFirst1; /* 1 if bit pattern is 11xxxxxx */
    int isSetFirst3 = (!!(x & 0x20)) & isSetFirst2; /* 1 if bit pattern is 111xxxxx */
    int isSetFirst4 = (!!(x & 0x10)) & isSetFirst3; /* etc */
    int isSetFirst5 = (!!(x & 0x08)) & isSetFirst4;
    int isSetFirst6 = (!!(x & 0x04)) & isSetFirst5;
    int isSetFirst7 = (!!(x & 0x02)) & isSetFirst6;
    int isSetFirst8 = (!!(x & 0x01)) & isSetFirst7;

    return isSetFirst1 +
           isSetFirst2 +
           isSetFirst3 +
           isSetFirst4 +
           isSetFirst5 +
           isSetFirst6 +
           isSetFirst7 +
           isSetFirst8;
}

这个想法是隔离一个位 like x & 0x40，然后使用双重否定将其转换为 0 或 1 !!，然后我们可以&像布尔运算符一样使用我们知道必须是 0 或 1 的数字。一旦我们测试了所有位，我们可以通过添加它们来简单地计算设置了多少。

我将把它留给你，将它扩展到你需要的尽可能多的位。

于 2012-09-21T02:05:10.683 回答