Bit Manipulation

TODO: use bitmap word rather than bitmask ADD ============================== TODO: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/description/

In the context of binary operations and numbers in programming, n, -n, and ~n have specific meanings:

1. n: This is a variable representing a number. In binary operations, n is usually considered in its binary form. For example, if n = 5, its binary representation is 101 in a simple binary system.

2. -n: This represents the negative of the number n. In most programming languages, including Python, -n is calculated using two’s complement notation. However, when you print -n using functions like print() or bin(), they show a - sign followed by the binary representation of the absolute value of n, rather than the actual two’s complement binary form.

3. ~n: This represents the bitwise NOT operation applied to n. In binary terms, bitwise NOT flips every bit of n. In two’s complement (which is used by most modern computers for representing signed integers), ~n is equivalent to -(n + 1). For example, if n = 5 (101 in binary), ~n will flip all bits resulting in … 11111010 in a system with more than 3 bits (like an 8-bit system). This result is the two’s complement representation of -6.

   • Why -6? In two’s complement, ~n is the same as -(n + 1). So, ~5 is -(5 + 1), which equals -6.

TODO: More : https://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

Foundational Techniques

Negating Bits in a Number

Bit LengthWhile Loop for Bitmask

Solution

~num is equivalent to negate_bits(num). In Python, integers are of arbitrary size and the bitwise NOT operation (~) on a non-negative integer results in a negative value due to two’s complement representation.

The function negate_bits is designed to invert all bits of a given integer num. This operation effectively computes the bitwise NOT of num, adjusted for a specific number of bits determined by num itself. Note that for some problem, you have to specifically mention the max_bits such as len(nums)

The key steps involved in this function are:

• Determine the number of bits needed to represent num in binary.

• Create a bitmask of all 1s with length equal to the number of bits calculated.

• Perform a bitwise XOR between num and the bitmask to invert num’s bits.

Warning

This code will not work for 0, since python gives bit_length of 0 as 0. Hence the answer would also be 0. But the other solution will work for 0 too.

Detailed Examples

1. negate_bits(5):

   • Binary representation of 5: 101.

   • bit_length = 3, bitmask = 111.

   • XOR-ing 5 with the mask: 101 ^ 111 = 010.

   • The negated bits represent the number 2.

2. negate_bits(2):

   • Binary representation of 2: 10.

   • bit_length = 2, bitmask = 11.

   • XOR-ing 2 with the mask: 10 ^ 11 = 01.

   • The negated bits represent the number 1.

3. negate_bits(21):

   • Binary representation of 21: 10101.

   • bit_length = 5, bitmask = 11111.

   • XOR-ing 21 with the mask: 10101 ^ 11111 = 01010.

   • The negated bits represent the number 10.

Analysis

Time Complexity: O(log(n))

bit_length calculation depends on the number of bits given number has.

Space Complexity: O(1)

Python

def negate_bits(num: int) -> int:
    bit_length = num.bit_length()
    bitmask = (1 << bit_length) - 1  # binary with all 1's
    return num ^ bitmask

Determining if the Least Significant Bit (LSB) is Set (Odd/Even Numbers)

Solution

The function check_least_significant_bit is designed to determine if the least significant bit (LSB) of an integer is set.

Understanding the LSB:

• In binary, each digit represents a power of 2. The rightmost bit (LSB) represents (2^0), which is 1.

• If the LSB is 1, it means the number is odd. If it’s 0, the number is even.

The bitwise AND operation & is used to compare the LSB of the number with 1. If the result is 1, the LSB is set (i.e., the number is odd).

Detailed Examples

1. check_least_significant_bit(4):

   • Binary representation of 4: 100.

   • Performing 4 & 1: 100 & 001 = 000 (result is 0).

   • The LSB is not set. The function returns False.

2. check_least_significant_bit(5):

   • Binary representation of 5: 101.

   • Performing 5 & 1: 101 & 001 = 001 (result is 1).

   • The LSB is set. The function returns True.

3. check_least_significant_bit(0):

   • Binary representation of 0: 000.

   • Performing 0 & 1: 000 & 001 = 000 (result is 0).

   • The LSB is not set. The function returns False.

4. check_least_significant_bit(-2):

   • In two’s complement, binary of -2 in a 32-bit system: 11111111111111111111111111111110.

   • Performing -2 & 1: … 11111110 & 00000001 = 00000000 (result is 0).

   • The LSB is not set. The function returns False.

Analysis

Time Complexity: O(1)

The operation involves a single bitwise AND, executed in constant time, regardless of input size.

Space Complexity: O(1)

The function’s space complexity is constant as it doesn’t allocate additional space based on input size.

Python

def check_least_significant_bit(n: int) -> bool:
    return n & 1 == 1

Unsetting the Least Significant (Rightmost) Set (1) Bit - Brian Kerninghan’s Algorithm

Solution

The function unset_least_significant_bit is designed to turn off (unset) the least significant bit (LSB) of an integer.

In binary numbers, unsetting the LSB means changing the rightmost bit from 1 to 0. This operation can be performed using the bitwise AND operation with the number minus 1. The expression n & (n - 1) unsets the LSB of n.

Detailed Examples

