查找重疊1位的計數

我試圖找出2個給定數字之間重疊1位的數量。查找重疊1位的計數

例如，給定5和6：

5 // 101 
6 // 110

有1個重疊的1位（第一位）

我有以下代碼

#include <iostream> 
using namespace std; 

int main() { 
    int a,b; 
    int count = 0; 
    cin >> a >> b; 
    while (a & b != 0) { 
     count++; 
     a >>= 1; 
     b >>= 1; 
    } 
    cout << count << endl; 

    return 0; 
}

但是，當我進入335和123它返回7，但我認爲這是不正確的

有人可以看到我的代碼有問題嗎？

來源

2010-07-13 dato datuashvili

335 in binary = 101001111; 123在二進制= 001111011.看起來像4給我。 – 2010-07-13 21:01:00

你的算法不正確 - 你只需要和這兩個值，然後對結果進行總體計數。 – 2010-07-13 21:28:18

我認爲值得指出的是，這個問題本質上是要求如何計算'hammingWeight（a＆b）'。有一些很好的答案如何計算海明重量在這裏：http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer – msandiford 2013-04-21 01:21:39

問題是，你只是打印出任意的比特匹配的次數，因爲每次迭代都會取消最不重要的比特位（這將最多爲設置的比特數爲較小的數字）。你比較每次迭代的[a] BITWISE和[b]的所有比特。您也可以用1遮蔽糾正這個：a & b & 1，這樣當你換檔的事情位向右每一次，你只如果最低顯著位正在檢查檢查：

while (a && b){ 
    count += a & b & 1; 
    a>>=1; 
    b>>=1; 
}

來源

2010-07-13 21:02:43

第一句話並不嚴格; 85（01010101）和170（10101010）將輸出0，因爲它們沒有共同之處。他正在打印最重要的匹配位的偏移量 – 2010-07-13 21:26:04

哎呦，好抓;剛剛修改。 – 2010-07-13 21:36:05

您現有的算法每個位計數只要其餘位中的任何位測試匹配;因爲123和335有一個共同的MSB，所以只要任一個數不爲零就是對的。 123是較小的7位，所以它是真實的7次，直到該數字被完全處理。作爲極端情況，128（10000000）和255（11111111）會返回8與您的方法，即使它實際上是1.

你想和兩個數字一起開始，然後計數1那麼結果

來源

2010-07-13 21:01:28

你想計數設置的位數。相反，你的代碼是計算二進制對數。

只有在設置了最低位位時才增加計數。

for (int c = a & b; c != 0; c >>= 1) { 
    if (c & 1) 
    ++count; 
}

來源

2010-07-13 21:04:58 erickson

我喜歡Marcs爲了清晰起見而更好地回答，但是這對於更少的操作更好（我希望此版本以等效while循環完成，但這是個人偏好）。 – Dolphin 2010-07-14 14:17:09

稍短形式：

int countCommonBits(int a,int b) {  
    int n = 0; 
    for (unsigned v = (unsigned)(a & b); v; v >>= 1) { 
     n += 1 & v; 
    } 
    return n; 
}

如果您知道這兩個數字是積極的，你可以不使用無符號的類型的。注意當使用「int」時，負號右移的符號擴展會給你帶來一些過多計數（即無限循環）。

很久以後... 回顧一箇舊的答案，碰到了這個。當前「接受」的答案是1）效率低下，2）如果數字是負數，則爲無限循環。 FWIW。

來源

2010-07-13 23:54:34

查找重疊1位的計數

回答

相關問題