C++求解漢明距離-創(chuàng)新互聯(lián)

漢明距離介紹
漢明距離應(yīng)用
解法1：Brian Kernighan算法
解法2
解法3

成都創(chuàng)新互聯(lián)公司從2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目做網(wǎng)站、成都網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元克州做網(wǎng)站,已為上家服務(wù),為克州各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

漢明距離介紹

leetcode 461 漢明距離，難度：簡(jiǎn)單

兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目。

給你兩個(gè)整數(shù) x 和 y，計(jì)算并返回它們之間的漢明距離。

示例 1：

輸入：x = 1, y = 4
輸出：2
解釋：
1 (0 0 0 1)
4 (0 1 0 0)

對(duì)應(yīng)二進(jìn)制位不同的位置個(gè)數(shù)為2

示例 2：

輸入：x = 3, y = 1
輸出：1

提示：

0<= x, y<= 231 - 1

漢明距離應(yīng)用

漢明距離廣泛應(yīng)用于多個(gè)領(lǐng)域。在編碼理論中用于錯(cuò)誤檢測(cè)，在信息論中量化字符串之間的差異。

兩個(gè)整數(shù)之間的漢明距離是對(duì)應(yīng)位置上數(shù)字不同的位數(shù)。

解決此題，可以使用異或運(yùn)算，當(dāng)對(duì)應(yīng)的二進(jìn)制為不同時(shí)，輸出為1，然后統(tǒng)計(jì)異或后1的個(gè)數(shù)。

統(tǒng)計(jì)二進(jìn)制中1的個(gè)數(shù)，主要有3種方法：

Brian Kernighan算法，
移位運(yùn)算
直接使用系統(tǒng)API.

下面分別介紹這3種算法

解法1：Brian Kernighan算法

Brian Kernighan算法可以用于清除二進(jìn)制數(shù)中最右側(cè)的1。Brian Kernighan算法的做法是先將當(dāng)前數(shù)減一，然后在與當(dāng)前數(shù)進(jìn)行按位與運(yùn)算。

x=x&(x-1)

示意圖
在這里插入圖片描述
x&(x-1)的結(jié)果變成了1110

利用此算法我們可以統(tǒng)計(jì)一個(gè)數(shù)字的二進(jìn)制中的1的個(gè)數(shù)，即一比特?cái)?shù)：

#includeusing namespace std;

int oneCounts(int num) {int ones = 0;

    while (num >0) {num &= num - 1;
        ones++;
    }

    return ones;
}

int main()
{int num = 23;  // 1 0111

    cout<< oneCounts(num)<< endl;

    return 0;
}

對(duì)應(yīng)的此題的解法

class Solution {public:
    int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
        while (s) {s &= s - 1;
            ret++;
        }
        return ret;
    }
};

復(fù)雜度分析

時(shí)間復(fù)雜度：O(logC)，其中 C 是元素的數(shù)據(jù)范圍;
空間復(fù)雜度：O(1)。

確實(shí)簡(jiǎn)單，簡(jiǎn)單的前提是得知道Brian Kernighan算法.

解法2

不知道Brian Kernighan算法也可以解決。
使用異或運(yùn)算，記 s = x⊕y，我們可以不斷地檢查 s 的最低位，如果最低位為 1，那么令計(jì)數(shù)器加一，然后我們令 s 整體右移一位，這樣 s 的最低位將被舍去，原本的次低位就變成了新的最低位。我們重復(fù)這個(gè)過(guò)程直到 s=0 為止。這樣計(jì)數(shù)器中就累計(jì)了 s 的二進(jìn)制表示中 1 的數(shù)量。

代碼

class Solution {public:
    int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
        while (s) {ret += s & 1;
            s >>= 1;
        }
        return ret;
    }
};

代碼說(shuō)明s&1, 如果最末位是1，那么s&1 = 1, ret += 1，否則ret += 0, 然后s右移一位。

解法3

使用系統(tǒng)內(nèi)置API: __builtin_popcount, 該函數(shù)可以統(tǒng)計(jì)二進(jìn)制數(shù)中1的個(gè)數(shù)，但是僅在gcc/g++下可使用。
代碼

#includeusing namespace std;

class Solution {public:
    int hammingDistance(int x, int y) {return __builtin_popcount(x ^ y);
    }
};

int main(){Solution s;

    cout<< s.hammingDistance(1, 4)<< endl;

    return 0;
}

雖然這是一道簡(jiǎn)單題，但是并不簡(jiǎn)單，leetcode沒(méi)哪道題簡(jiǎn)單。

本文參考資料
（1）https://leetcode.cn/problems/hamming-distance
（2）https://zhuanlan.zhihu.com/p/498119781

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：C++求解漢明距離-創(chuàng)新互聯(lián)
標(biāo)題URL：http://muchs.cn/article40/hesho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、面包屑導(dǎo)航、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站設(shè)計(jì)、用戶體驗(yàn)、外貿(mào)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容