1. unset_least_significant_bit(5):

   • Binary representation of 5: 101.

   • Performing 5 & (5 - 1): 101 & 100 = 100 (result is 4).

   • The LSB is unset. The function returns 4.

2. unset_least_significant_bit(22):

   • Binary representation of 22: 010110.

   • Performing 22 & (22 - 1): 010110 & 010101 = 010100 (result is 20).

   • The LSB is unset. The function returns 20.

3. unset_least_significant_bit(63):

   • Binary representation of 63: 111111.

   • Performing 63 & (63 - 1): 111111 & 111110 = 111110 (result is 62).

   • The LSB is unset. The function returns 62.

4. unset_least_significant_bit(64):

   • Binary representation of 64: 1000000.

   • Performing 64 & (64 - 1): 1000000 & 0111111 = 0000000 (result is 0).

   • The LSB is unset. The function returns 0.

Analysis

Time Complexity: O(1)

The operation involves a single bitwise AND, executed in constant time, regardless of input size.

Space Complexity: O(1)

The function’s space complexity is constant as it doesn’t allocate additional space based on input size.

Python

def unset_least_significant_bit(n: int) -> int:
    return n & (n - 1)

Get/Isolate the Least Significant (Rightmost) Set (1) Bit

Solution

The operation x & -x isolates the least significant set bit of an integer x. Basically, this works because of two’s complement. In two’s complement notation -x is the same as ~x + 1. In other words, to compute -x, one has to revert all bits in x and then add 1 to the result.

Adding 1 to ~x in binary representation means to carry that 1-bit till the rightmost 0-bit in ~x and to set all the lower bits to zero. Note, that the rightmost 0-bit ~x corresponds to the rightmost 1-bit in x .

In summary, -x is the same as ~x + 1. This operation reverts all bits of x except the rightmost 1-bit, in turn isolating it.

Example:

1. With x = 8 (00001000)

   • ~x is 11110111

   • -8 which is ~x + 1 is 11111000

   • 8 & -8 gives 00001000 (8)

2. With x = 7 (00000111)

   • ~x is 11111000

   • -7 which is ~x + 1 is 11111001

   • 7 & -7 gives 00000001 (1)

3. With x = 6 (00000110)

   • ~x is 11111001

   • -6 which is ~x + 1 is 11111010

   • 6 & -6 gives 00000010 (2)

Analysis

Time Complexity: O(1)

The function isolate_least_significant_set_bit performs a single bitwise AND operation between x and -x. This operation does not depend on the size of the number and is executed in constant time. Therefore, the time complexity is O(1).

Space Complexity: O(1)

This function uses a fixed amount of space. It does not require any additional memory that grows with the size of the input, as it only stores the result of the bitwise AND operation. Hence, the space complexity is also O(1).

Python

def isolate_least_significant_set_bit(x: int) -> int:
    return x & -x

Reverse Bits of a Given 32 Bits Unsigned Integer

Solution

The function reverseBits reverses the bits of a 32-bit unsigned integer. This complex operation involves several steps, each using bitwise AND, shifts, and OR operations to manipulate and rearrange the bits.

The process:

• First, the number is split into two 16-bit blocks and swapped.

• Then, each 16-bit block is divided into two 8-bit blocks and swapped.

• This process is repeated for 4-bit, 2-bit, and 1-bit blocks.

By progressively breaking down the number into smaller blocks and swapping them, the bits are effectively reversed.

Step-by-Step Explanation with an Example: (reverseBits(43261596))

Initial number: 43261596 (in binary: 00000010100101000001111010011100).

1. 16-bit swap:

   • Right shift by 16: 0000001010010100 (isolate the first 16 bits).

   • Left shift by 16: 00001111010011100000000000000000 (isolate the last 16 bits and shift).

   • Bitwise OR of the two: 00001111010011100000001010010100.

2. 8-bit swap within each 16-bit block:

   • Right shift by 8: 0000111101001110 and 0000000101001010.

   • Left shift by 8: 1001110000000000 and 0101001000000000.

   • Bitwise OR of the two: 1001110101001000 and 0101001000001010.

   • Combine: 10011101010010000101001000001010.

3. 4-bit swap within each 8-bit block:

   • Apply a similar process using 4-bit masks and 4-bit shifts.

4. 2-bit swap within each 4-bit block:

   • Apply a similar process using 2-bit masks and 2-bit shifts.

5. 1-bit swap within each 2-bit block:

   • Apply a similar process using 1-bit masks and 1-bit shifts.

   • Final result: 00111001011110000010100101000000 (in decimal: 964176192).

Each step uses bitwise masks to isolate relevant bits and shifts them into their new positions.

Analysis

Time Complexity: O(1)

The function consists of a fixed number of steps and operations, irrespective of the input size, resulting in constant time complexity.

Space Complexity: O(1)

The function uses a fixed amount of space, only manipulating the given input without additional memory allocation.

Python

