LeetCode(一)--461.Hamming Distance&476.Number Complement 位运算

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 = 4

Output: 2

Explanation:

• 1 (0 0 0 1)
  4 (0 1 0 0)

The above arrows point to positions where the corresponding bits are different.

解题方法如下

public class Solution {
public int hammingDistance(int x, int y) {
int diff=x^y;//位异或
int count=0;
while (diff != 0) {  
             count++;  
            diff = diff & (diff - 1); 
// 计算1的个数
        }  
return count;

    }
}

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: 5 Output: 2
Explanation: 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: 1 Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

解题方法如下

public class Solution {
public int findComplement(int num) {
int temp = num, mask = 1;
while(temp != 0) {
            temp = temp >> 1;//右移
            mask = mask << 1;//左移
        }
return num ^ (mask - 1);
    }
//mask - 1为和num二进制位等长的所有位数为1的数，
//与num取^可以得到和num相反的数字 

}

还有解法

public class Solution {
public int findComplement(int num) {
return ~num & ((Integer.highestOneBit(num) << 1) - 1);
//highestOneBit当num是正数时返回跟它最靠近的比它小的2的N次方
//即最高位是1其余位都是0且与num位数相同的数
    }
}

涉及到位运算，有许多技巧，可以参考
20个位运算技巧
位运算简介及技巧基础篇
位运算简介及技巧进阶篇
位运算简介及技巧进阶篇2
位运算简介及技巧实战篇