Cracking Coding Interview - 5.6 Conversion

2019-08-20 1 分钟阅读 ARTS-A

Conversion: Write a function to determine the number of bits you would need to flip to convert integer A to integer B.

EXAMPLE

1
2

Input:  29 (or: 11101), 15 (or: 01111)
Output: 2

Hints: #336, #369

解法1

这个题可以用XOR来做，因为XOR的意思是相异为真，然后再数一下有多少个1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int converstion(int a, int b) {
  int xor = a ^ b;
  int count = 0;
  while (xor != 0) {
    if (xor & 1 == 1) {
      count++;
    }
    xor >>>= 1;
  }
  return count;
}

解法2

解法1用位移来计算有多少个1，还可以有更简便的方法。

如果我们可以每次迭代都可以清除一个数字最右边的1，那么我们只需要计算吧这个数字清零为止共做了几次循环即可。

用n & (n - 1)可以做到这一点，回顾5.5 - Debugger里对于减法的描述：

当你在给二进制做减法的时候，实际上是把最右边的1变成0，把它右边的0都变成1。

实际上就是：

1
2
3
4
5

       rightmost 1
           v
n:     xxxx100
n - 1: xxxx011
AND:   xxxx000

两者AND一下就把最右边的1给去除了。

代码：

1
2
3
4
5
6
7
8
9

public int conversion(int a, int b) {
  int xor = a ^ b;
  int count;
  while (xor != 0) {
    count++;
    xor &= xor - 1;
  }
  return count;
}
Cracking Coding Interview - 5.5 Debugger
Cracking Coding Interview - 5.7 Pairwise Swap

版权

CC BY-NC-ND 4.0

相关文章

评论