def reverseBits(self, n):
    n = ((n & 0b11111111111111111111111111111111) >> 16) | (
        (n & 0b11111111111111111111111111111111) << 16
    )
    n = ((n & 0b11111111000000001111111100000000) >> 8) | (
        (n & 0b00000000111111110000000011111111) << 8
    )
    n = ((n & 0b11110000111100001111000011110000) >> 4) | (
        (n & 0b00001111000011110000111100001111) << 4
    )
    n = ((n & 0b11001100110011001100110011001100) >> 2) | (
        (n & 0b00110011001100110011001100110011) << 2
    )
    n = ((n & 0b10101010101010101010101010101010) >> 1) | (
        (n & 0b01010101010101010101010101010101) << 1
    )
    return n

Swapping Two Variables

Solution

The function swap_nums demonstrates a method to swap the values of two variables, a and b, without using a temporary variable. It employs the XOR (^) bitwise operation, which has the unique property that an element XORed with itself is zero, and any element XORed with zero is the element itself.

Steps Explained:

1. a = a ^ b: XORs a and b, storing the result in a. This result is effectively the combined information of a and b.

2. b = b ^ a: Now, XORing b with the new a (which is a ^ b) will cancel out the original a (since a ^ a = 0), leaving only b, which gets stored in b.

3. a = a ^ b: Similarly, XORing the new a (which is a ^ b) with the new b (which is now the original a) cancels out the original b, leaving a with the value of the original b.

Detailed Example Explanation:

Consider swapping a = 5 (binary 101) and b = 3 (binary 011):

• After the first step (a = a ^ b), a becomes 110 (binary for 6), which is the XOR of 101 and 011.

• After the second step (b = b ^ a), b becomes 101 (binary for 5), which is the original value of a.

• After the third step (a = a ^ b), a becomes 011 (binary for 3), which is the original value of b.

Thus, a and b have been successfully swapped.

Analysis

Time Complexity: O(1)

The swap operation consists of three XOR assignments, each executed in constant time, resulting in an overall time complexity of O(1).

Space Complexity: O(1)

No additional space is used, as the swap is performed in-place with the original variables.

Python

def swap_nums(a, b):
    a = a ^ b
    b = b ^ a
    a = a ^ b
    return a, b

Trivial Ops

476. Number Complement (Easy)

Bit by BitBitmask of 1’s

Python

def bitwiseComplement(self, n: int) -> int:
    if n == 0:
        return 1
    negation = 0
    for pos in range(n.bit_length() - 1, -1, -1):
        bit = n & (1 << pos) == 0
        negation = (negation << 1) | bit
    return negation

1009. Complement of Base 10 Integer (Easy)

Solution

This question is same as 476. Number Complement (Easy).

Python

def bitwiseComplement(self, n: int) -> int:
    bitmask = 1
    while bitmask < n:
        bitmask = bitmask << 1 | 1
    return n ^ bitmask

190. Reverse Bits (Easy)

Bit by Bit5 Ops - Mask and Shift

Solution

The function reverseBits reverses the bits of a given 32-bit unsigned integer. It iterates through each bit of the number, shifting the accumulated result to make room for the next bit and then adding the least significant bit of the input number. This process is repeated for all 32 bits of the integer, effectively reversing the bit order.

Analysis

Time Complexity: O(1)

The function iterates a fixed number of times (32 iterations for a 32-bit number), and each operation within the loop is executed in constant time. Hence, the overall time complexity is O(1), as it does not depend on the input size but rather on the fixed bit size of the input.

Space Complexity: O(1)

The space complexity is also constant, as the function only uses a fixed amount of additional space to store the reversed number.

Python

def reverseBits(self, n: int) -> int:
    r = 0
    for i in range(32):
        r = (r << 1) | (n & 1)
        n >>= 1
    return r

1486. XOR Operation in an Array (Easy)

Python

def xorOperation(self, n: int, start: int) -> int:
    xor = start
    for i in range(1, n):
        xor = xor ^ (start + 2 * i)
    return xor

1720. Decode XORed Array (Easy)

Python

def decode(self, encoded: List[int], first: int) -> List[int]:
    ans = [first]
    for i in encoded:
        ans.append(ans[-1] ^ i)
    return ans

2433. Find The Original Array of Prefix Xor (Medium)

Python

def findArray(self, pref: List[int]) -> List[int]:
    ans = [pref[0]]
    for i in range(1, len(pref)):
        ans.append(pref[i - 1] ^ pref[i])
    return ans

1829. Maximum XOR for Each Query (Medium)

Python

def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
    xor = 0
    ans = []
    for i in nums:
        xor = xor ^ i
        ans.insert(0, xor ^ (2**maximumBit - 1))
    return ans

2932. Maximum Strong Pair XOR I (Easy)

Python

def maximumStrongPairXor(self, nums: List[int]) -> int:
    maxi = 0
    for i in nums:
        for j in nums:
            if abs(i - j) <= min(i, j):
                maxi = max(maxi, i ^ j)
    return maxi

Count 1-Bits

191. Number of 1 Bits (Easy)

Check LSBUnset LS 1-Bit

Solution

The hammingWeight function calculates the number of set bits (1s) in the binary representation of an integer. This count is known as the Hamming weight. The function iterates through each bit of the number and checks if each bit is set.

Example: Calculating Hamming Weight of 13

• The binary representation of 13 is 1101.

