190. 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.

Follow up:

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

---

本题要把一个无符号32位整数的二进制位翻转，因为之前刚刷过LeetCode Number of 1 Bits可以快速统计uint32中二进制1的个数，所以很快联想到解法。一个32次的循环，依次获取到原数字的每一个二进制位，然后和结果取或，结果依次左移。
完整代码如下：

class Solution {
public:
    uint32_t reverseBits(uint32_t n)
    {
        uint32_t ans = 0;
        for (int i = 0; i < 31; i++) {
            ans |= (n & 1);
            ans <<= 1;
            n >>= 1;
        }
        return ans | (n & 1);
    }
};

本代码提交AC，用时3MS。

有意思的是Follow up，说如果这个函数会被多次调用，该怎样优化。都提到会被多次调用了，那肯定是把之前计算过的结果保存起来，下次查询的时候直接调用。但是一个32位的数，一共有2^32种情况，多次调用遇到同一个数的概率有点低，如果把之前的结果当成一个缓存，则缓存命中的概率有点低。如果只是缓存4bit的结果，只有2^4=16种情况，命中的概率就大大提高了。 这个解法就是直接缓存了4bit的翻转结果，放到tb数组中。每次取出原数字的4bit，然后直接查tb表，得到4bit的翻转结果，和ret取或，这样for循环只执行了8次。不错。

char tb[16] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
uint32_t reverseBits(uint32_t n)
{
    int curr = 0;
    uint32_t ret = 0;
    uint32_t msk = 0xF;
    for (int i = 0; i < 8; i++) {
        ret = ret << 4;
        curr = msk & n;
        ret |= tb[curr];
        n = n >> 4;
    }
    return ret;
}

还有一种解法借鉴了归并排序的思路，假设要对一个8bit的数组归并排序，先要不断一分为二，在归并的时候，在最底层对每1bit-1bit的对归并排序，倒数第二层对每2bit-2bit的对归并排序，如此往上归并。

      01101001
    /         \
   0110      1001
  /   \     /   \
 01   10   10   01
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

逆序也可以借鉴归并的思路，如下，首先最底层对每相邻的1bit-1bit交换位置，然后倒数第二层，对每相邻的2bit-2bit交换位置，如此往上交换，得到序列10010110，正好是上图中01101001的逆序。

      10010110
    /         \
   0110      1001
  /   \     /   \
 10   01   01   10
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

这个思路的代码如下，没有了for循环，只需执行20次位运算，代码中用8bit的字符串模拟了执行的情况。

class Solution {
public:
    uint32_t reverseBits(uint32_t x)
    {
        // x = ABCDEFGH
        x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); // x = B0D0F0H0 | 0A0C0E0G = BADCFEHG
        x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); // x = DC00HG00 | 00BA00FE = DCBAHGFE
        x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); // x = HGFE0000 | 0000DCBA = HGFEDCBA
        x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); // …
        x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
        return x;
    }
};

上面的16进制数字中:
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
0xAAAAAAAA = 1010 1010 1010 1010 1010 1010 1010 1010
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0xCCCCCCCC = 1100 1100 1100 1100 1100 1100 1100 1100
本代码提交AC，用时也是3MS。

190. 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.

Follow up:

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

---

要求一个无符号整数的二进制表示中’1’的个数。 没必要先把数的二进制表示求出来，只需要将数n和1相与，如果结果为1，说明最低位为1，否则最低位为0，然后不断把n向右移动，直到n为0。 完整代码如下：

class Solution {
public:
    int hammingWeight(uint32_t n)
    {
        int cnt = 0;
        while (n) {
            cnt += n & 1;
            n >>= 1;
        }
        return cnt;
    }
};

本代码提交AC，用时3MS。
二刷。直接n&(n-1)可以去掉n中的最后一个数，所以n有多少个二进制1就运算多少次，性能更佳，代码如下：

public
class Solution { // you need to treat n as an unsigned value
public
    int hammingWeight(int n)
    {
        int ans = 0;
        while (n != 0) {
            ++ans;
            n = n & (n – 1);
        }
        return ans;
    }
}

本代码提交AC，用时2MS。

136. Single Number

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

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

---

已知一个数组中除了一个数字，其他数字都出现了两次，现在需要找出这个只出现一次的数字。要求线性时间复杂度，且不使用额外的空间。 这是一个位运算的题，我们知道两个相同的数按位异或之后结果为0，因为异或操作是相同为0，不同为1。所以可以把数组中的所有数字都进行异或运算，那么所有出现两次的数字异或之后都等于0，最终只剩下出现次数为1次的那个数字。思路还是很巧妙的，完整代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i];
        }
        return ans;
    }
};

本代码提交AC，用时16MS。

LeetCode Sum of Two Integers Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example: Given a = 1 and b = 2, return 3.

---

不使用加减法实现两个整数之和。这其实就是用位运算实现加法，我还清楚的记得本科面搜狐实习的时候被问到这个问题，当时还没有答上来。。。 用基本位运算实现加减乘除和位运算 实现加法这两篇博客介绍得很详细，可以参考之。 简单讲，对于两个二进制数a,b，异或运算（a^b）可以得到两数不加进位的和，与运算（a&b）可以得到两数每一位上的进位。所以还需要把每一位的进位依次加到之前的和里面。完整代码如下： [cpp] class Solution { public: int getSum(int a, int b) { int sum = a^b, carry = a&b; while (carry) { int tmp_a = sum; // 把和当作新的被加数a int tmp_b = carry << 1; // 把进位当作新的加数b sum = tmp_a^tmp_b; // 新的和 carry = tmp_a&tmp_b; // 新的进位 } return sum; } }; [/cpp] 本代码提交AC，用时0MS。 //负数也可以通过上述代码 如果要用位运算实现减法，通过简单的转换就能变成加法：a-b=a+(-b)。负数在计算机中的表示是补码，负数的补码等于正数的原码（正数的原码、反码和补码相等）取反加1。得到(-b)的表示之后，就可以调用上面的加法函数了。]]>