龙猫12138 2018-05-14 08:33 采纳率: 0%
浏览 1511
已结题

java,算汉明距离,leetcode上这个最快的算法是什么意思,求指点

public int hammingDistance(int x, int y) {
int hamming = x ^ y;
int cnt = 0;
while(hamming > 0){
hamming = hamming & (hamming - 1);
cnt++;
}
return cnt;
}


第一句相异还明白的,但是当hamming大于0,然后用hamming去和hamming-1按位相和就不懂了,为什么这样就能算出来?

  • 写回答

3条回答

  • huster_yjt 2018-05-14 08:41
    关注

    while(hamming > 0){
    hamming = hamming & (hamming - 1);
    cnt++;
    }
    这一段是计算hamming有多少个1,hamming & (hamming - 1);相当于每次都把二进制的一个1消除了, 比如 hamming 二进制为1111;
    则hamming & (hamming - 1) = 1110,下次循环就变成了 1100.。。依次类推,最后就是4

    评论

报告相同问题?