• We start with a counter bits set to 0. Then, we check each bit from right to left.

  • First bit (rightmost): 1 & 1 equals 1. Counter bits becomes 1.

  • Second bit: 1 & 0 (after right shifting 1 3 >> 1 gives 110 which is 6) equals 0. Counter bits remains 1.

  • Third bit: 1 & 1 (now 6 >> 1 gives 11 which is 3) equals 1. Counter bits becomes 2.

  • Fourth bit: 1 & 1 (now 3 >> 1 gives 1) equals 1. Counter bits becomes 3.

• After checking all the bits, the counter bits is 3, which is the total number of set bits in 13.

Therefore, hammingWeight(13) returns 2 .

Analysis

Time Complexity: O(1)

The run time depends on the number of bits in n. Because n in this piece of code is a 32-bit integer, the time complexity is O(1).

To be precise, the loop will stop on the most significant bit (MSB), and at this iteration the n will be 0.

Space Complexity: O(1)

Since no additional space is allocated.

Python

def hammingWeight(self, n: int) -> int:
    """Loop"""
    bits = 0
    while n != 0:
        if n & 1:  # Check if the least significant bit is set or not
            bits += 1
        n >>= 1
    return bits

2595. Number of Even and Odd Bits (Easy)

Python

def evenOddBit(self, n: int) -> List[int]:
    even = odd = 0
    pos = 0
    while n != 0:
        if n & 1:  # Check if the least significant bit is set or not
            if pos % 2:
                odd += 1
            else:
                even += 1
        pos += 1
        n >>= 1
    return [even, odd]

2859. Sum of Values at Indices With K Set Bits (Easy)

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
    total = 0
    for i, n in enumerate(nums):
        if self.hammingWeight(i) == k:
            total += n
    return total

1356. Sort Integers by The Number of 1 Bits (Easy)

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def sortByBits(self, arr: List[int]) -> List[int]:
    return sorted(arr, key=lambda i: (self.hammingWeight(i), i))

2657. Find the Prefix Common Array of Two Arrays (Medium)

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
    bitmap_a = bitmap_b = 0
    ans = []
    for i in range(len(A)):
        bitmap_a = bitmap_a | (1 << A[i])
        bitmap_b = bitmap_b | (1 << B[i])
        ans.append(self.hammingWeight(bitmap_a & bitmap_b))
    return ans

461. Hamming Distance (Easy)

Solution

Recommended prerequisite: 191. Number of 1 Bits (Easy).

The Hamming distance between two integer numbers is the number of positions at which the corresponding bits are different.

Given the above definition, it might remind one of the bit operation called XOR which outputs 1 if and only if the input bits are different.

As a result, in order to measure the hamming distance between x and y, we can first do x XOR y operation, then we simply count the number of bit 1 in the result of XOR operation.

Analysis

Time Complexity: O(1)

The run time depends on the number of 1-bits in n. In the worst case, all bits in n are 1-bits. In case of a 32-bit integer, the run time is O(1).

Space Complexity: O(1)

Since no additional space is allocated.

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def hammingDistance(self, x: int, y: int) -> int:
    xor = x ^ y
    return self.hammingWeight(xor)

2220. Minimum Bit Flips to Convert Number (Easy)

Solution

Task is to find the hamming distance. Refer 461. Hamming Distance (Easy).

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def minBitFlips(self, start: int, goal: int) -> int:
    xor = start ^ goal
    return self.hammingWeight(xor)

2997. Minimum Number of Operations to Make Array XOR Equal to K (Medium)

Solution

Task is to find the hamming distance. Refer 461. Hamming Distance (Easy).

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def minOperations(self, nums: List[int], k: int) -> int:
    xor = 0
    for i in nums:
        xor = xor ^ i
    return self.hammingWeight(xor ^ k)

1318. Minimum Flips to Make a OR b Equal to c (Medium)

Using Hamming WeightBit by Bit

Solution

Prerequisite: 461. Hamming Distance (Easy).

The problem is asking us to have a | b equal to c. If we do (a | b) ^ c, then every bit that is different (and thus we need to flip) will have a value of 1. Therefore we can just do (a | b) ^ c and count the bits that are set.

However, there is one exception, which is when (c & 1) = 0 and both a & 1 and b & 1 equal 1. In this case, we need an additional flip. To find all these cases, we also need to identify all the bits where both A and b are equal to 1.

Analysis

Time Complexity: O(log(n))

To find the hamming weight.

Space Complexity: O(1)

Python

def hammingWeight(self, n: int) -> int:
    bits = 0
    while n != 0:
        n = n & (n - 1)  # Unset the lowest set bit
        bits += 1
    return bits


def minFlips(self, a: int, b: int, c: int) -> int:
    # a b  a|b  a&b  c  steps
    # 0 0  |=0  &=0  0  =0
    # 0 0  |=0  &=0  1  =1
    # 1 0  |=1  &=0  0  =1
    # 1 0  |=1  &=0  1  =0
    # 1 1  |=1  &=1  0  =2 <<- (+1); can be found when AND=1 and c=0
    # 1 1  |=1  &=1  1  =0                  ----vvvvvvvvvvvvvvvv----
    return self.hammingWeight((a | b) ^ c) + self.hammingWeight((a & b) & ((a | b) ^ c))

