비트 연산 활용.

https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

의 글을 정리함. 파이썬 버전.

1. 숫자를 이진수로 변경했을때 1의 갯수 세기.

def count_one(n):
    count = 0
    while n:
        n = n&(n-1)
        count += 1

    return count

print count_one(3)

2.1 어떤 수가 2의 거듭제곱인지 판단.

2의 거듭제곱들은 이진수로 아래와 같다.

1, 10, 100, 1000, 10000 .... 그리고 이것들보다 1 작은수의 이진수는 아래와 같다.

0, 01, 011, 0111, 01111 ..... 2의 거듭제곱이면 n&(n-1) == 0이어야 함을 만족한다. 아래 조건은 n이 음수인 경우도 있어서 n>0을 적어놨다.

def isPowerOfTwo(self, n):
    return n > 0 and n&(n-1) == 0

2.2 어떤 수가 4의 거듭제곱인지 판단.

앞부분은 바로 위에 적은 2의 거듭제곱이면서, 뒷부분은 0x55555~와 &연산을 했을때 0이 아니어야 한다. 2의 거듭제곱의 경우는 1,10,100,1000인데, 4의 거듭제곱의 경우는 100, 10000이렇게 두개씩 늘어나는데 그걸 걸러내려고 0x55555와 &연산을 하는것 같다.

32비트보다 큰 수의 경우 뒤의 0x55555555를 더 늘려야 한다.

def isPowerOfFour(n):
    return (not (n&(n-1))) and ((n&0x55555555) != 0)

print isPowerOfFour(16)

2.3 어떤 수가 3의 거듭제곱인지 판다.

몰라도 되는거같아서 그냥 링크만 걸어놓음.....

https://leetcode.com/problems/power-of-three/discuss/77977/Math-1-liner-no-log-with-explanation

3. ^만으로 합 구하기. c와 파이썬의 shift(<<)동작이 달라서 아래처럼 구현해야한다고 댓글에 써있음.

https://stackoverflow.com/questions/39113479/infinite-loop-while-adding-two-integers-using-bitwise-operations-in-python-3

def getSum(a, b):
    mask = 0xFFFFFFFF
    while not b == 0:
        carry = a & b
        a = (a ^ b) & mask
        b = (carry << 1) & mask

    if a > 2 ** 31:
        return ~(a ^ mask)

    else:
        return a
print getSum(4,5)

4. 1~n중에 빠진 숫자 찾기.

같은수를 두번 xor하면 0이 되는 성질을 이용한다.

def missingNumber(nums):
    ret = 0
    for i in xrange(len(nums)):
        ret ^= i
        ret ^= nums[i]
    return ret^len(nums)

print missingNumber([0,1,3])

5. |로 가장 많은 비트 저장하기.

n보다 작은 2의 거듭제곱중 가장 큰 수 구하기.

def largest_power(N):
    N = N | (N>>1)
    N = N | (N>>2)
    N = N | (N>>4)
    N = N | (N>>8)
    N = N | (N>>16)
    return (N+1)>>1

print largest_power(15)

6. 비트를 거꾸로 뒤집기.

def reverseBits(n):
    mask = 1
    ret = 0
    for i in xrange(32):  # 32비트 기준
        ret <<= 1
        if (mask&n):
            ret = ret | 1
        mask <<= 1
    return ret

print reverseBits(1)

7. & tricks -> 이건 이해가 안가서 안적음.

8. 범위 내의 모든 수를 &연산한 값. 5,7을 넣으면 5&6&7의 값.

def rangeBitwiseAnd(m, n):
    a = 0
    while m != n:
        m >>= 1
        n >>= 1
        a += 1
    return m<<a

이외에 저 링크의 아래부분에 비트로 푸는 문제들에 대한 추가 예시가 있음.