c - 按位操作 : After a series of consecutive bits, 将最左边的不同位传播到右边

Question

这个问题不太可能帮助任何 future 的访客；它只与一个小地理区域、一个特定时刻或一个非常狭窄的情况相关，而这些情况通常不适用于互联网的全局受众。如需帮助使这个问题更广泛地适用，visit the help center .




9年前关闭。




我在一个练习中遇到了一些麻烦，我们必须只使用位运算符(在 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...

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

Answer 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;
}

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

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