TODO - 477. Total Hamming Distance (Medium)

LS 1-Bit

231. Power of Two (Easy)

Unset LS 1-BitIsolate LS 1-Bit

Solution

The solution is straightforward:

1. Power of two has just one 1-bit.

2. x & (x - 1) sets this 1-bit to zero, and hence one has to verify if the result is zero x & (x - 1) == 0.

Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Python

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

342. Power of Four (Easy)

Solution

Let’s first check if num is a power of two: x > 0 and x & (x - 1) == 0.

Now the problem is to distinguish between even powers of two (when x is a power of four) and odd powers of two (when x is not a power of four). In binary representation both cases are single 1-bit followed by zeros.

Hence power of four would make a zero in a bitwise AND with number 0b10101010101010101010101010101010.

Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Python

def isPowerOfFour(self, n: int) -> bool:
    return (
        (n > 0) and (n & (n - 1) == 0) and (n & 0b10101010101010101010101010101010 == 0)
    )

LSB - Loop

2980. Check if Bitwise OR Has Trailing Zeros (Easy)

Python

def hasTrailingZeros(self, nums: List[int]) -> bool:
    evens = 0
    for i in nums:
        if i & 1 == 0:
            evens += 1
        if evens >= 2:
            return True
    return False

868. Binary Gap (Easy)

Python

def binaryGap(self, n: int) -> int:
    last_pos = None
    pos = 0
    maxi = 0
    while n:
        if n & 1:
            if last_pos is not None:
                maxi = max(maxi, pos - last_pos)
            last_pos = pos
        n = n >> 1
        pos += 1
    return maxi

1342. Number of Steps to Reduce a Number to Zero (Easy)

Python

def numberOfSteps(self, num: int) -> int:
    steps = 0
    while num:
        if num & 1:
            steps += 1
        steps += 1
        num = num >> 1
    return steps - 1 if steps else 0

XOR - Cancel Bits

136. Single Number (Easy)

XORBitmask & Log2

Solution

The singleNumber() function identifies the unique number in a list where every other number appears exactly twice. It leverages the property of XOR operation:

• commutative and associative

• If we take XOR of zero and some bit, it will return that bit:

  \[a \oplus 0 = a\]

• If we take XOR of two same bits, it will return 0

  \[a \oplus a = 0\]

Hence,

\[a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b\]

Examples and Step by Step Explanation:

Example 1:

• Input: [2, 2, 1]

• Process:

  • Start with xor = 0.

  • Iterate through the list: 2 ^ 2 ^ 1.

  • 2 ^ 2 is 0, and 0 ^ 1 is 1. So, we are left with 1.

• Output: 1

Example 2:

• Input: [4, 1, 2, 1, 2]

• Process:

  • Start with xor = 0.

  • Iterate through the list: 4 ^ 1 ^ 2 ^ 1 ^ 2.

  • After all operations, we are left with 4 since all pairs cancel out.

• Output: 4

This approach effectively finds the unique number by canceling out all pairs of numbers.

Analysis

Time Complexity: O(n)

The function iterates once through the list of n numbers, performing an XOR operation for each. Thus, the time complexity is linear.

Space Complexity: O(1)

Only a single additional variable (xor) is used, which occupies constant space, regardless of the input size.

Python

def singleNumber(self, nums: List[int]) -> int:
    xor = 0
    for number in nums:
        xor = xor ^ number
    return xor

540. Single Element in a Sorted Array (Medium)

Solution

Refer 136. Single Number (Easy).

Python

def singleNonDuplicate(self, nums: List[int]) -> int:
    xor = 0
    for number in nums:
        xor = xor ^ number
    return xor

268. Missing Number (Easy)

Also

• Missing in Array (Easy)

XORBitmask & Log2One Pass

Solution

The missingNumber function finds the missing number in an array containing n distinct numbers taken from 0, 1, 2, ..., n, utilizing the XOR operation’s properties. Since XOR of a number with itself is 0, and XOR of a number with 0 is the number itself, XORing all indices and their corresponding values together with n isolates the missing number because it won’t be canceled out.

Index	0	1	2	3
Value	0	1	3	4

\[\begin{split}\begin{align*} \text{missing} &= 4 \oplus (0 \oplus 0) \oplus (1 \oplus 1) \oplus (2 \oplus 3) \oplus (3 \oplus 4) \\ &= (4 \oplus 4) \oplus (0 \oplus 0) \oplus (1 \oplus 1) \oplus (3 \oplus 3) \oplus 2 \\ &= 0 \oplus 0 \oplus 0 \oplus 0 \oplus 2 \\ &= 2 \end{align*}\end{split}\]

Examples and Step by Step Explanation:

Example 1:

• Input: [3, 0, 1]

• Process:

  • Initialize xor with n (length of nums), which is 3.

  • Iterate over the array: xor = 3 ^ (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1) (index ^ nums[index] for each index).

  • Simplified, this cancels out all but 2.

• Output: The missing number is 2.

Example 2:

• Input: [0, 1]

• Process:

  • Initialize xor with n (2).

  • Iterate over the array: xor = 2 ^ (0 ^ 0) ^ (1 ^ 1).

  • This simplifies to 2, indicating it’s the missing number.

