Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A bit must be flipped exactly when start and goal differ in that position.
  2. 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));
    }
}

Solve Minimum Bit Flips online · All practice problems