在一个字符中分隔1的字符串

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

即

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

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

来源

2013-03-24 QuarterlyQuotaOfQuotes

你的提议和问题陈述+例子似乎告诉不同的故事。请您在后置条件下展开。 – 2013-03-24 21:52:28

我改变了格式。我猜这很混乱。 – QuarterlyQuotaOfQuotes 2013-03-24 22:04:22

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

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

首先x|(x-1)涂片最右边的1到右侧，加入1关闭所有的位为0，包括1的最右边跑，安定x与排除最右边的运行1的，最后，异或与x只保留了最右边的运行1秒。

然后我们只需要确保我们要找的范围是最右边的范围。这是简单的bitmath不太适合，但如果有计算前导零（clz），这不是太辛苦：

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

((1 << i) - 1)使得部分的面具，我们正在寻找可以在运行的右端（也可能是只是错过了结束，但没关系），然后clz寻找的右边的第一个零，然后这些转移移除了我们不想看到的那些位。

将第一个公式用于隔离最右边的1的运算结果，以得到i所在的运行结果。i最好在某些运行中，或者事情横跨（更准确地说，它将返回从高于i的索引开始的1的第一次运行）

*：对于这个问题，这些都不重要。一个2KB的表格不是一个笨拙的解决方案，除非你只有少量的内存可用，并且即使是这样，输入是如此之短以至于循环并不是那么糟糕。

来源

2013-03-24 23:40:11 harold

这是一个有趣的操作。你写的代码表达得很好，你想介绍一下它的丑陋吗？

我可以看到的细节：由于i表示arg中的位数，所以i绝对没有意义。在条件下写!= 0从来没有一点意义。您可能不希望在使用它的任何地方重新宣布掩码，也不希望在连续两次初始化掩码。

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

来源

2013-03-24 22:00:18

在一个字符中分隔1的字符串

回答

相关问题