두 배 또는 NOT timer 10s memory 1024MB

시작값인 0 이상의 정수 \mathbf{S}와 목표값인 0 이상의 정수 \mathbf{E}가 주어진다. \mathbf{S}와 \mathbf{E}는 모두 이진수 표현(즉, 2진법 표기)으로 주어진다. 목표는 \mathbf{S}를 \mathbf{E}로 변환하는 것이다. 사용할 수 있는 연산은 다음 두 가지뿐이다:

• 현재 값을 2배로 만든다.
• 현재 값에 비트 단위 NOT(bitwise NOT)을 취한다. 현재 값의 이진수 표현은 불필요한 앞자리 0을 제거한 형태로 취하며, 연산 결과로 생긴 불필요한 앞자리 0도 모두 제거한다. (필요한 앞자리 0은 0의 표현에 있는 것 하나뿐이다.)

예를 들어 2배 연산을 하면 6은 12가 되고, 0은 0이 되며, 10은 20이 된다. NOT 연산을 하면 0은 1이 되고, 1은 0이 되며, 3 = 11_2는 0이 된다. 또한 14=1110_2는 1이 되고, 10=1010_2는 5=101_2가 되며, 5=101_2는 2=10_2가 된다. (X_2는 이진수 표현이 X인 정수를 뜻한다.)

두 연산은 원하는 만큼, 원하는 순서로 사용할 수 있다. 예를 들어 \mathbf{S} = 10001_2를 \mathbf{E} = 111_2로 바꾸려면, NOT 연산을 먼저 한 뒤 2배 연산을 두 번 하고 마지막으로 다시 NOT 연산을 하면 된다: 10001_2 \overset{\text{NOT}}{\Longrightarrow} 1110_2 \overset{\times 2}{\Longrightarrow} 11100_2 \overset{\times 2}{\Longrightarrow} 111000_2 \overset{\text{NOT}}{\Longrightarrow} 111_2.

변환을 완료하는 데 필요한 연산 횟수의 최솟값을 구하라. 만약 불가능하다면 불가능하다고 출력하라.