BIT OPERATION

位运算

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

public int SingleNumber(int[] nums)
{
    int res = nums[0];
    for(int i = 1; i < nums.Length; i++)
    {
        res ^= nums[i];
    }
    return res;
}

异或是一个“半加器”，也就是不带进位的二进制运算，普遍用于加密解密上。我们发现1⊕0 = 1，1⊕1 = 0，当a⊕b以后再⊕a，结果还是b。所以上面题目中说，除了某个元素，其他元素均出现两次，我们利用异或的特点，找到了只出现一次的元素。

191. 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1:

输入: 11
输出: 3
解释: 整数 11 的二进制表示为 00000000000000000000000000001011

示例 2:

输入: 128
输出: 1


解释: 整数 128 的二进制表示为 00000000000000000000000010000000

public int HammingWeight(uint n)
{
    int c = 0;
    while(n > 0)
    {
        n &= (n - 1);
        c++;
    }
    return c;
}

n - 1实际上是在将从低位到高位最后面的一个1的那一位到最低位取反，即101100 - 1 = 101011。减1操作之后再与上自己，这样就把最后是1的位以及其后面的所有位置为0。当n = 0的时候，说明全部遍历完为1的位。

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 2^0 = 1

示例 2:

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

输入: 218
输出: false

public bool IsPowerOfTwo(int n)
{
     return n > 0 && (n & (n - 1)) == 0;
}

我们把2的幂次方的数用2进制表示出来会发现，所有的2的幂次方都只包含1个1，我们可以利用此原理来判定是否是2的幂次方（想一想左移操作<<，1左移1位实际上就是乘以2，再左移2位就是再乘以2）。(n & (n - 1)) == 0原理同【汉明重量】。

342. 4的幂

给定一个整数 (32位有符整数型)，请写出一个函数来检验它是否是4的幂。

示例: 当 num = 16 时 ，返回 true 。 当 num = 5时，返回 false。

问题进阶：你能不使用循环/递归来解决这个问题吗？

public bool IsPowerOfFour(int num)
{
    return (((num - 1) & num) == 0) && ((num & 0x55555555) != 0);
}

如果是4的幂，那一定是2的幂，因此((num - 1) & num) == 0)是表示是2的幂，我们把0x55555555转换成2进制看一下，是1010101010101010101010101010101。4的次幂实际上是2^2n次幂，也就是1左移2n次幂，所以奇数位为1偶数位为0即是0x55555555（1左移2n位，结果所在的位是2n + 1，在奇数位上）。因此(num & 0x55555555) != 0表示的是2进制的“1”在奇数位上。