11. 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路： 一个n位二进制数，标记其每一位为[0 1 2……n]，减去1之后，会使得右数第一个1到第n为发生改变，1转换为0，0转换为1。为了避免减去重复位数上的1，使减1以后的数与原数相与，会使得改变了的位数都变为0。
例， 111，减1得110，111&110得110，
110，减1得101，110&101得100，
100，减1得010，100&010得000，
发生3次转换，原数含3个1。
1
2
3
4
5
6
7
8
9
10
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
n = (n - 1) & n;
count++;
}
return count;
}
}
12. 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路： 幂运算注意指数小于等于0时的特殊情况，等于0时返回1；小于0时，底数不可为0。另外简化幂运算可以提高运行效率。最原始的方法，若指数为n，则需循环n次，可以通过二进制表示指数，减少循环次数。
例， 指数n=5，二进制表示为101，底数m=2。
m^n = 2^1001 = (2^100)*(2^001) = (2^4 * 2^1) = 2^5
将5表示成二进制数之后，与1相与，即可得最右一个是否为1，若为1则计算一次幂运算，向右移位继续判断最后一位是否为1，第一个1为底数的1次，第二个1位底数的2次，第三个1为底数的4次……，最后将结果相乘即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public double Power(double base, int exponent) {
boolean negative = false;
double result = 1;
if(exponent == 0) return 1;
if(exponent < 0) {
exponent = -exponent;
negative = true;
if(base == 0) return 0;
}
while(exponent != 0){
if((exponent & 1) == 1){
result *= base;
}
base *= base;
exponent >>= 1;
}
return negative? 1/result: result;
}
}
13. 调整数组顺序使奇数位于偶数前
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路： 开辟两个新的vector，一个存奇数，一个存偶数，再拼接。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public void reOrderArray(int [] array) {
int oddCount = 0, start = 0;
for(int i : array){
if(i % 2 == 1) oddCount+=1;
}
int[] tmp = new int[array.length];
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1) tmp[start++] = array[i];
else tmp[oddCount++] = array[i];
}
for(int i = 0; i < array.length; i++){
array[i] = tmp[i];
}
}
}