Practice › Bit Manipulation
Minimum Bit Flips
Easy · Bit Manipulation · Asked at Amazon, Microsoft, TCS, Infosys
A bit flip changes one bit of a number from 0 to 1 or from 1 to 0. Print the minimum number of bit flips to convert start into goal.
Input
A single line: start goal.
Output
The number of flips.
Constraints
- 0 ≤ start, goal ≤ 10^9
The bits that differ are exactly the 1-bits of start XOR goal — count them.
Example 1
Input
10 7
Output
3
Example 2
Input
3 4
Output
3
Hints
- A bit must be flipped exactly when start and goal differ in that position.
- XOR marks the differing positions with 1s — count them.
Approach
x = start ^ goal has a 1 wherever the numbers differ. Count its set bits: either loop and test the lowest bit, or use Kernighan's trick x &= x − 1 (removes one set bit per step), or the built-in popcount.
Complexity: O(number of bits) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
long long x = a ^ b;
int count = 0;
while (x) {
x &= x - 1; // drop the lowest set bit
count++;
}
cout << count << "\n";
return 0;
}Python solution
a, b = map(int, input().split())
print(bin(a ^ b).count("1"))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong(), b = sc.nextLong();
System.out.println(Long.bitCount(a ^ b));
}
}