bit_manipulation.py

BM 1. Single Number: You are given a non-empty array of integers nums. Every integer appears twice except for one.
Return the integer that appears only once.
You must implement a solution with O(n)O(n) runtime complexity and use only O(1)O(1) extra space.

#Solution
def singleNumber(self, nums: List[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

BM 2: You are given an unsigned integer n. Return the number of 1 bits in its binary representation.
You may assume n is a non-negative integer which fits within 32-bits.

#Solution
def hammingWeight(self, n: int) -> int:
    count = 0
    for i in range(32):
        if n & (1 << i) > 0:
            count += 1
    return count 

def hammingWeight(self, n: int) -> int:
    c = 0
    while n:
        c += 1 if n & 1 else 0
        n >>= 1
    return c

BM 3: Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].
Return an array output where output[i] is the number of 1's in the binary representation of i.
#Solution
def countBits(self, n: int) -> List[int]:
    offset = 1
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        if offset * 2 == i:
            offset *= 2

        dp[i] = 1 + dp[i - offset]
    return dp