Y
Published on

Leetcode Pattern 8 Bit Operations

Authors
  • avatar
    Name
    Yinhuan Yuan
    Twitter

Introduction

Bit manipulation is an essential technique in computer science, offering a fast and efficient way to solve various algorithmic problems. Bit manipulation involves directly working with the bits of binary numbers, allowing you to perform operations that are typically faster than their arithmetic or logical counterparts. Common operations include AND, OR, XOR, NOT, left shift, and right shift.

  1. Basic Bitwise Operators
  • AND (&): Compares each bit of two numbers and returns a new number with bits set to 1 where both corresponding bits are 1.
  • OR (|): Compares each bit of two numbers and returns a new number with bits set to 1 where at least one corresponding bit is 1.
  • XOR (^): Compares each bit of two numbers and returns a new number with bits set to 1 where the corresponding bits are different.
  • NOT (~): Inverts all the bits of a number.
  • Left Shift (<<): Shifts the bits of a number to the left by a specified number of positions, effectively multiplying the number by powers of two.
  • Right Shift (>>): Shifts the bits of a number to the right, effectively dividing the number by powers of two.
  1. Advantages of Bit Manipulation
  • Efficiency: Bit operations are generally faster and use less memory compared to arithmetic operations, making them ideal for time-critical applications.
  • Simplicity in Representation: Bit manipulation can simplify complex problems, especially those involving binary data, set operations, or low-level data structures.
  • Optimization: Bit manipulation often leads to optimized solutions by reducing the number of operations or the space complexity.
  1. Common Bit Manipulation
  • Set a Bit: Set a specific bit to 1. number |= (1 << n); For example, Set the 3rd bit of number: number |= (1 << 2);
  • Clear a Bit: Set a specific bit to 0. number &= ~(1 << n); For example, Clear the 3rd bit of number: number &= ~(1 << 2);
  • Toggle a Bit: Flip the state of a specific bit (0 to 1 or 1 to 0). number ^= (1 << n); For example, Toggle the 3rd bit of number: number ^= (1 << 2);
  • Check a Bit: Determine if a specific bit is set (1) or not (0). (number & (1 << n)) != 0; For example, Check if the 3rd bit of number is set: (number & (1 << 2)) != 0;
  • Extract the Rightmost Set Bit: Extract the least significant bit that is set to 1.number & (-number); For example, number = 12 (1100 in binary) → number & (-number) gives 4 (0100 in binary).
  • Clear the Rightmost Set Bit: Set the rightmost 1 bit to 0. number & (number - 1); For example, number = 12 (1100 in binary) → number & (number - 1) gives 8 (1000 in binary).
  • Count the Number of 1 Bits (Hamming Weight)
    • Using a loop:
      int count = 0;
while (number) {
    count += number & 1;
    number >>= 1;
}
    • Using number & (number - 1) method:
      int count = 0;
while (number) {
    number &= (number - 1);
    count++;
}
  • Get the Value of the Least Significant Bit: Get the value of the lowest bit. number & 1; For example, number = 12 (1100 in binary) → number & 1 gives 0.
  • Bit Masking: Extract specific bits from a number. (number >> n) & mask; For example, To extract 3 bits starting from bit 2: (number >> 2) & 0x7; (0x7 is the mask for 3 bits)
  • Shift Operations
    • Left Shift: number << n; (shifts bits left by n positions, filling with 0s)
    • Right Shift: number >> n; (shifts bits right by n positions, filling with 0s for unsigned numbers, and sign bit for signed numbers)
  • Swap Values Without a Temporary Variable
    • Operation:
      x ^= y;
