Tag: bit manipulate

201. Bitwise AND of Numbers Range

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) {
            shift++;
            m = m >> 1;
            n = n >> 1;
        }
        return m << shift;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

260. Single Number III

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given an array of numbers 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.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int two_num = 0;
        for (int num : nums) two_num = two_num ^ num;
        int set_bit = 0;
        for (set_bit = 0; set_bit < 32; set_bit++) {
            if ((two_num >> set_bit & 1) == 1) break;
        }
        int result = 0;
        for (int num : nums) {
            if ((num >> set_bit & 1) == 1) result = result ^ num;
        }
        vector<int> results = {result, result ^ two_num};
        return results;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

318. Maximum Product of Word Lengths

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<int> masks(words.size(), 0);
        int result = 0;
        for (int i = 0; i < words.size(); i++) {
            for (char c : words[i]) {
                masks[i] = masks[i] | 1 << (c - 'a');
            }
            for (int j = 0; j < i; j++) {
                if (masks[j] & masks[i]) continue;
                result = max(result, int(words[i].size() * words[j].size()));
            }
        }
        return result;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

190. Reverse Bits

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

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

Related problem: Reverse Integer

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) + (n >> i & 1);
        }
        return result;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

231. Power of Two

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Given an integer, write a function to determine if it is a power of two.
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0 && !(n & (n - 1)));
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

137. Single Number II

fightingminion1 Comment

Difficulty: Medium

Frequency: N/A

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            int ta = (a & ~b & ~num) | (~a & b & num);
            b = (~a & b & ~num) | (~a & ~b & num);
            a = ta;
        }
        return a | b;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

Bit Manipulation

fightingminionLeave a comment

OR

  • OR is used for setting a bit regardless of the other bit.
  • When you want to set a bit to 1, just ‘OR’ the bit with 1
  • If x denotes a bit(0 or 1), then the following hold true.
  • x | 0 = x (i.e. OR ing with 0 retains the original bit.)
  • x | 1 = 1 (i.e. OR ing with 1 sets the bit to 1.)

Examples

  • Set the last digit to 1
    x | 1
  • Set the number to its closest even number (i.e. set the last digit to 0)
    (x | 1) - 1
  • Set the k-th digit to 1, e.g. 0b101001 -> 0b101101, k=3
    x | (1 << (k-1))
  • Set the last k digits to 1, e.g. 0b101001 -> 0b101111, k=3
    x | (1 << k - 1)
  • Flip the last continuous 0’s to 1’s, e.g. 0b10110000 -> 0b10111111
    x | (x-1)
  • Flip the first 0 to 1 (starting from right), e.g. 0b10101011 -> 0b10101111
    x | (x+1)

 

AND

  • AND can be used for clearing a bit.
  • When you want to ‘clear’ a bit, just ‘AND’ it with 0.
  • AND can be used for checking whether a bit is set.
  • To check whether a bit is set, just ‘AND’ it with 1, it will return whether that bit was set.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x & 0 = 0 (i.e. AND ing with 0 clears the bit to 0)
  • x & 1 = x (i.e. AND ing with 1 retains the original bit)

Examples

  • What’s the k-th digit of x?
    (x >> (k-1)) & 1
  • Is a number odd? (I.e., Is the last digit 1?)
    (x & 1) == 1
  • What’s the last k digits of x?
    x & (1 << k - 1)
  • What’s the last 3 digits of x?
    x & 0x111
  • Set the k-th digit to 0, e.g. 0x101101 -> 0x101001, k=3
    x & ~(1 << (k-1))
  • Is a number pow of 2?
    (x != 0) && (x & (x-1) ==0), i.e. x && !(x & (x - 1))
  • Flip the last continuous 1’s to 0’s, e.g. 0b10101111 -> 0b10100000
    x & (x+1)
  • N & 0xFF = least significant byte of integer or the last 8 bits of integer.

 

XOR

  • for flipping selective bits, XOR is chosen.
  • for flipping a bit, XOR it with 1, it will get reversed.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x ^ 1 = ~x (XOR ing with 1 flips the bits)

Examples

  • Flip k-th digit
    x ^ (1 << (k-1))
  • Flip last k digits
    x ^ (1 << k - 1)
  • Get the last continuous 1’s, e.g. 0b10101111 -> 0b1111
    (x ^ (x+1)) >> 1
  • Remove the left of the first 1 from the right, e.g. 0b10101000 -> 0b1000
    (x ^ (x-1)) >> 1 + 1   or   x ^ (x-1) & x
  • Swap two numbers
    One way to swap two numbers is to use + and – (two inverse operations):
    a = a + b;  b = a - b;  a = a - b;
    And we can use xor and since its inverse operation is itself:
    a = a ^ b;  b = a ^ b;  a = a ^ b;

 

NOT

  • The bitwise complement operator, ~, flips every bit in a number.

Examples

  •  ~N + 1 = -N

 

SHIFT

  • Left Shift
    • symbol is ‘<<‘
    • x << y means x shifted y bits to the left.
    • If you run out of space, bits drop off from the left.
  • Right Shift
    • symbol is ‘>>’
    • x >> y means x shifted y bits to the right.
    • If you run out of space, bits drop off from the right.

Examples

  • Remove the last digit
    x >> 1
  • Add a 0 to the end of a number
    x << 1
  • Add an 1 to the end of a number
    x << 1 + 1
  • N << 1 = N*2
  • N << 2 = N*pow(2,2)
  • N << k = N*(pow(2,k))
  • N >> 1 = floor(N/2)
  • N >> 2 = floor(N/pow(2,2))
  • N >> k = floor(N/pow(2,k))

191. Number of 1 Bits

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            if (n % 2) count++;
            n = n / 2;
        }
        return count;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

187. Repeated DNA Sequences

fightingminion1 Comment

Difficulty: Medium

Frequency: N/A

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> stringCount;
        vector<string> results;
        for (int i = 10; i <= s.size(); i++) {
            if (stringCount[s.substr(i - 10, 10)] == 1) {
                results.push_back(s.substr(i - 10, 10));
            }
            stringCount[s.substr(i - 10, 10)]++;
        }
        return results;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

136. Single Number

fightingminion1 Comment

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Test cases:
1. [1, 2, 2, 3, 1]
Corner cases:
1. [1]
2. [0]
Solution 1:
Data structure:
hash table
Steps:
1. For each element, if not in the set, insert it; otherwise, erase it.
2. Return the only element in the set.
Complexity:
Runtime: O(n)
Space: O(n)
Code:
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> my_set;
        for (int num : nums) {
            if (my_set.find(num) != my_set.end()) {
                my_set.erase(num);
            } else {
                my_set.insert(num);
            }
        }
        return *my_set.begin();
    }
};
Solution 2:
Data structure:
Bit Manipulation
steps:
1. For each element, do XOR.
Complexity:
Runtime: O(n)
Space: O(1)
Code:
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int num : nums) res = res^num;
        return res;
    }
};
Things to learn:
1. Be familiar with the bit manipulation operations.
2. num ^ num = 0.