• Output: 2.

Example 3:

• Input: [9, 6, 4, 2, 3, 5, 7, 0, 1]

• Process:

  • Initialize xor with n (9).

  • Iterate and XOR all indices and values: ends up isolating 8 as it’s not canceled.

• Output: 8.

Analysis

Time Complexity: O(n)

The function iterates once over the array of size n to perform XOR operations, resulting in linear time complexity.

Space Complexity: O(1)

No additional space is used besides the variable for the cumulative XOR operation, ensuring constant space complexity.

Python

def missingNumber(self, nums: List[int]) -> int:
    xor = len(nums)
    for index in range(len(nums)):
        xor = xor ^ index ^ nums[index]
    return xor

389. Find the Difference (Easy)

XORBitmask & Log2

Solution

The function findTheDifference finds the character that was added to string t, which is a shuffled version of string s plus one additional character. It uses the XOR operation to identify the added character by leveraging the property that a ^ a = 0 and a ^ 0 = a. XORing all characters in both strings s and t cancels out the common characters and leaves the added character.

Examples and Step by Step Explanation:

• Input: s = "abcd", t = "abcde"

  • XOR all characters in s and then XOR all characters in t. The common characters in s and t will cancel out, leaving the XOR value as the ASCII code of the added character ‘e’.

  • The final XOR result represents the ASCII value of ‘e’. Using chr(xor), we find the character ‘e’ as the difference.

• Input: s = "", t = "y"

  • Since s is empty, XOR-ing its characters has no effect on the initial xor value of 0.

  • XOR-ing the character ‘y’ from t with 0 results in the ASCII value of ‘y’.

  • The final XOR result is the ASCII value of ‘y’, and chr(xor) returns ‘y’ as the added character.

Analysis

Time Complexity: O(n)

The time complexity is O(n) where n is the length of the longer string (t), as the function iterates through each character of both strings exactly once.

Space Complexity: O(1)

The space complexity is O(1) as the solution uses a fixed amount of space, regardless of the input size.

Python

def findTheDifference(self, s: str, t: str) -> str:
    xor = 0
    for char in s:
        xor = xor ^ ord(char)
    for char in t:
        xor = xor ^ ord(char)
    return chr(xor)

Bitmask - Palindrome

266. Palindrome Permutation (Easy)

Solution

A palindrome is a string that reads the same forwards and backwards, like “radar” or “level”. In terms of character counts, a string can be permuted to a palindrome if at most one character occurs an odd number of times, and all other characters occur an even number of times

The canPermutePalindrome function checks whether a given string can be rearranged to form a palindrome. It uses a bitmask to track the odd or even count of each character in the string.

Here’s how the function works:

1. Bitmask Creation: The function uses an integer bitmask as a compact way to store whether the count of each character is odd or even.

2. Iterating Over Characters: For each character in the string, it calculates 1 << (ord(char) - ord("a")). This expression creates a number with a single bit set corresponding to the character (assuming all characters are lowercase).

3. XOR Operation: The function then performs an XOR operation ^ with the bitmask. This operation toggles the bit corresponding to the character. If a character appears an even number of times, its bit will end up as 0; if it appears an odd number of times, its bit will be 1.

4. Checking Palindrome Condition: Finally, bitmask & (bitmask - 1) checks if at most one bit in the bitmask is set. This operation returns 0 if and only if bitmask is 0 (no characters appear an odd number of times) or a power of 2 (exactly one character appears an odd number of times).

Detailed Explanation with Examples:

Example 1: code

• Bitmask Process:

  • c: ASCII difference from ‘a’ is 2, so bitmask = 0 ^ (1 << 2), bitmask becomes 0b100.

  • o: ASCII difference is 14, so bitmask = 0b100 ^ (1 << 14), bitmask updates to 0b100000000000100.

  • d: ASCII difference is 3, so bitmask = 0b100000000000100 ^ (1 << 3), bitmask changes to 0b100000000001100.

  • e: ASCII difference is 4, so bitmask = 0b100000000001100 ^ (1 << 4), bitmask becomes 0b100000000101100.

• Result: bitmask & (bitmask - 1) is not 0, so it’s False.

Example 2: aab

• Bitmask Process:

  • a: ASCII difference from ‘a’ is 0, so bitmask = 0 ^ (1 << 0), bitmask becomes 0b1.

  • a: ASCII difference is 0, so bitmask = 0b1 ^ (1 << 0), bitmask updates to 0b0.

  • b: ASCII difference is 1, so bitmask = 0b0 ^ (1 << 1), bitmask becomes 0b10.

• Result: bitmask & (bitmask - 1) is 0, so it’s True.

Example 3: carerac

• Bitmask Process:

  • c, a, r, e, r, a, c: After processing each character, the bitmask becomes 0b10000.

• Result: bitmask & (bitmask - 1) is 0, so it’s True (only one bit or no bit remains set).

Analysis

Time Complexity: O(n)

The function iterates through each character in the string once, where n is the length of the string. Therefore, the time complexity is linear, O(n).

Space Complexity: O(1)

