Name		Name	Last commit message	Last commit date
parent directory ..
136_SingleNumber.cpp		136_SingleNumber.cpp
136_SingleNumber.py		136_SingleNumber.py
137_SingleNumberII.cpp		137_SingleNumberII.cpp
137_SingleNumberII.py		137_SingleNumberII.py
169_MajorityElement.cpp		169_MajorityElement.cpp
169_MajorityElement.py		169_MajorityElement.py
190_ReverseBits.py		190_ReverseBits.py
191_NumberOf1Bits.py		191_NumberOf1Bits.py
201_BitwiseANDofNumbersRange.py		201_BitwiseANDofNumbersRange.py
231_PowerOfTwo.py		231_PowerOfTwo.py
260_SingleNumberIII.cpp		260_SingleNumberIII.cpp
260_SingleNumberIII.py		260_SingleNumberIII.py
268_MissingNumber.py		268_MissingNumber.py
29_DivideTwoIntegers.cpp		29_DivideTwoIntegers.cpp
29_DivideTwoIntegers.py		29_DivideTwoIntegers.py
318_MaximumProductOfWordLengths.py		318_MaximumProductOfWordLengths.py
338_CountingBits.cpp		338_CountingBits.cpp
338_CountingBits.py		338_CountingBits.py
342_PowerOfFour.cpp		342_PowerOfFour.cpp
342_PowerOfFour.py		342_PowerOfFour.py
371_SumOfTwoIntegers.cpp		371_SumOfTwoIntegers.cpp
371_SumOfTwoIntegers.py		371_SumOfTwoIntegers.py
78_Subsets.py		78_Subsets.py
README.md		README.md

README.md

常用位操作

其它常用位操作如下：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

考虑如果数组里只有一个数字出现一次，其它数字均出现两次，那么可以直接将所有数字异或一遍，最后得到的数字即为只出现一次的数字。现在数组中有两个出现一次的，可以考虑通过某种手段将数组分为两部分，每部分中只有一个数字出现一次，其它均出现两次，这样对每部分进行异或就能找到一个数字。

假设 m 和 n 是两个不同的数字，拆分时要将 m, n 放在不同的部分去，同时保证其它数字两次出现在同一个部分中。m, n不同，所以至少有一位是不同的，例如m为0的话n就为1。为了方便，可以找出m, n发生差异所在的最低位k，那么：

2^k = (m^n) & (-m^n)

求m, n 的异或只需要将数组中所有数字异或一遍即可。划分数组可以根据num&2^k 是否为1的结果。

给定整数 n，返回长度为 n+1 的数组arr，其中arr[i]为整数i 的二进制表示中 1 的个数。

我们知道计算一个整数二进制表示中 1 的个数可以这样来做，

while(x){
    count += 1;
    x = x&(x-1); // 将最低位的1置为0
}

因此，很容易想到利用动态规划的思想来解决这个问题，动态转移方程为：

ans[i] = ans[i >> 1] + (i&0x1)
# ans[i] = ans[i & (i - 1)] + 1

此外统计一个整数的二进制表示中0的个数可以这样实现：

while((x+1))
{
  count++;
  x=x|(x+1);
}