learn-to-code
Question: Write a function to compute the number of bits required to convert a integer to another.
For example, Input 29 (or 11101), 15 (or 01111) the output is 2.
It may seem complex but it is actually easy to do. The number of different bits can be counted by the exclusive OR (XOR). If the XOR of two bits are 1, which means a flip is required. In the following, we just shift the result of A xor B and count each bit if it is one:
1 2 3 4 5 6 7 | int bitSwapRequired(int a, int b) { int count = 0; for (int c = a^b; c != 0; c >>>= 1) { count += c & 1; } return count; } |
int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a^b; c != 0; c >>>= 1) {
count += c & 1;
}
return count;
}However, this can be improved a little bit better. Instead of shifting one bit at a time, we can use X & (X – 1) to clear the least significant bit.
1 2 3 4 5 6 7 | int bitSwapRequired(int a, int b) { int count = 0; for (int c = a^b; c != 0; c &= (c - 1)) { count ++; } return count; } |
int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a^b; c != 0; c &= (c - 1)) {
count ++;
}
return count;
}This Bit Manipulation question is often asked in a interview, so it is worth remembering the tricks!
You may also like: C编程练习题：翻转整数位
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Coding Exercise - Add Two Numbers on Singly-Linked List
Next Post: C++ Coding Exercise - Container With Most Water (Recursion)
