C 的位操作

位操作运算符

C++基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下所示：

Note:

• 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
• 位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫明其妙的结果
• 另外位操作还有一些复合操作符，如&=、|=、 ^=、<<=、>>=
• &&、|、~|都是逻辑操作符

位操作实战

476 Number Complement

476. Number Complement Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2: Input: 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.
3. This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

题目来源:https://leetcode.com/problems/number-complement/

class Solution {
public:
    int findComplement(int num) {
        int tmp = num;
        int mask = 0;
        while (tmp)
        {
            mask = mask << 1;
            mask = mask | 1;
            tmp = tmp >> 1;
        }
        int result = (~num) & mask;
        return result;
    }
};

461 Hamming Distance

1. Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 2. Example: Input: x = 1, y = 4

Output: 2

Explanation:

1 (0 0 0 1)

4 (0 1 0 0)

   ↑   ↑

The above arrows point to positions where the corresponding bits are different. 题目来源：https://leetcode.com/problems/hamming-distance/

class Solution {
public:
    int hammingDistance(int x, int y) {
        int c = x ^ y;
        int ret = 0;
        while(c != 0)
        {
            ret += (c & 1);
            c = c >> 1;
        }

        return ret;
    }
};

190 Reverse Bits

1. Reverse Bits
   

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100

Output: 00111001011110000010100101000000

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101

Output: 10111111111111111111111111111111

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

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 signed integer type and should not affect your implementation, as the internal binary representation of the integer 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.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret;
        uint32_t mask = 1;
        int loop = 32;
        uint32_t tmp;

        while(--loop)
        {
            tmp = n & mask;
            n = n >> 1;
            ret = ret | tmp;
            ret = ret << 1;
        }

        tmp = n & mask;

        return ret | tmp;
    }
};

官方题解

Approach 1: Bit by Bit

Intuition
Though the question is not difficult, it often serves as a warm-up question to kick off the interview. The point is to test one’s basic knowledge on data type and bit operations.

As one of the most intuitive solutions that one could come up during an interview, one could reverse the bits one by one.

As easy as it sounds, the above intuition could lead to quite some variants of implementation. For instance, to retrieve the right-most bit in an integer n, one could either apply the modulo operation (i.e. n % 2) or the bit AND operation (i.e. n & 1). Another example would be that in order to combine the results of reversed bits (e.g. 2^a, 2^b2a,2b), one could either use the addition operation (i.e. 2^a + 2^b2a+2b) or again the bit OR operation (i.e. 2^a | 2^b2a∣2b).
Algorithm
Here we show on example of implementation based on the above intuition.

The key idea is that for a bit that is situated at the index i, after the reversion, its position should be 31-i (note: the index starts from zero).

• We iterate through the bit string of the input integer, from right to left (i.e. n = n >> 1). To retrieve the right-most bit of an integer, we apply the bit AND operation (n & 1).
  
• For each bit, we reverse it to the correct position (i.e. (n & 1) << power). Then we accumulate this reversed bit to the final result.
  
• When there is no more bits of one left (i.e. n == 0), we terminate the iteration.

class Solution {
  public:
  uint32_t reverseBits(uint32_t n) {
    uint32_t ret = 0, power = 31;
    while (n != 0) {
      ret += (n & 1) << power;
      n = n >> 1;
      power -= 1;
    }
    return ret;
  }
};

Complexity

• Time Complexity: O(1). Though we have a loop in the algorithm, the number of iteration is fixed regardless the input, since the integer is of fixed-size (32-bits) in our problem.
  
• Space Complexity: O(1), since the consumption of memory is constant regardless the input.
  

Approach 2: Byte by Byte with Memoization

Intuition
Someone might argument it might be more efficient to reverse the bits, per byte, which is an unit of 8 bits. Though it is not necessarily true in our case, since the input is of fixed-size 32-bit integer, it could become more advantageous when dealing with the input of long bit stream.

Another implicit advantage of using byte as the unit of iteration is that we could apply the technique of memoization, which caches the previously calculated values to avoid the re-calculation.
The application of memoization can be considered as a response to the follow-up question posed in the description of the problem, which is stated as following:

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

To reverse bits for a byte, one could apply the same algorithm as we show in the above approach. Here we would like to show a different algorithm which is solely based on the arithmetic and bit operations without resorting to any loop statement, as following:

def reverseByte(byte):
    return (byte * 0x0202020202 & 0x010884422010) % 1023

The algorithm is documented as “reverse the bits in a byte with 3 operations” on the online book called Bit Twiddling Hacks by Sean Eron Anderson, where one can find more details.
Algorithm

• We iterate over the bytes of an integer. To retrieve the right-most byte in an integer, again we apply the bit AND operation (i.e. n & 0xff) with the bit mask of 11111111.
  
