[LeetCode] Hamming Distance（二进制中有多少个1）+ Number Complement（补码）

啊，又是好久没来了！

最近又开始刷leetcode，发现题目多了不少。还是从基础开始做吧。

这里是两道关于位运算的题。

1. Hamming Distance

题目链接在此

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4Output: 2Explanation:1   (0 0 0 1)4   (0 1 0 0)       ↑   ↑The above arrows point to positions where the corresponding bits are different.
就是数一下两个二进制数之间有位数有区别。很简单，先异或，再数有多少个1。
输多少个1那一步，我写的这篇博客有。
这里是我在不记得大神的做法的情况下，自己写的（3ms）：
class Solution {public:	int hammingDistance(int x, int y) {		int a = x ^ y;		int count = 0;		while (a != 0) {			count += (a & 1); 			a >>= 1;		}		return count;	}};
2. Number Complement
题目链接在此
Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary rePResentation.
Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5Output: 2Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1Output: 0Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.补码定义为二进制每位都翻转后得到的数字。这是我写的，就是先算出这个数的二进制有多少位，然后用这么多位的1跟他做异或。比如2的二进制是10，有两位， 就拿11和10做异或，得到01。显然比较慢：
class Solution {public:    int findComplement(int num) {        int n = num;        int bits = 0;        while(n) {            bits++;            n >>= 1;        }        return num ^ int(pow(2.0, bits) - 1);    }};这是discuss里的大神的做法：
class Solution {public:    int findComplement(int num) {        unsigned mask = ~0;        while (num & mask) mask <<= 1;        return ~mask & ~num;    }};例子：num          = 00000101mask         = 11111000~mask & ~num = 00000010