位运算题目总结

LeetCode 求二进制数中1的个数

这是一种更高效的思路，把整数减1，再与原来的数做与运算，会把原来的二进制数最右边的1去掉。计算有多少次去掉1的操作，即可知道1的个数。

n = n & (n-1)

1
2
3
4
5
6
7
8
9

int hammingWeight(uint32_t n) {
       int cnt = 0;
       while(n)
       {
           cnt++;
           n = n & (n-1);
       }
       return cnt;
   }

LeetCode 2的幂

输入一个数，判断是不是2的幂次方

2的幂次方，只要满足n>0 && (n & (n-1)) == 0即可。

1
2
3
4
5
6

bool isPowerOfTwo(int n) {
       if(n > 0 && (n & (n-1)) == 0)
           return true;
       else
           return false;
   }

汉明距离

汉明距离是指两个数字对应二进制位不同的位置的数目。如1 (0 0 0 1)　4 (0 1 0 0)，第1,3位不同

1
2
3
4
5
6
7
8
9

int hammingDistance(int x, int y) {
        int res = 0;
        int n = x ^ y;
        while(n){
            n = n & (n-1);
            res++;
        }
        return res;
    }

2020/05/12美团笔试

最大的汉明距离

当时没有考虑清楚，每个数之间的汉明距离都要算一遍，而简单地一次遍历相邻数字的汉明距离，所以只通过了18%，现在复盘刷到类似的题目时突然想起来了……

• ← Previous Post
• Next Post →