알고리즘 - Python 비트연산 활용하기

신찬수, 한국외대, 컴퓨터공학부, 2021, 비트연산, Bit Manipulation, Python
생각해 볼 문제 두 가지 더~ 생각하는 답이 있으면 댓슬에 남겨주세요~^^
예제문제 4: 양의 정수 n을 입력받아 n보다 크거나 같은 수 중에서 가장 작은 2^k 값을 계산하시오.
예제문제 5: 앞면/뒷면이 나올 확률이 각각 1/2인 동전 하나를 여러 번 던져 1부터 6까지의 주사위의 눈을 각각 1/6의 확률로 랜덤 생성하는 방법은?

[@wooooya]

4번에 대해 생각한 답은 아래와 같습니다. 혹시 n이 2^k이 아니어서 else문에 걸렸을 때, O(logN) 말고 더 효율적인 방법으로 답을 도출해낼 수 있을까요? def solution(n): if n & (n-1) == 0: return n else: k = 0 while n: k += 1 n = n >> 1 return 2 ** k 그리고 혹시 실례가 되지 않는다면 출처를 밝히고 해당 영상에 있는 내용을 바탕으로 블로그 글을 게재해도 괜찮을까요, 교수님? 영상 늘 잘 보고 있습니다. 감사합니다!

[@ChanSuShin]

정확한 코드네요. ^^ 더 효율적인 방법은 힘들어보입니다. 출처를 밝히면 링크 거셔도 됩니다.

[@wooooya]

@@ChanSuShin 답글 감사드립니다, 교수님!

[@mindolll]

def solution(n): if n & (n - 1) == 0: return n while (n & (n - 1) != 0): n &= (n - 1) return n * 2 while문을 이렇게 바꾸면 이진수에서 1의 개수만큼만 연산하도록 줄일 수 있을 것 같습니다.

[@ChanSuShin]

@@mindolll good job! O(1의 개수) 시간이면 되는 방법이네요^^