0

我需要想出一个函数，它需要一个字符和一个设置位的索引，并隔离一个包含该位的 1 字符串。

IE

char isolate(unsigned char arg, int i);

例如：

隔离（221,2）将返回 28（11011101 >>> 00011100）

隔离（221,6）将返回 192（11011101 >>> 1100000）

查找表似乎是一个笨拙的解决方案，因为它需要 ~256*8=2048 个条目。

我正在考虑检查索引左侧和右侧的每个单独的位：

char isolate(char arg, int i)
{
   char result=0;
   char mask = 1<<i;
   for(char mask = 1<<i; arg & mask != 0; mask>>=1)
      result |= mask;
   for(char mask = 1<<i; arg & mask != 0; mask<<=1)
      result |= mask;
   return result;
}

但它也似乎有点难看。我怎么能做得比这更好？

4

2 回答 2

3

这是一个有趣的操作。您编写的代码可以很好地表达它，所以您介意详细说明它有多丑吗？

我可以看到的细节：鉴于它在 中i表示一个位数，因此成为更广泛的类型arg绝对没有意义。在条件下i写作从来没有意义。!= 0您可能不想在使用它的任何地方重新声明掩码，也不想连续两次初始化它。

至于实际的扩展位掩码，我现在想不出一种更具表现力、更清洁或更高效的方式。

于 2013-03-24T22:00:18.897 回答
0

警告：这些都没有经过测试甚至相关*，但它可能很有趣。

隔离最右边的 1 很容易，就像这样：（x ^ (x & ((x|(x-1))+1))下面的解释），所以让我们来处理它。

首先x|(x-1)将最右边的 1 涂抹到右边，加 1 将所有这些位变为 0，包括最右边的 1，x与删除最右边的 1，最后，与x只留下最右边的 1。

然后我们只需要确保我们正在寻找的范围是最右边的。这不太适合简单的位数学运算，但如果有前导零计数 ( clz)，那就不太难了：

int shift = 32 - clz(~x & ((1 << i) - 1));  //replace 32 with word size
x = (x >> shift) << shift;

((1 << i) - 1)制作我们正在寻找的运行的右端可能所在的部分的掩码（它也可能错过结束，但这没关系），然后查找inclz右侧的第一个零，然后移位删除我们不想查看的位。ix

应用第一个公式，用于隔离最右边的 1 的运行，以得到其中的运行i。i最好在某个运行中，或者事情横向发展（更准确地说，它会返回第一次运行从高于i)的索引开始的 1s

*：对于这个问题，这些都不重要。除非您只有少量可用内存，否则 2KB 表并不是一个笨拙的解决方案，即使是这种情况，输入也很短，以至于循环并不是那么糟糕。

于 2013-03-24T23:40:11.827 回答