바위타는 두루미

문제 정수 A와 정수 B를 2진수로 표현했을 때, A를 B로 바꾸기 위해 뒤집어야 하는 비트의 개수를 구하는 함수를 작성하라 입력 : 29(혹은 11101) , 15( 혹은 01111) 출력 : 2 접근법 두 수의 각각의 비트중에서 다른 비트를 찾아내는 문제이기 때문에 XOR연산을 이용하면 매우 간단하게 풀린다. def bitSwapRequired(a, b): count = 0 c = a^b while c != 0 : count += c & 1 c >>=1 return count 하지만 최하위 비트를 비교해가면서 한칸씩 쉬프트 하는 방법 대신 더 나은 방식을 찾아보자 c & (c-1)을 하면 최하위 비트부터 차례대로 1을 없애 나갈 수 있다. def bitSwapRequired(a,b): count =0..

문제 다음 코드가 하는 일을 설명하여라 ( n & (n-1)) ==0 접근법 이 문제는 거꾸로 접근해가면서 해결할 수 있다. 1. 우선 , A & B==0이 무엇을 의미하는가? - A와 B에서 1비트의 위치가 같은 곳은 없다는 것을 의미한다. 2. n-1은 어떻게 생겼을까? 1011000 - 1 = 1010111 이 된다. 이말은 즉, 가장 오른쪽의 연속된 0들은 모두 1로 변하고 첫번째 1비트가 0으로 바뀐형태를 취한다. 즉 n = abced1000 이면 n-1은 abcde0111 이고 n & (n-1) ==0 가 되려면 abcde는 모두 0이 되어야 하므로 n은 2의 거듭제곱 꼴이여야 저 코드가 참일 것이다. 따라서 n이 2의 거듭제곱꼴인지 확인하는 코드이다.

문제 양의 정수가 하나 주어졌다. 이 숫자를 2진수로 표기했을때 1비트의 개수가 같은 숫자중에서 주어진 수보다 크지만 가장 작은 수와, 작지만 가장 큰 수를 구하여라 . 해결법 이 문제는 두가지 방식으로 풀 수 있다. 원리는 같지만 비트조작으로 하는지, 수학적으로 해결하는지의 차이이다. 우선 비트조작으로 해결하는 것을 살펴보자 - 비트조작으로 다음수 구하기 주어진 수보다 크지만 가장 작은수는 1의 갯수가 같은 다음 수를 의미할 것이다. 그러기 위해서는 0수열로 끝나는 수열이 아닌것 ( 다음에 1수열이 나오는 수열) 중에서 맨 오른쪽 0비트를 1로 뒤집고 , 뒤집은 수 보다 오른쪽에 있는 0과 1을 재정렬해서 0은 전부 왼쪽에 1은 전부 오른쪽에 오도록 하면 가장 작은 수가 될 것이다. 1101100111..