• For each byte, first we reverse the bits within the byte, via a function called reverseByte(byte). Then we shift the reversed bits to their final positions.
  
• With the function reverseByte(byte), we apply the technique of memoization, which caches the result of the function and returns the result directly for the future invocations of the same input.
  

Note that, one could opt for a smaller unit rather than byte, e.g. a unit of 4 bits, which would require a bit more calculation in exchange of less space for cache. It goes without saying that, the technique of memoization is a trade-off between the space and the computation.

class Solution {
public:
    uint32_t reverseByte(uint32_t byte, map<uint32_t, uint32_t> cache) {
        if (cache.find(byte) != cache.end()) {
            return cache[byte];
        }
        uint32_t value = (byte * 0x0202020202 & 0x010884422010) % 1023;
        cache.emplace(byte, value);
        return value;
    }

    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0, power = 24;
        map<uint32_t, uint32_t> cache;
        while (n != 0) {
            ret += reverseByte(n & 0xff, cache) << power;
            n = n >> 8;
            power -= 8;
        }
        return ret;
    }
};

Complexity

• Time Complexity: O(1). Though we have a loop in the algorithm, the number of iteration is fixed regardless the input, since the integer is of fixed-size (32-bits) in our problem.
  
• Space Complexity: O(1). Again, though we used a cache keep the results of reversed bytes, the total number of items in the cache is bounded to 2^8 = 25628=256.

Approach 3: Mask and Shift

Intuition
We have shown in Approach #2 an example on how to reverse the bits in a byte without resorting to the loop statement. During the interview, one might be asked to reverse the entire 32 bits without using loop. Here we propose one solution that utilizes only the bit operations.

The idea can be considered as a strategy of divide and conquer, where we divide the original 32-bits into blocks with fewer bits via bit masking, then we reverse each block via bit shifting, and at the end we merge the result of each block to obtain the final result.

In the following graph, we demonstrate how to reverse two bits with the above-mentioned idea. As one can see, the idea could be applied to blocks of bits.

Algorithm
We can implement the algorithm in the following steps:

• 1). First, we break the original 32-bit into 2 blocks of 16 bits, and switch them.
  
• 2). We then break the 16-bits block into 2 blocks of 8 bits. Similarly, we switch the position of the 8-bits blocks
  
• 3). We then continue to break the blocks into smaller blocks, until we reach the level with the block of 1 bit.
  
• 4). At each of the above steps, we merge the intermediate results into a single integer which serves as the input for the next step.
  

The credit of this solution goes to @tworuler and @bhch3n for their post and comment-bit-operation-C%2B%2B-solution-(8ms)) in the discussion forum.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};

Complexity

• Time Complexity: O(1), no loop is used in the algorithm.
  
• Space Complexity: O(1). Actually, we did not even create any new variable in the function.

260 Single Number III

260. Single Number III
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.

Example:

Input: [1,2,1,3,2,5]

Output: [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?

对于这道题，我采用了两种方法，一种是采用hash table的方法，即将值作为key都放入到hash table中，之后统计出hashtable中value为1的key。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int>ret;

        map<int, int>hashtable;
        for(auto& index : nums)
        {
            hashtable[index]++;
        }

        for(auto &index : hashtable)
        {
            if(index.second == 1)
                ret.push_back(index.first);
        }

        return ret;
    }
};

第二种方法是采用排序的方法

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int>ret;

        for(int i = 0; i < nums.size();)
        {
            if(i+1 == nums.size())
            {
                ret.push_back(nums[i]);
                i++;
            }
            else if(nums[i] != nums[i+1])
            {
                ret.push_back(nums[i]);
                i++;
            }
            else
            {
                i = i + 2;
            }
        }

        return ret;
    }
};

还有一种方法是从评论区-time-O(1)-space-Easy-Solution-with-Detail-Explanations)中所看到的，采用了异或运算

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

• In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value ‘1’) in the XOR result. Find
  out an arbitrary set bit (for example, the rightmost set bit).
  
• In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.
  

Complexity:

• Time: O (n)
  
• Space: O (1)
  

A Corner Case:

• When diff == numeric_limits<int>::min(), -diff is also numeric_limits<int>::min(). Therefore, the value of diff after executing diff &= -diff is still numeric_limits<int>::min(). The answer is still correct.

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // Get its last set bit
        diff &= -diff;

        // Pass 2 :
        vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
        for (int num : nums)
        {
            if ((num & diff) == 0) // the bit is not set
            {
                rets[0] ^= num;
            }
            else // the bit is set
            {
                rets[1] ^= num;
            }
        }
        return rets;
    }
};