[LeetCode/Easy] 2220. Minimum Bit Flips to Convert Number

1. Input

1) 정수 start

2) 정수 goal

 

2. Output

1) start에 bit flip을 여러 번 수행해 goal을 만들 때, 필요한 bit flip의 최소 횟수를 반환

- bit flip이란 수를 2진수로 표현한 후 0을 1로, 1을 0으로 바꾸는 것을 말한다.

 

3. Constraint

1) 0 <= start, goal <= 10^9

 

4. Example

Input: start = 10, goal = 7 -> Output: 3

설명: 10 = 1010(2), 7 = 0111(2)

- 앞에서부터 4번째 비트: 1010 -> 1011

- 앞에서부터 2번째 비트: 1011 -> 1111

- 앞에서부터 1번째 비트: 1111 -> 0111

- 따라서 필요한 bit flip의 최소 횟수는 3이다.

 

5. Code

1) 첫 코드(2022/06/14)

String s = Integer.toBinaryString(start);
String g = Integer.toBinaryString(goal);

String p = "";
for(int i=0 ; i<Math.abs(s.length()-g.length()) ; i++)
    p += "0";

if(start > goal)
    g = p + g;
else if(start < goal)
    s = p + s;

int count = 0;
for(int i=0 ; i<s.length() ; i++)
    if(s.charAt(i) != g.charAt(i))
        count++;

return count;

2) 다시 풀어본 코드(2023/01/15)

int answer = 0;
while(start>=1 && goal>=1){
    if(start%2 != goal%2)
        answer++;
    start /= 2; goal /= 2;
}

if(start>=1){
    while(start>=1){
        answer += start%2;
        start /= 2;
    }                
}else{
    while(goal>=1){
        answer += goal%2;
        goal /= 2;
    }
}
return answer;

- 성능이 압도적으로 좋아졌다.