在一個字符中分隔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的字符串

回答

相關問題