Count Bits to Convert A to B
Solve this Problem
Given two non-negative integers
a and b, count how many bit positions need to be flipped to turn a into b.
A bit position needs flipping exactly where a and b disagree — and XOR is built to flag exactly that: a ^ b has a 1 in every position where the two numbers differ, and a 0 everywhere they agree. Counting the set bits in that XOR result, the same set-bit-counting trick used earlier, gives the answer directly.
Test Case 1:
Input:a = 10, b = 20
Output:4
Explanation:10 = 01010, 20 = 10100 — they differ in 4 bit positions.
Test Case 2:
Input:a = 0, b = 0
Output:0
Explanation:Identical numbers need no bits flipped.
Test Case 3:
Input:a = 7, b = 8
Output:4
Explanation:7 = 0111, 8 = 1000 — every one of the 4 low bits differs.
Constraints
- ◆
0 ≤ a, b ≤ 2³¹ − 1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compare Each of 32 Bits
BruteWalk all 32 bit positions and count how many of them differ between a and b.
Time
O(32)Space
O(1)Java
1class Solution {
2 public int countBitsToConvert(int a, int b) {
3 int count = 0;
4 for (int bit = 0; bit < 32; bit++) {
5 int bitA = (a >>> bit) & 1;
6 int bitB = (b >>> bit) & 1;
7 if (bitA != bitB) {
8 count++;
9 }
10 }
11 return count;
12 }
13}Optimal — XOR and Count Set Bits
OptimalA bit position needs flipping exactly where a and b disagree — and XOR is built to flag exactly that: a ^ b has a 1 in every position where the two numbers differ, and a 0 everywhere they agree. Counting the set bits in that XOR result, using the same Brian Kernighan trick from counting set bits, gives the answer directly.
Time
O(number of differing bits)Space
O(1)Java
1class Solution {
2 public int countBitsToConvert(int a, int b) {
3 int diff = a ^ b;
4 int count = 0;
5 while (diff != 0) {
6 diff = diff & (diff - 1);
7 count++;
8 }
9 return count;
10 }
11}