Missing Number

To find the missing number in 1...N

xor1 = XOR of numbers from 1 to N
xor2 = XOR of all given numbers
missing_number = xor1 ^ xor2

Swapping Two Numbers Without a Third Variable

A = A ^ B
B = A ^ B
A = A ^ B

Checking if the i-th Bit is Set (0-based index)

Time Complexity: O(1)

(1 << i) & num → set if result ≠ 0
(num >> i) & 1 → set if result ≠ 0

Setting the i-th Bit

num | (1 << i)

Set the rightmost bit

num | (num + 1)

Clearing the i-th Bit

num & ~(1 << i)

Toggling the i-th Bit

num ^ (1 << i)

Check if a number is power of 2 or not

return n > 0 and (n & (n - 1)) == 0

Count the number of set bits

O(k), where k is the number of set bits (often faster than checking all bits).

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

Divide two integers without using multiplication, division and mod operator (Important)

--->revise Time Complexity: O((logN)^2) – (where N is the absolute value of dividend). The outer loop runs for O(logN) times. The inner loop runs for O(logN) (approx.) times as well.

    def divide(dividend, divisor):
        # Base case
        if dividend == divisor:
            return 1
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
        if divisor == 1:
            return dividend
        # Variable to store the sign of result
        isPositive = True
        # Updating the sign of quotient
        if dividend >= 0 and divisor < 0:
            isPositive = False
        elif dividend < 0 and divisor > 0:
            isPositive = False
        # Storing absolute dividend & divisor
        n,d = abs(dividend),abs(divisor)
        # Variable to store the answer and sum
        ans,sum_ = 0,0
        # Looping while sum added to divisor is less than or equal to divisor
        while sum_ + d <= n:
            # Increment the count
            ans += 1
            # Update the sum
            sum_ += d
        # Handling overflowing condition
        if ans > 2**31 - 1 and isPositive:
            return 2**31 - 1
        if ans > 2**31 - 1 and not isPositive:
            return -2**31
        # Returning the quotient with proper sign
        return ans if isPositive else -1 * ans

Count number of bits to be flipped to convert A to B

    def minBitsFlip(start,goal):
        # Variable to store bits that are different in both numbers
        num=start^goal
        # Variable to count number of set bits
        count = 0
        for i in range(32):
            # Update count if the rightmost bit is set
            count += (num & 1)
            # Shift the number every time by 1 place
            num = num >> 1
        return count

power set

Time Complexity: O(N x 2N)
N is the number of elements in the input array requires O(2N) iterations.For each iteration, we perform O(N) operations to construct the corresponding subset by interpreting the bits of the number.

def subsets(self, nums):
    n=len(nums)
    ts=(1<<n)-1
    flist=[]
    for i in range(ts,-1,-1):
        ans=[]
        for j in range(n):
            if i&(1<<j):
                ans.append(nums[j])
        flist.append(ans)
    return flist

Find XOR of numbers from L to R (O(1))

    def XORtillN(self, n):
        if n % 4 == 1:
            return 1
        if n % 4 == 2:
            return n + 1
        if n % 4 == 3:
            return 0
        return n
    def findRangeXOR(self, l, r):
        return self.XORtillN(l - 1) ^ self.XORtillN(r)