y ^= x;
x ^= y;
    • Example: x = 5, y = 3 → After the operations, x = 3, y = 5.
  • Negate a Number (Two's Complement): ~number + 1; For example, number = 5 → ~5 + 1 gives -5.

Bit Operations Problems

136. Single Number[Easy]

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Solution: We can leverage the properties of the XOR operation: a = 0 ^ a = a ^ 0 and 0 = a ^ a. By XORing all the numbers in the array, the pairs of duplicate numbers will cancel out, leaving only the single number.

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

137. Single Number II[Medium]

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Each element in nums appears exactly three times except for one element which appears once.

Solution: We convert all the numbers to binary strings. For negative numbers, we add 2**32 to ensure a positive representation. We also pad the binary strings with leading zeros to ensure each has a length of 32 bits.

We then go through each bit position and count the occurrences of '1'. If the count for a bit position is not divisible by 3, the remaining count indicates the bit of the unique number in that position. Once we have determined the bits of the unique number, we can convert the binary result back to a decimal number. If the result represents a negative number, we subtract 2**32 from it to get the correct value.

function singleNumber(nums: number[]): number {
    const numStrings = nums.map((num) => {
        // nums is only 32 bit number
        const number = num >= 0 ? num : 2 ** 32 + num;
        return number.toString(2).padStart(32, "0"); // put 0 in the beginning if it is necessary
    });
    const freq = Array(32).fill(0);
    for (let i = 0; i < 32; i++) {
        freq[i] = numStrings
            .map((numStr) => parseInt(numStr[i], 2))
            .reduce((acc, cur) => acc + cur, 0) % 3;
    }
    const ans = parseInt(freq.map((v) => String(v)).join(""), 2);
    if (freq[0] === 0) return ans;
    // Negative integer
    return ans - 2 ** 32;
}

260. Single Number III[Medium]

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Solution: To find the two elements that appear only once in the given array nums, while ensuring linear runtime complexity and constant extra space, we can use the bitwise XOR operation.

Here's the step-by-step approach:

  1. XOR All Elements: Start by XORing all elements in the array. This will cancel out the elements that appear twice and leave us with the XOR of the two unique elements.

  2. Find a Differentiating Bit: The result from the previous step will be the XOR of the two unique elements, which means at least one bit will differ between them. We find the rightmost set bit (least significant bit) in the XOR result. This bit will help us differentiate between the two unique elements. This can be found using xor_result & -xor_result.

  3. Separate the Elements: Using the differentiating bit, we split the original array into two groups:

    • Group 1: Elements where the differentiating bit is set.
    • Group 2: Elements where the differentiating bit is not set.

  4. Find the Unique Elements: XOR all elements in each group. The results will be the two unique numbers since all other elements in each group will cancel out.

function singleNumber(nums: number[]): number[] {
  let xor_result = 0;
  nums.forEach((num) => {
    xor_result ^= num;
  });
  /*
    Suppose xor_result is                     1010
    Compute -xor_result:
    First, invert all the bits of xor_result: 0101.
    Then, add 1 to the result: 0101 + 1 =     0110.
    The result 0010 has isolated the rightmost set bit.
    */
  // from the right to left, this is the first bit where two numbers become different.
  const rightmost_set_bit = xor_result & -xor_result;

  let num1 = 0;
  let num2 = 0;
  nums.forEach((num) => {
    if (num & rightmost_set_bit) {
      num1 ^= num;
    } else {
      num2 ^= num;
    }
  });
  return [num1, num2];
}

191. Number of 1 Bits[Easy]

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Follow up: If this function is called many times, how would you optimize it?

Solution: We use the operation n = n & (n - 1) to clear the rightmost 1-bit in n. The number of times this operation can be performed before n becomes 0 is equal to the number of 1-bits in n.

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n > 0:
            n = n & (n - 1) # clear the most right 1 bit of n
            ans += 1
        return ans

338. Counting Bits[Easy]

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass? Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution: We can use the fact that countBits(n) = countBits(n // 2) if n is even, and countBits(n) = countBits(n // 2) + 1 if n is odd.

function countBits(n: number): number[] {
  const ans = Array(n + 1).fill(-1);
  ans[0] = 0;
  const helper = (x: number) => {
    const mid = Math.floor(x / 2);
    const midResult = ans[x] === -1 ? helper(mid) : ans[mid];
    ans[x] = x % 2 === 1 ? midResult + 1 : midResult;
    return ans[x];
  };
  for (let i = 1; i <= n; i++) {
    helper(i);
  }
  return ans;
}

190. Reverse Bits[Easy]

Reverse bits of a given 32 bits unsigned integer.

Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up: If this function is called many times, how would you optimize it?

Solution: We extract the bit value at position i and set the corresponding bit value at position 31 - i.

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            bit = (n >> i) & 1  # Extract the ith bit from n
            result |= bit << (31 - i)  # Place the bit in the correct position in result
        return result

1009.Complement of Base 10 Integer[Easy]

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer n, return its complement.

Solution: We solve this problem with the fact: x ^ 1111....111 = ~x.

  1. Determine the number of bits in the binary representation of n.
  2. Create a mask with the same number of bits all set to 1. This mask will help us flip all the bits of n.
  3. Flip the bits of n by XORing n with the mask. XORing with 1 flips the bit (0 becomes 1 and 1 becomes 0).
def bitwiseComplement(n: int) -> int:
    # Handle the edge case where n is 0, as its complement is 1
    if n == 0:
        return 1

    # Determine the number of bits in n
    num_bits = n.bit_length()

    # Create a mask with the same number of bits as n, all set to 1
    mask = (1 << num_bits) - 1

    # XOR n with the mask to get the complement
    return n ^ mask

832.Flipping an Image[Easy]

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.

For example, flipping [1,1,0] horizontally results in [0,1,1]. To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

For example, inverting [0,1,1] results in [1,0,0].

Solution: We use the reverse function to reverse the row, and then flip each bit using row[i] = 1 - row[i].

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for row in image:
            # Flip the row horizontally
            row.reverse()
            # Invert the row
            for i in range(len(row)):
                row[i] = 1 - row[i]
        return image

201. Bitwise AND of Numbers Range[Medium]

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Solution: The key idea is to find the common prefix of the binary representations of left and right since, for numbers that differ, their lower bits will differ, leading to a result of 0 when ANDed over a range.

  1. Initialization:

    • shift is initialized to 0. This variable will keep track of how many positions the bits have been shifted.

  2. Finding the common prefix:

    • The while loop continues as long as left is less than right. The goal of this loop is to find the common prefix of left and right.
    • Inside the loop:
      • Both left and right are right-shifted by one position (left >>= 1; right >>= 1;). This effectively removes the least significant bit from both numbers.
      • The shift counter is incremented by 1 (shift += 1;) to keep track of how many bits have been shifted.

  3. Final computation:

    • Once left equals right, the loop ends. The value of left (or right, since they are now equal) now contains the common prefix of the binary representations of the original left and right, shifted to the right by shift positions.
    • The function returns left shifted back to the left by shift positions (left << shift;). This operation restores the common prefix to its original position in the binary representation, effectively constructing the result.
function rangeBitwiseAnd(left: number, right: number): number {
    let shift = 0;
    while (left < right) {
        left >>= 1;
        right >>= 1;
        shift += 1;
    }
    return left << shift;
};

89. Gray Code[Medium]

An n-bit gray code sequence is a sequence of 2n integers where:

Every integer is in the inclusive range [0, 2n - 1], The first integer is 0, An integer appears no more than once in the sequence, The binary representation of every pair of adjacent integers differs by exactly one bit, and The binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence.

Solution: The k-bit Gray code is a binary sequence where each pair of consecutive terms differs by exactly one bit. To construct the (k+1)-bit Gray code, we use the k-bit Gray code sequence and generate the (k+1)-bit sequence as follows:

  1. Forward Traversal:

    • Start with the k-bit Gray code sequence.
    • Prepend a 0 to the binary representation of each number in the k-bit sequence.
    • This produces the first half of the (k+1)-bit Gray code sequence.

  2. Reverse Traversal:

    • Reverse the k-bit Gray code sequence.
    • Prepend a 1 to the binary representation of each number in the reversed k-bit sequence.
    • This produces the second half of the (k+1)-bit Gray code sequence.

For example, the 2-bit Gray code sequence is 0, 1, 3, 2, with binary representations 00, 01, 11, 10. To generate the 3-bit Gray code sequence:

  • First 4 Terms:

    • Take the 2-bit Gray code 0, 1, 3, 2.
    • Prepend 0 to each binary representation to get 000, 001, 011, 010.

  • Last 4 Terms:

    • Reverse the 2-bit Gray code to get 2, 3, 1, 0.
    • Prepend 1 to each binary representation to get 110, 111, 101, 100.

Thus, the 3-bit Gray code sequence is 0, 1, 3, 2, 6, 7, 5, 4, with binary representations 000, 001, 011, 010, 110, 111, 101, 100.

function grayCode(n: number): number[] {
    const solver = (n: number): string[] => {
        if (n === 1) return ["0", "1"];
        const codes = solver(n - 1);
        const reversed = codes.slice(0, codes.length);
        reversed.reverse();
        return [...codes.map((num) => `0${num}`), ...reversed.map((num) => `1${num}`)];
    };
    return solver(n).map((num) => parseInt(num, 2));
}

371. Sum of Two Integers[Medium]

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Solution: When adding two numbers, the result can be divided into two parts: the carry part and the non-carry part.

  1. Carry Part: A carry occurs only when both numbers have a 1 in the same bit position. This carry is effectively represented by performing a bitwise AND on the two numbers and then shifting the result left by one position. This can be expressed as carry = (a & b) << 1.

  2. Non-Carry Part: The non-carry part of the addition is determined by the bitwise XOR operation. When the corresponding bits of the two numbers are different, the result is 1; if they are the same, the result is 0. Thus, the non-carry part can be represented as non-carry = a ^ b.

To find the sum of two numbers a and b without using the + operator, you can follow these steps:

  1. Compute the carry using carry = (a & b).
  2. Compute the non-carry part using a = a ^ b.
  3. Replace b with the carry shifted by one.
  4. Repeat the above steps until b becomes 0, at which point a will hold the final sum of the two numbers.
function getSum(a: number, b: number): number {
    // Iterate till there is no carry
    while (b !== 0) {
        // carry now contains common set bits of a and b
        const carry = a & b;
        // Sum of bits of a and b where at least one of the bits is not set
        a = a ^ b;
        // Carry is shifted by one so that adding it to a gives the required sum
        b = carry << 1;
    }
    return a;
};

405. Convert a Number to Hexadecimal[Easy]

Given an integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

Solution: For negative integers, first add 2 ** 32 to convert them to positive. Then, repeatedly divide the number by 16, recording the remainder and updating the number with the quotient. Continue this process until the number becomes 0. Finally, convert the collected remainders into a string.

function toHex(num: number): string {
    if (num === 0) return "0";
    if (num < 0) {
        num += 2 ** 32;
    }
    let n = num;
    const ans = [];
    while (n > 0) {
        ans.unshift(n % 16);
        n = Math.floor(n / 16);
    }
    const chars = "0123456789abcdef";
    return ans.map(i => chars[i]).join("");
};

504. Base 7[Easy]

Given an integer num, return a string of its base 7 representation.

Solution: Similar to problem 405, Convert a Number to Hexadecimal, we use 7 instead of 16 as the divisor.

function convertToBase7(num: number): string {
  if (num === 0) return "0";
  const helper = (num: number) => {
    let n = num;
    const ans = [];
    while (n > 0) {
      ans.unshift(n % 7);
      n = Math.floor(n / 7);
    }
    return ans.map((i) => String(i)).join("");
  };
  return num < 0 ? "-" + helper(-num) : helper(num);
}

1349. Maximum Students Taking Exam[Hard]

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible.

Students must be placed in seats in good condition.

Solution: We use state Compression Dynamic Programming to solve this problem. mask |= 1 << j;: set the jth position (from right) bitCount: num >>= 1; and ans += num & 1; const dp: Map<number, number>[] = Array.from({length: m + 1}, ()=> new Map());: dp[row][status] rowth const [prevState, prevCount] of dp[row - 1].entries()

function maxStudents(seats: string[][]): number {
    const m = seats.length;
    const n = seats[0].length;
    const seatMasks = createSeatMasks(seats);
    const dp: Map<number, number>[] = Array.from({length: m + 1}, ()=> new Map());
    dp[0].set(0, 0);
    for (let row = 1; row <= m; row ++) {
        const seatMask = seatMasks[row - 1];
        for (const [prevState, prevCount] of dp[row - 1].entries()) {
            for (let currState = 0; currState < (1 << n); currState++) {
                if ((currState & ~seatMask) !== 0) continue;
                if ((currState & (currState >> 1)) !== 0) continue;
                if ((prevState & (currState >> 1)) !== 0) continue;
                if ((prevState & (currState << 1)) !== 0) continue;
                const count = bitCount(currState);
                const newCount = prevCount + count;
                if (!dp[row].has(currState) || newCount > dp[row].get(currState)!) {
                    dp[row].set(currState, newCount);
                }
            }
        }
    }
    // Find the maximum number of students that can be seated
    return Math.max(...dp[m].values());
}
function createSeatMasks(seats: string[][]): number[] {
    // Convert seats to bitmask rows
    const seatMasks: number[] = seats.map(row => {
        let mask = 0;
        row.forEach((val, j) => {
            if (val === '.') {
                mask |= (1 << j);
            }
        });
        return mask;
    });
    return seatMasks;
};
function bitCount(num: number): number {
    let count = 0;
    while (num) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}
Discuss on Twitter • View on GitHub