11-二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
这道题本来用Brian Kernighan’s Algorithm做，不管是正负数都能在B次迭代后返回结果（B为二进制数中置位的个数）。BKA的核心思想是：
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit.
因此，n & (n-1)得到将n的最低置位设为0后的数。不过无奈Python的整数并没有32位或64位限制，所以负数理论上是有无限个置位，为了处理这种情况只能先将其位与一个0xffffffff（32位下）。
def NumberOf1(self, n):
if n < 0:
n &= 0xffffffff
count = 0
while n:
n &= (n-1)
count += 1
return count
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while (n) {
n &= n - 1;
++count;
}
return count;
}
};
12-数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。
这道题就是要求base ** exponent而已，但可能不想人用math.pow或者**，只能靠乘除法。用乘除法来做乘方也是可行的，而且还不慢。举个例子，2**11，将其表示为二进制，就是
10**1011 = 10**1000 * 10*0010 ** 10**0001
而求2**(2**n)（n是一个自然数）是非常好求的。在下面的代码中，只需要随着迭代，每一步将base翻倍，即相当于让指数左移了一位。因此，将乘方拆解为若干个乘方的连乘，就能通过乘法在常数时间内（不大于32次迭代，因为exponent不超过32位）求得答案。
如果exponent是一个负数，只需要将其取反，最后在返回时返回答案的倒数即可。
def Power(self, base, exponent):
expo = exponent if exponent >= 0 else -exponent
rtn = 1.
while expo:
if expo & 1:
rtn *= base
base *= base
expo >>= 1
return rtn if exponent > 0 else 1/rtn
class Solution {
public:
double Power(double base, int exponent) {
bool neg_flag = false;
if (exponent < 0) {
neg_flag = true;
exponent = -exponent;
}
double rtn = 1;
while (exponent) {
if (exponent & 1) rtn *= base;
base *= base;
exponent >>= 1;
}
if (neg_flag) return 1 / rtn;
return rtn;
}
};
40-数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
如果数组的只有一个数字出现了一次，而其他数字出现两次的话，可以将所有数异或起来，结果就是那个只出现一次的数（因为其他数出现两次，同样的数异或结果是0）。如果数组有两个数字出现一次，那么将所有数异或在一块，得到的是那两个出现一次的数的异或值。因为这两个数不一样，所以异或值不为0。这个异或值为置位的位置上，这两个数肯定一个是0一个是1。因此，可以通过异或值的最低置位将所有数分成两部分，一部分在该位上为0一部分在该位上为1。对这两部分做异或，便可得到最终的结果。
如果用Python，代码可以写得很短。求异或值的最低置位t时，只需要将其与减一后的值异或，便可得到一个二进制形如111..1的数，这个数共有t位。然后，加上1再右移一位，便可得到最低的置位。
from functools import reduce
class Solution:
def FindNumsAppearOnce(self, array):
temp1 = reduce(lambda x, y: x^y, array)
temp1 = ((temp1 ^ (temp1-1)) + 1) >> 1
arr1 = [x for x in array if temp1&x]
arr2 = [x for x in array if not temp1&x]
a1 = reduce(lambda x, y: x^y, arr1)
a2 = reduce(lambda x, y: x^y, arr2)
return a1, a2
class Solution {
public:
void FindNumsAppearOnce(vector<int> data, int *num1, int *num2) {
int temp1 = 0;
for (int each: data) temp1 ^= each;
temp1 = ((temp1 ^ (temp1 - 1)) + 1) >> 1;
*num1 = 0, *num2 = 0;
for (int each: data) {
if (each & temp1) *num1 ^= each;
else *num2 ^= each;
}
}
};