[LeetCode] 2220. Minimum Bit Flips to Convert Number

https://leetcode.com/problems/minimum-bit-flips-to-convert-number/description/?envType=daily-question&envId=2024-09-11

leetcode - Minimum Bit Flips to Convert Number

문제 유형 : 비트마스킹

문제 난이도 : Easy

 

문제

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

• For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

 

비트 반전은 숫자 x에서 한 비트를 골라서 0 -> 1 또는 1 -> 0을 행하는 작업을 말한다.

두 정수 start와 goal이 주어지는데, start에서 goal로 만들기 위한 비트반전의 수를 구하시오.

 

풀이

두 비트를 xor하면 서로가 다르게 가지고 있는 자리의 비트만 1이 된다.

이 수의 이진 표현에서의 1의 개수를 구하면 된다.

 

코드

C++

class Solution {
public:
    int minBitFlips(int start, int goal) {
        int x = start ^ goal;
        int ans = 0;
        while(x > 0) {
            ans += x%2;
            x /= 2;
        }

        return ans;
    }
};

GO

func minBitFlips(start int, goal int) int {
    x := start ^ goal
    ans := 0

    for x > 0 {
        ans += x % 2
        x /= 2
    }

    return ans
}