The space complexity is constant, O(1), because the function uses a fixed-size integer (bitmask) for computation, regardless of the size of the input string.

Python

def canPermutePalindrome(self, s: str) -> bool:
    bitmask = 0
    for char in s:
        bitmask = bitmask ^ (1 << ord(char) - ord("a"))
    return bitmask & (bitmask - 1) == 0  # check if bitmask has only one set bit

1457. Pseudo-Palindromic Paths in a Binary Tree (Medium)

Please refer here: 1457. Pseudo-Palindromic Paths in a Binary Tree (Medium).

Bitmask - Log2

136. Single Number (Easy)

Refer :136. Single Number (Easy).

268. Missing Number (Easy)

Refer 268. Missing Number (Easy).

389. Find the Difference (Easy)

Refer 389. Find the Difference (Easy).

41. First Missing Positive (Hard)

Solution

The firstMissingPositive function is designed to find the smallest positive integer that does not appear in an array. The solution involves several steps, utilizing bit manipulation to efficiently find the missing number.

Why +2 in bit_length?: If the input is [1], then we need to get the negation of bitmask = 0b10 as 101 and not 01. This can only happen when the bit_length = 3, which is +2 of len([1]).

Steps Explained:

1. Bitmask Creation: Iterates through the array, setting bits in the bitmask for each positive integer found that is less than or equal to the length of the array.

2. Negation: Applies bitwise negation to the bitmask, effectively flipping all bits.

3. Unsetting the 0th Bit: Ensures that the 0th bit is unset because 0 is not considered a positive number.

4. Identifying the Missing Number: Finds the least significant set bit (LSB) in the negation, which corresponds to the smallest missing positive number.

Detailed Example Explanation:

• Input: [1, 2, 0]

  • Bitmask representing the presence of 1, 2: bitmask = 0b110.

  • After negating all bits: negation = 0b11001.

  • After unsetting 0th bit: negation = 0b11000.

  • After isolating least significant set bit: ls_set = 0b1000.

  • To get the answer, log2(ls_set) = 3

• Input: [3, 4, -1, 1]

  • Bitmask representing the presence of 1, 3, 4: bitmask = 0b11010.

  • After negating all bits: negation = 0b100101.

  • After unsetting 0th bit: negation = 0b100100.

  • After isolating least significant set bit: ls_set = 0b100.

  • To get the answer, log2(ls_set) = 2

• Input: [7, 8, 9, 11, 12]

  • Since none of the number is in range [0, len(nums)):, bitmask would be bitmask = 0b0.

  • After negating all bits: negation = 0b1111111.

  • After unsetting 0th bit: negation = 0b1111110.

  • After isolating least significant set bit: ls_set = 0b10.

  • To get the answer, log2(ls_set) = 1

• Input: [2147483647]

  • Since none of the number is in range [0, len(nums)):, bitmask would be bitmask = 0b0.

  • After negating all bits: negation = 0b111.

  • After unsetting 0th bit: negation = 0b110.

  • After isolating least significant set bit: ls_set = 0b10.

  • To get the answer, log2(ls_set) = 1

• Input: [1]

  • Bitmask representing the presence of 1: bitmask = 0b10.

  • After negating all bits: negation = 0b101.

  • After unsetting 0th bit: negation = 0b100.

  • After isolating least significant set bit: ls_set = 0b100.

  • To get the answer, log2(ls_set) = 2

Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Python

def firstMissingPositive(self, nums: List[int]) -> int:
    def negate_bits(num: int) -> int:
        bit_length = len(nums) + 2  # why + 2?
        bitmask = (1 << bit_length) - 1  # binary with all 1's
        return num ^ bitmask

    bitmask = 0
    for num in nums:
        if num > 0 and num <= len(nums):
            bitmask = bitmask | (1 << num)

    negation = negate_bits(bitmask)
    # zero is not a positive, hence unset 0 if set
    negation = (negation | 1) ^ 1
    # find the least significant set bit
    ls_set = negation & -negation

    return int(math.log2(ls_set))

Bitmask

448. Find All Numbers Disappeared in an Array (Easy)

Solution

Very similar to the solution of 41. First Missing Positive (Hard).

Steps Explained:

1. Bitmask Creation: Iterate through nums, set the corresponding bit in the bitmask.

2. Negating Bits: Apply a negation operation to the bitmask to invert all bits. The bit_length would be the length of the input array.

3. Unsetting the 0th Bit: Ensures that the 0th bit is unset because 0 is not considered a positive number.

4. Identifying Missing Numbers: Iterate through the negated bitmask, collecting positions where a bit is set to 1. These positions represent missing positive integers.

Detailed Example Explanation:

• Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]

  • After iterating over nums: bitmask = 0b110011110.

  • After negating all bits: negation = 0b1100001.

  • After unsetting 0th bit: negation = 0b1100000.

  • ans = [5, 6]

• Input: nums = [1, 1]

  • After iterating over nums: bitmask = 0b10.

  • After negating all bits: negation = 0b101.

  • After unsetting 0th bit: negation = 0b100.

  • ans = [2]

• Input: nums = [1, 1, 1]

  • After iterating over nums: bitmask = 0b10.

  • After negating all bits: negation = 0b1101.

  • After unsetting 0th bit: negation = 0b1100.

  • ans = [2, 3]

Analysis

Time Complexity: O(n)

The algorithm iterates over the array once to build the bitmask, and again to collect missing numbers based on the negated bitmask, leading to a linear time complexity.

Space Complexity: O(1)

The space used is constant, relying solely on a fixed-size bitmask and a few auxiliary variables, regardless of the input size.

Python

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    def negate_bits(num: int) -> int:
        bit_length = len(nums) + 1
        bitmask = (1 << bit_length) - 1
        return num ^ bitmask

    bitmask = 0
    for number in nums:
        bitmask = bitmask | (1 << number)

    negation = negate_bits(bitmask)

    # 0 is not part of the range, ignore by unsetting it.
    negation = (negation | 1) ^ 1

    # append all those positions where a bit is set to 1
    ans = []
    for pos in range(negation.bit_length()):
        if negation & (1 << pos):
            ans.append(pos)
    return ans

442. Find All Duplicates in an Array (Medium)

Python

def findDuplicates(self, nums: List[int]) -> List[int]:
    bitmask = 0
    ans = []
    for number in nums:
        pos = 1 << number
        # if the pos was already set, number has been already seen once
        if bitmask & pos:
            ans.append(number)
        # set the position, which is number'th bit
        bitmask = bitmask | pos
    return ans

2206. Divide Array Into Equal Pairs (Easy)

Python

def divideArray(self, nums: List[int]) -> bool:
    bitmask = 0
    for i in nums:
        bitmask = bitmask ^ (1 << i)
    return bitmask == 0

2869. Minimum Operations to Collect Elements (Easy)

Python

def minOperations(self, nums: List[int], k: int) -> int:
    mask = (1 << k) - 1
    mask <<= 1  # to incorporate 0th position
    bitmap = 0
    for i in range(len(nums) - 1, -1, -1):
        bitmap = bitmap | (1 << nums[i])
        if bitmap & mask == mask:
            return len(nums) - i
    return 0

1684. Count the Number of Consistent Strings (Easy)

Python

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    count = len(words)
    mask = 0
    for i in allowed:
        mask = mask | (1 << (ord(i) - ord("a")))

    for word in words:
        for i in word:
            pos = 1 << (ord(i) - ord("a"))
            if pos & mask == 0:
                count -= 1
                break
    return count

2351. First Letter to Appear Twice (Easy)

Python

def repeatedCharacter(self, s: str) -> str:
    bitmap = 0
    for i in s:
        pos = 1 << (ord(i) - ord("a"))
        if pos & bitmap:
            return i
        bitmap = bitmap | pos

2032. Two Out of Three (Easy)

Python

def twoOutOfThree(
    self, nums1: List[int], nums2: List[int], nums3: List[int]
) -> List[int]:
    bm1 = bm2 = bm3 = 0
    for i in nums1:
        bm1 |= 1 << i
    for i in nums2:
        bm2 |= 1 << i
    for i in nums3:
        bm3 |= 1 << i

    ans = []
    for i in range(1, 101):
        pos = 1 << i
        if sum([bm1 & pos != 0, bm2 & pos != 0, bm3 & pos != 0]) >= 2:
            ans.append(i)
    return ans

645. Set Mismatch (Easy)

Bit by Bit Loop

137. Single Number II (Medium)

Python

def singleNumber(self, nums: List[int]) -> int:
    """Bit Manipulation: Mod 3"""
    loner = 0
    for pos in range(32):
        bits = 0
        for num in nums:
            bits += num & (1 << pos) != 0
        bits = bits % 3
        loner = loner | (bits << pos)
    # Do not mistaken sign bit for MSB.
    if loner >= (1 << 31):
        return loner - (1 << 32)
    return loner

2917. Find the K-or of an Array (Easy)

Python

def findKOr(self, nums: List[int], k: int) -> int:
    bitmask = 0
    for pos in range(32):
        bits = 0
        for n in nums:
            if n & (1 << pos):
                bits += 1
        if bits >= k:
            bitmask = bitmask | (1 << pos)
    return bitmask

Advanced

693. Binary Number with Alternating Bits (Easy)

Python

def hasAlternatingBits(self, n: int) -> bool:
    return n & (n >> 1) == 0 and (n & (n >> 2)) == (n >> 2)

1256. Encode Number (Medium)

Python

def encode(self, num: int) -> str:
    return bin(num + 1)[3:]

201. Bitwise AND of Numbers Range (Medium)

Python

def rangeBitwiseAnd(self, left: int, right: int) -> int:
    shifts = 0
    while left != right:
        left >>= 1
        right >>= 1
        shifts += 1
    return left << shifts


def rangeBitwiseAnd(self, left: int, right: int) -> int:
    while left < right:
        right &= right - 1
    return left & right

2568. Minimum Impossible OR (Medium)

Python

def minImpossibleOR(self, nums: List[int]) -> int:
    nums_set = set(nums)
    look_for = 1
    while look_for in nums_set:
        look_for <<= 1
    return look_for

260. Single Number III (Medium)

287. Find the Duplicate Number (Medium)

832. Flipping an Image (Easy)